Динамическое программирование. Нередко не удается разбить задачу на небольшое число подзадач, объединение решений которых позволяет получить решение исходной задачи

Нередко не удается разбить задачу на небольшое число подзадач, объединение решений которых позволяет получить решение исходной задачи. В таких случаях мы можем попытаться разделить задачу на столько подзадач, сколько необходимо, затем каждую подзадачу разделить на еще более мелкие подзадачи и т.д. Если бы весь алгоритм сводился именно к такой последовательности действий, мы бы получили в результате алгоритм с экспоненциальным временем выполнения. Но зачастую удается получить лишь полиномиальное число подзадач и поэтому ту или иную подзадачу приходится решать многократно. Если бы вместо этого мы отслеживали решения каждой решенной подзадачи и просто отыскивали в случае необходимости соответствующее решение, мы бы получили алгоритм с полиномиальным временем выполнения.

С точки зрения реализации иногда бывает проще создать таблицу решений всех подзадач, которые нам когда-либо придется решать. Мы заполняем эту таблицу независимо от того, нужна ли нам на самом деле конкретная подзадача для получения общего решения. Заполнение таблицы подзадач для получения решения определенной задачи получило название динамического программирования (это название происходит из теории управления).1

Алгоритм Кратчайший путь из одного источника (алгоритм Дейкстры)

В задаче нахождения кратчайших путей из одного источника ситуация иная. Хотя нет причин предполагать, что для ее решения понадобится более 0(е) времени, ни один такой алгоритм не известен. Мы обсудим алгоритм сложности , работа которого основана на построении множества S узлов, кратчайшие расстояния до которых от источника известны. На каждом шаге к S добавляется тот из оставшихся узлов, скажем и, расстояние до которого от источника меньше всех других оставшихся узлов. Если стоимости всех ребер неотрицательны, то можно быть уверенным, что путь из источника в v проходит только через узлы из S. Поэтому достаточно найти для каждого узла v кратчайшее расстояние до него от источника вдоль пути, проходящего только через узлы из S.

Вход. Ориентированный граф G== (V, Е), источник и функция , отображающая множество ЕхЕ в множество неотрицательных вещественных чисел. Полагаем , если и ,

Метод: Строим такое множество вершин , что кратчайший путь из источника в каждый узел целиком лежит в . Элемент массива содержит стоимость кратчайшего пути ведущего из в , который проходит только через узлы из .

Чтобы показать корректность, надо доказать индукцией по размеру множества S, что для каждого ребра число равно длине кратчайшего пути из в . Более того, для всех число равно длине кратчайшего пути из в , лежащего целиком (если не считать сам узел v) в S.

Базис. Пусть ||S|| = 1. Кратчайший путь из в себя имеет длину 0, а путь из в , лежащий целиком (исключая ) в S, состоит из единственного ребра . Таким образом, строки 2 и 3 корректно формируют начальные значения массива D.

Шаг индукции. Пусть w — узел, выбранный в строке 5. Если число D[w] не равно длине кратчайшего пути из v0 в w, то должен быть более короткий путь Р. Этот путь Р должен содержать некоторый узел, отличный от w и не принадлежащий S. Пусть v - первый такой узел на Р. Но тогда расстояние от до меньше D[w], а кратчайший путь в целиком (исключая сам узел и) лежит в S. Следовательно, по предположению индукции в момент выбора w, пришли к противоречию. Отсюда заключаем, что такого пути Р нет и — длина кратчайшего пути из в w. Второе утверждение (о том, что остается корректным) очевидно ввиду строки 8.

Жадные алгоритмы

Рассмотрим небольшую "детскую" задачу. Допустим, что у нас есть монеты достоинством 25, 10, 5 копеек и 1 копейка и нужно вернуть сдачу 63 копейки. Почти не раздумывая, мы преобразуем эту величину в две монеты по 25 копеек, одну монету в 10 копеек и три монеты по одной копейке. Нам не только удалось быстро определить перечень монет нужного достоинства, но и, по сути, мы составили самый короткий список монет требуемого достоинства.

На каждом шаге алгоритма мы выбирали монету наибольшего достоинства, которое удовлетворяло ограничениям нашей задачи. Эту монету мы исключали из общей суммы и вновь решали модифицированную задачу. Этот метод внесения изменений называется "жадным" алгоритмом. На каждой отдельной стадии "жадный" алгоритм выбирает тот вариант, который является локально оптимальным в том или ином смысле. Обратите внимание, что алгоритм для определения сдачи обеспечивает в целом оптимальное решение лишь вследствие особых свойств монет. Если бы у нас были монеты достоинством 1 копейка, 5 и 11 копеек и нужно было бы дать сдачу 15 копеек, то "жадный" алгоритм выбрал бы сначала монету достоинством 11 копеек, а затем четыре монеты по одной копейке, т.е. всего пять монет. Однако в данном случае можно было бы обойтись тремя монетами по 5 копеек.

