Баланс подзадач
При проектировании алгоритмов приходится идти на различные компромиссы. Очевидно, что по мере возможности необходимо сбалансировать вычислительные затраты на выполнение различных частей алгоритма.
При использовании алгоритмов декомпозиции желательно, чтобы подзадачи были примерно одинакового размера. Например, сортировку вставками можно рассматривать как разбиение задачи на две подзадачи – одна размером 1, а другая – п-1, причем максимальные затраты на выполнение слияния равняются п шагам. Сортировка слиянием разбивает задачу на две подзадачи, каждая размером п/2, а ее эффективность равняется О(п logn). Складывается впечатление, что разбиение задачи на равные (или примерно равные) подзадачи является важным фактором обеспечения высокой эффективности алгоритмов.
Динамическое программирование
Нередко не удается разбить задачу на небольшое число подзадач, объединение решений которых позволяет получить решение исходной задачи. В таких случаях можно попытаться разделить задачу на столько подзадач, сколько необходимо, затем каждую подзадачу разделить на еще более мелкие подзадачи и т.д. Если бы весь алгоритм сводился именно к такой последовательности действий, в результате получили бы алгоритм с экспоненциальным временем выполнения.
Но зачастую удается получить лишь полиномиальное число подзадач и поэтому ту или иную подзадачу приходится решать многократно. Если бы вместо этого отслеживали решения каждой решенной подзадачи и просто отыскивали в случае необходимости соответствующее решение, был бы получен алгоритм с полиномиальным временем выполнения.
С точки зрения реализации иногда бывает проще создать таблицу решений всех подзадач, которые когда-либо придется решать. Заполняем эту таблицу независимо от того, нужна ли на самом деле конкретная подзадача для получения общего решения. Заполнение таблицы подзадач для получения решения определенной задачи получило название динамического программирования (это название происходит из теории управления).
Формы алгоритма динамического программирования могут быть разными – общей их «темой» является лишь заполняемая таблица и порядок заполнения ее элементов.
«Жадные» алгоритмы
Рассмотрим небольшую задачу. Допустим, что есть монеты достоинством 50, 10, 5 копеек и 1 копейка и нужно вернуть сдачу 83 копейки. Почти не раздумывая, преобразуем эту величину в одну монету в 50 копеек, три монеты по 10 копеек и три монеты по одной копейке. Удалось не только быстро определить перечень монет нужного достоинства, но и составить самый короткий список монет требуемого достоинства.
Алгоритм, которым воспользовались только что, заключался в выборе монеты самого большого достоинства (50 копеек), но не больше 83 копеек, добавлению ее в список сдачи и вычитанию ее стоимости из 83 (получается 33 копейки). Затем снова выбираем монету самого большого достоинства, но не больше остатка (33 копеек): этой монетой оказывается монета в 10 копеек. Эту монету мы опять добавляем в список сдачи, вычитаем ее стоимость из остатка и т.д.
Этот метод внесения изменений называется «жадным» алгоритмом. На каждой отдельной стадии «жадный» алгоритм выбирает тот вариант, который является локально оптимальным в том или ином смысле. Обратите внимание, что алгоритм для определения сдачи обеспечивает в целом оптимальное решение лишь вследствие особых свойств монет. Если бы были монеты достоинством 1 копейка, 5 и 11 копеек и нужно было бы дать сдачу 15 копеек, то «жадный» алгоритм выбрал бы сначала монету достоинством 11 копеек, а затем четыре монеты по одной копейке, т.е. всего пять монет. Однако в данном случае можно было бы обойтись тремя монетами по 5 копеек.
Наиболее распространенными «жадными» алгоритмами можно назвать алгоритм построения кратчайшего пути Дейкстры и алгоритм построения остовного дерева минимальной стоимостью Краскала. Алгоритм кратчайшего пути Дейкстры является «жадным» в том смысле, что он всегда выбирает вершину, ближайшую к источнику, среди тех, кратчайший путь которых еще неизвестен. Алгоритм Краскала также «жадный», так как он выбирает из остающихся ребер, которые не создают цикл, ребро с минимальной стоимостью.
Следует подчеркнуть, что не каждый «жадный» алгоритм позволяет получить оптимальный результат в целом. Как нередко бывает в жизни, «жадная стратегия» подчас обеспечивает лишь сиюминутную выгоду, в то время как в целом результат может оказаться неблагоприятным. Посмотрим, например, что произойдет, если в алгоритмах Дейкстры и Краскала допустить наличие ребер с отрицательными весами. Оказывается, что на алгоритм Краскала построения остовного дерева это никак не повлияет: с его помощью по-прежнему можно будет получить дерево минимальной стоимости. Но алгоритм Дейкстры в некоторых случаях уже не позволяет получить кратчайшие пути.
Пример 10.1. На рисунке 10.2 показан граф с ребром отрицательной стоимости между вершинами b и с.
Рис. 10.2. Граф с ребром отрицательного веса.
Если источником является вершина s, то алгоритм Дейкстры сначала правильно определяет, что минимальный путь до а имеет протяженность 1. Теперь, рассматривая ребра от s (или а) до b или с, алгоритм рассчитывает, что кратчайший путь от s до b, а именно s а b, имеет длину 3. Но далее получаем, что с имеет кратчайший путь от s длиной 1.
Однако «жадный» выбор b вместо с является неоправданным. Оказывается, что путь sасb имеет длину лишь 2, поэтому вычисленное нами минимальное расстояние для b является неправильным.
Существуют задачи, для которых ни один из известных «жадных» алгоритмов не позволяет получить оптимального решения; тем не менее имеются «жадные» алгоритмы, которые с большой вероятностью позволяют получать «хорошие» решения. Нередко вполне удовлетворительным можно считать «почти оптимальное» решение.
Пример 10.2. Рассмотрим одну знаменитую задачу, для получения оптимального решения которой из всех известных нам алгоритмов подходят лишь алгоритмы полного перебора, время выполнения которых зависит экспоненциально от объема входных данных. Эта задача, которая называется задачей коммивояжера, сводится к поиску в неориентированном графе с весовыми значениями ребер такого маршрута (простого цикла, включающего все вершины), у которого сумма весов составляющих его ребер будет минимальной. Такой маршрут часто называют гамильтоновым циклом.
Задача коммивояжера имеет ряд практических применений. Например, задача коммивояжера использовалась для составления маршрутов лиц, занимающихся выемкой монет из таксофонов. В этом случае вершинами являются места установки таксофонов и «базовый пункт». Стоимостью каждого ребра (отрезка маршрута) является время в пути между двумя точками (вершинами) на маршруте.
Еще одним применением задачи коммивояжера является задача обхода доски шахматным конем: надо найти последовательность ходов, которые позволят коню обойти все поля шахматной доски, попадая на каждое поле лишь один раз, и вернуться, в конце концов, на исходное поле. В этом случае роль вершин графа выполняют поля шахматной доски. Предполагается также, что ребра между двумя полями, которые являются «составными частями» хода коня, имеют нулевой вес; все остальные ребра имеют вес, равный бесконечности. Оптимальный маршрут имеет нулевой вес и должен быть маршрутом коня.
«Жадный» алгоритм для задачи коммивояжера является вариантом алгоритма Краскала. Здесь, как и в основном алгоритме Краскала, сначала рассматриваются самые короткие ребра. В алгоритме Краскала очередное ребро принимается в том случае, если оно не образует цикл с уже принятыми ребрами; в противном случае ребро отвергается. В случае задачи коммивояжера «критерием принятия» ребра является то, что рассматриваемое ребро (в сочетании с уже принятыми ребрами):
• не приводит к появлению вершины со степенью три и более;
• не образует цикл (за исключением случая, когда количество выбранных ребер равняется количеству вершин в рассматриваемой задаче).
Совокупности ребер, выбранных в соответствии с этими критериями, образуют совокупность несоединенных путей; такое положение сохраняется до выполнения последнего шага, когда единственный оставшийся путь замыкается, образуя маршрут.