Эвристический поиск

Поиск в ширину с древовидным представлением путей кандидатов

Представление деревьев

Поиск в ширину. Древовидное представление множества путей-кандидатов

В предыдущем алгоритме мы хранили множество путей-кандидатов в виде списка. Такое представление является неэкономным с точки зрения расхода памяти, так как начальные участки путей дублируются. Будем хранить пути-кандидаты в виде дерева. Рассмотри представление дерева в Prolog’е.

Дерево — это либо лист, либо корень со списком поддеревьев.

tr = l(тип_вершины); % лист

t(тип_вершины, tlist). % корень + список поддеревьев

tlist = tr* % список деревьев

В качестве примера запишем в Prolog-нотации какое-нибудь дерево (рис. 4).

Рисунок 4. Дерево, записанное в Prolog-нотации

t(a,[t(b,[l(d),l(g)]),t(c,[l(f),l(c)])]).

На первый взгляд такая запись кажется очень громоздкой, но Prolog-нотация для списков очень компактна. Внутреннее представление дерева в памяти гораздо более эффективно.

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

Ключевую роль в программе будет играть отношение expo(«расширить»).

expo(Way,D,D1,Yes,Sol)

Way — путь от стартовой вершины до корня расширяемого дерева

D — расширенное дерево

D1 — расширенное дерево

Yes — флаг (есть ли решение)

Sol — путь решение

При каждом обращении к expo Way и D конкретизированы. Далее возможны 3 ситуации и, соответственно, 3 типа возвращаемого результата.

D содержит целевую вершину, D1 — свободная переменная, Yes = 1, Sol — конкретизирована.

D не содержит целевую вершину, D1 — расширение D на один уровень, Yes = 0, Sol — свободная.

D не содержит целевую вершину, D — тупиковое и expo возвращает неудачу.

Рассмотрим пример (рис. 5). Требуется расширить дерево t(a,[l(b),l(c)]), причем ветвь a-b тупиковая, а ветвь a-c расширяется до
a-c-d. Чтобы расширить дерево, нужно расширить список его поддеревьев. Поддерево l(b) удаляется из списка. Так как оно тупиковое, то вместо него к списку ничего не добавляется. Поддерево l(c) удаляется из списка, вместо него помещается расширенное дерево t(c,[l(d)]).

Рисунок 5. Удаление тупиковой ветви из дерева поиска

Полученное дерево D1 — расширение дерева D. Раньше из списка путей удалялись тупиковые пути, теперь из дерева поиска удаляются тупиковые ветки.

Окончательно процедура expo состоит из 3-х правил.

% (1) лист l(Х) — целевая вершина

expo(Way,l(X),_,1,[X|Way):- end(X).

% (2) лист l(X) расширяется до дерева t(X,LD)

expo(Way,l(X),t(X,LD),0,_):-

findall(Y,continue(X,Way,Y),LD).

Findall собирает все Y-соседки X и делает из них одновершинные деревья, которые накапливаются в списке LD.

% (3) для расширения дерева t(X,LD) используется вспомогательная

% процедура expall — "расширить всех"

expo(Way,t(X,LD),t(X,LD1),Yes,Sol):-

expall([X|Way], LD,[],LD1,Yes,Sol).

Рассмотрим отношение expall.

Корень X расширяемого дерева добавляется к пути, затем список поддеревьев LD расширяется до LD1. Expall организована по типу восходящей рекурсии, поэтому в пустом списке 3-го аргумента будут накапливаться расширенные поддеревья из LD. Когда список LD опустеет, произойдет копирование расширенных поддеревьев из 3-го аргумента в четвертый.

Если в каком-то из расширенных поддеревьев окажется целевая вершина, то Yes =1 и Sol окажется конкретизирована. Если все поддеревья из LD окажутся тупиковыми, то expall вернет неудачу. Если не все поддеревья из LD тупиковые, и в них нет целевых вершин, то Yes = 0 и LD1 (список расширенных поддеревьев) конкретизирован.

% (1) все поддеревья из LD расширены

expall(_,[],[D|DD],[D|DD],0,_).

Список LD пуст, расширенные поддеревья копируются из 3-го аргумента в четвертый.

Если все поддеревья из LD были тупиковые, то LD1=[] и не сопоставляются с [D|DD], т.е. expall возвращает неудачу.

% (2) первое дерево D из LD содержит целевую вершину

expall(Way,[D|DD],DD1,LD1,1,Sol):-

expo(Way,D,D1,1,Sol).

Каким образом expall расширяет список поддеревьев LD? Берет первое дерево D листом, то expo его расширит, если нет — вызовет expall. Таким образом, процедуры expo и expall организованны по типу перекрестной рекурсии.

% (3) первое дерево не содержит целевую вершину и не
% является тупиковым

expall(Way,[D|DD],DD1,LD1,Yes,Sol):-

expo(Way,D,D1,Yes1,Sol),

Yes1=0,!,

expall(Way,DD,[D1|DD1],LD1,Yes,Sol).

% (4) первое дерево не содержит целевую вершину и
% тупиковое

expall(Way,[D|DD],DD1,LD1,Yes,Sol):-

expall(Way,DD,DD1,LD1,Yes,Sol).

На тупиковом дереве expo в правиле (3) возвращает неудачу и происходит переход на правило (4), где D удалено из списка расширяемых деревьев, и вызвана рекурсия expall для хвоста DD.

Если все деревья окажутся тупиковыми и expall, вызванная с пустым списком, вернет неудачу, то возврат пойдет к последнему расширенному дереву, чтобы попытаться расширить его по другому. Этот возврат на предыдущий уровень рекурсии блокируется отсечением в правиле (3) процедуры expall. Если это отсечение убрать, то программа зациклиться на первой же тупиковой ветви.

Запуск ширины из стартовой вершины происходит в процедуре solve:

solve(A,Sol):-

width(l(A),Sol).

Процедура поиска в ширину.

% D содержит целевую вершину

width(D,Sol):-

expo([],D,D1,Yes,Sol),

Yes = 1.

% рекурсивный вызов с расширенным деревом

width(D,Sol):-

expo([],D,D1,Yes,Sol),

Yes = 0,

Width(D1,Sol).

continue(X,Way,l(Y)):-

go(X,Y),

not(member(Y,Way)).

Задание. Написать программу, реализующую составление минимального плана перестановок кубиков поиском в ширину с древовидным представлением путей–кандидатов в решение. Определить ее вычислительную сложность.

Дата добавления: 2015-06-27