Мы уже встречались в этой книге с несколькими "жадными" алгоритмами, например алгоритмом построения кратчайшего пути Дейкстры. Алгоритм кратчайшего пути Дейкстры является "жадным" в том смысле, что он всегда выбирает вершину, ближайшую к источнику, среди тех, кратчайший путь которых еще неизвестен.

Следует подчеркнуть, что не каждый "жадный" алгоритм позволяет получить оптимальный результат в целом. Как нередко бывает в жизни, "жадная стратегия" подчас обеспечивает лишь сиюминутную выгоду, в то время как в целом результат может оказаться неблагоприятным. Посмотрим, например, что произойдет, если в алгоритмах Дейкстры допустить наличие ребер с отрицательными весами. то алгоритм Дейкстры в некоторых случаях уже не позволяет получить кратчайшие пути.

Другим примером применения стратегии жадного алгоритма является алгоритм Крускала

«построения остовного дерева минимальной сложности в связном графе». Рассмотрим граф , ребрам которого приписаны некоторые веса. Требуется построить остовное дерево минимальной сложности (Под сложностью понимается сумма весов ребер, составляющих остовное дерево). Алгоритм Крускала является типичным представителем алгоритмов, в которых используются АТД «объединить, найти» В начальный момент времени дерево представляет собой множество одноэлементных подмножеств, каждое из которых содержит вершину графа. В процессе работы алгоритма ребро минимального веса попадает в остовное дерево, если оно на этот момент связывае различные множества вершин. После этого соответствующие множества сливаются различные подмножества сливаются, выбирается очередное ребро минимальной стоимости и процесс повторяется пока не будет получено единственное множество.

Алгоритм имеет сложность , где - число ребер графа.

"Жадный" алгоритм для задачи коммивояжера, речь о котором пойдет ниже, является вариантом алгоритма Крускала. Здесь, как и в основном алгоритме Крускала, сначала рассматриваются самые короткие ребра. В алгоритме Крускала очередное ребро принимается в том случае, если оно не образует цикл с уже принятыми ребрами; в противном случае ребро отвергается. В случае задачи коммивояжера "критерием принятия" ребра является то, что рассматриваемое ребро (в сочетании с уже принятыми ребрами)

• не приводит к появлению вершины со степенью три и более';

• не образует цикл (за исключением случая, когда количество выбранных ребер

равняется количеству вершин в рассматриваемой задаче).

Совокупности ребер, выбранных в соответствии с этими критериями, образуют совокупность несоединенных путей; такое положение сохраняется до выполнения последнего шага, когда единственный оставшийся путь замыкается, образуя маршрут.

Поиск с возвратом

Иногда приходится иметь дело с задачей поиска оптимального решения, когда невозможно применить ни один из известных методов, способных помочь отыскать оптимальный вариант решения, и остается прибегнуть к последнему средству — полному перебору. Этот раздел посвящен систематическому описанию метода полного перебора, называемого поиском с возвратом, а также метода, называемого альфа-бета отсечением, который зачастую позволяет существенно сократить объем операций поиска.

Задача. Имеется n предметов, соответственно веса: v[1],v[2],... v[n]. Можно ли их разложить на три кучи так, чтобы эти кучи имели одинаковый вес.

Идея. Попытки найти некий разумно обоснованный «выгодный» порядок расклада предметов сталкиваются с трудностями... Мы полностью откажемся от подобных попыток, и воспользуемся довольно «лобовым» подходом.

Опишем множество возможных кандидатов в решение - множество возможных раскладов n предметов на 3 кучи.

Зададим на этом множестве некий линейный порядок перечисления кандидатов.

Тогда задача специфицируется формулой: «решение»:=$xΫмножество кандидатов» («x - является решением»).

И соответствующий алгоритм перебора позволяет найти решение (если конечно оно есть):

«кандидат»:=«первый»;

«решение»:=false; «перебрали все»:=false;

WHILE NOT «решение» AND NOT «перебрали все» DO

IF «кандидат является решением»

THEN «решение»:=true

ELSE IF «следующий имеется»

THEN «кандидат»:=«следующий»

ELSE «перебрали все»:=true

Для аккуратной реализации этой идеи надо обеспечить выполнение ряда условий.

Ø Необходимые условия:

¨ множество кандидатов должно быть полным в смысле - должно содержать решение, если оно существует;

¨ должны быть реализуемы действия «кандидат»:= «первый», «кандидат»:= «следующий» и проверка условия «кандидат является решением».

Ø Желательные условия:

¨ множество кандидатов желательно иметь «поменьше»;

