Поиск с возвратом. Задача разбиения множеств

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

Задача. Имеется 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» поменять местами, то правильный расклад останется правильным, а неправильный - неправильным. Это означает, что можно уменьшить объем множества рассматриваемых кандидатов в решение, но... скорее всего усложнится алгоритм перечисления элементов сокращенного множества.

Продолжение 30

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

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

Метод перебора с возвратами (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).

Продолжение 30

Этот частичный «древовидный порядок» на множестве кандидатов в частичное решение обладает интересующим нас свойством - если расклад первых 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 как глобальные и поддерживать текущие значения этих переменных в процессе перемещений по дереву.

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

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