¨ порядок на этом множестве желательно иметь «полегче», в смысле реализуемости действий «первый», «следующий»... и т.п.

Представление множества возможных кандидатов в решение. Обозначим кучи - a,b,c. Тогда любой расклад n предметов по этим трем кучам можно задать соответствующим словом длины ровно n в алфавите {a,b,c}, i-ая буква - имя кучи, в которую попал i-й предмет. Линейный порядок на этом множестве возможных кандидатов - можно выбрать лексикографический, так упорядочены слова в словаре.

Реализуемость действий «первый», «следующий» и «является» возможно не совсем примитивна, но достаточно очевидна. Остаются пожелания - «поменьше» и «полегче», т.е. вопросы оптимизации алгоритма.

Рассмотрим две фундаментальные идеи в применении к этим вопросам.

Ø «Можно не различать то, что неразличимо с точки зрения интересующих нас свойств».

Пусть мы имеем некий расклад предметов. Если содержимое куч «a» и «b» поменять местами, то правильный расклад останется правильным, а неправильный - неправильным. Это означает, что можно уменьшить объем множества рассматриваемых кандидатов в решение, но... скорее всего усложнится алгоритм перечисления элементов сокращенного множества.

Математически это оформляется заданием подходящего отношения эквивалентности на множестве и факторизацией этого множества - рассмотрением только множества представителей (по одному) из каждого класса эквивалентности.

Ø На множестве можно выбрать отношение порядка такое, чтобы при появлении информации о неудачной попытке расклада оказались «близко под рукой» («в окрестности») кандидаты в решение, о которых можно сделать гарантированное заключение - они тоже не могут быть решениями, и пропустить проверку этих «бесперспективных» кандидатов. На этой идее основан метод перебора с возвратами.

Метод перебора с возвратами (BackTracking).

Ø Пусть на множестве возможных кандидатов в решение задан частичный «древовидный порядок»:

r1<r2, r1<r3, но r2 и r3 - несравнимы.

Ø Пусть этот порядок обладает важным свойством - если кандидат в решение не является решением, то в поддереве этого кандидата все кандидаты тоже не являются решениями.

Ø Пусть линейный порядок перечисления кандидатов соответствует префиксному обходу дерева - в глубину слева направо.

Ø Тогда алгоритм перебора можно уточнить так, чтобы при обнаружении кандидата, не являющегося решением, пропускать проверку «бесперспективных» кандидатов в его поддереве.

Вернемся к задаче о раскладе предметов.

Ø Расширим множество кандидатов в решение. Точнее добавим в него кандидатов в частичное решение, которые соответствуют частичным раскладам предметов в 3 кучи. Причем раскладывать предметы будем по порядку - от 1-го до n-го. Любой такой расклад первых i предметов (i<=n) можно задать соответствующим словом длины i в алфавите {a,b,c}.

Ø Расклад первых i предметов назовем недопустимым, если вес хотя бы одной кучи уже превышает треть общего веса, т.е. > (v[1]+v[2]+... v[n])/3.

Ø Все эти слова длины <=n можно разместить на дереве, воспользовавшись рассуждением: в корне - «пустое слово», любое слово имеет ровно 3 варианта продолжения - добавить в конец букву a, b или c.

Математически это оформляется определением частичного порядка на словах:

(слово1 «меньше» слово2) =

(слово1 «является началом для» слово2).

Кстати, префиксный обход этого дерева, т.е. соответствующий линейный порядок перечисления кандидатов - все тот же лексикографический (только на словах длины <=n).

Ø Этот частичный «древовидный порядок» на множестве кандидатов в частичное решение обладает интересующим нас свойством - если расклад первых i предметов уже недопустим, то нет смысла его продолжать.

Ø Воспользуемся стековым алгоритмом префиксного обхода дерева. В стеке будет храниться текущий кандидат в частичное решение. Интуитивно достаточно ясно, что такой информации о прошлом должно быть достаточно для принятия решений в будущем.

С учетом необходимости избегать обхода «бесперспективных» поддеревьев, алгоритм описывается следующей таблицей:

	Условие
размещение допустимое	размещение недопустимое
размещено все	размещено не все
В вершине стека	a	успешный конец	Добавить в стек «a» (cпуск вниз по левой ветви дерева; положить следующий предмет в кучу «a»).	Заменить в вершине стека «a» на «b» (возврат вверх и спуск вниз по следующей ветви дерева; переложить текущий предмет из кучи «a» в кучу «b»).
b	успешный конец	Добавить в стек «a» (cпуск вниз по левой ветви дерева; положить следующий предмет в кучу «a»).	Заменить в вершине стека «b» на «c» (возврат вверх и спуск вниз по следующей ветви дерева; переложить текущий предмет из кучи «b» в кучу «c»).
c	успешный конец	Добавить в стек «a» (cпуск вниз по левой ветви дерева; положить следующий предмет в кучу «a»).	Свертка: [a/b][c...]Þ[b/c] (многократный возврат вверх до вершины, имеющей непройденную ветвь вниз, и спуск по этой непройденной ветви).

Операция «свертка»: выталкивание верхних элементов «c» до тех пор, пока в вершине не появится отличный от «c». Если в итоге стек окажется пустым, то это свидетельствует о завершении полного перебора, в противном случае выполняется замена - либо «a» на «b», либо «b» на «c».

Операция «свертка» соответствует ситуации, когда все три варианта размещения текущего предмета оказались недопустимыми. В этом случае текущий предмет приходится возвращать в список неразмещенных и текущим становится ему предшествующий, для которого ситуация может оказаться такой же... На дереве это соответствует подъему вверх по крайней правой ветви некоторого поддерева.

Если при реализации алгоритма разбор случаев выполнять сначала по столбцам (по условиям), то можно провести очевидные группировки:

	Условие
размещение допустимое	размещение недопустимое
размещено все	размещено не все
В вершине стека	a	успешный конец	Добавить в стек «a».	Свертка: [a/b][c...]Þ[b/c], в которой возможно отсутствует список выталкиваемых «c».
b
c

PROGRAM pp{PROGRAM\Prj6\Prj6.dpr}; CONST n=20;

VAR v: ARRAY[1..n] OF REAL; Yes{«решение»}: BOOLEAN;

Stek: ARRAY[1..n] OF ’a’..’c’; iStek:0..n;

BEGIN {ввод(v[1..n])};

{«кандидат»:=«первый»: кладем 1-й предмет в кучу «a»}

Stek[1]:=’a’;iStek:=1; {«решение»}Yes:=false;

WHILE {«не решение» и «перебрали не все»}

NOT Yes AND (iStek>0)

DO {Разбор случаев по «Условию»}

IF {«кандидат допустим»}

THEN IF {«решение полное»} iStek=n

THEN {«решение»}Yes:=true

ELSE {«кандидат»:=«следующий, более полный»,

т.е. спуск вниз по ветви «a»}

BEGIN iStek:=iStek+1; Stek[iStek]:=’a’ END

ELSE BEGIN {многократный возрат}

WHILE (iStek>0) AND (Stek[iStek]=’c’)

DO iStek:=iStek-1;

IF {«перебрали не все»}(iStek>0)

THEN {«кандидат»:=«следующий, непроверенный»}

IF Stek[iStek]=’a’ THEN Stek[iStek]:=’b’

ELSE {Stek[iStek]=’b’} Stek[iStek]:=’c’

END;

IF {«решение»} Yes THEN {вывод содержимого стека}

ELSE WRITELN(‘Решения нет’) END.

Где проверку условия {«кандидат допустим»} можно реализовать, например с помощью функции:

FUNCTION Dopustim: BOOLEAN;

VAR {Текущие веса куч}Sa,Sb,Sc: REAL; i: INTEGER;

{С: REAL треть общего веса предметов}

BEGIN Sa:=0;Sb:=0;Sc:=0; FOR i:=1 TO iStek DO BEGIN

IF Stek[iStek]=’a’ THEN Sa:=Sa+v[i] ELSE

IF Stek[iStek]=’b’ THEN Sb:=Sb+v[i] ELSE Sc:=Sc+v[i];

Dopustim:=(Sa<=C)AND(Sb<=C)AND(Sc<=C) END END

Такая реализация проверки условия {«кандидат допустим»} приводит к необоснованным повторным перевычислениям текущих весов куч Sa,Sb,Sc. Устранить этот недостаток можно: определить переменные Sa,Sb,Sc как глобальные и поддерживать текущие значения этих переменных в процессе перемещений по дереву.

Алгоритмы перебора с возвратами, это классический случай алгоритмов, для которых аккуратная рекурсивная реализация не просто уместна, но и по сути не уступает стековой реализации по эффективности.

Вспомните задачу коммивояжера, которую мы рассмотрели в одном из предыдущих разделов. В связи с этой задачей мы описали так называемый "жадный алгоритм", позволяющий найти хороший, хотя и необязательно оптимальный, маршрут. Посмотрим, как можно было бы найти оптимальный маршрут путем систематического просмотра всех маршрутов. Это можно было бы сделать, рассмотрев все перестановки узлов и определив маршрут, который проходит через узлы в соответствующей последовательности, учитывая наилучший из найденных до сих пор маршрутов. Время, которое потребуется на реализацию такого подхода на графе с узлами, равняется , поскольку необходимо рассмотреть различных перестановок, а оценка каждой перестановки занимает время .