Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Поиск в ширину с древовидным представлением путей кандидатовПоиск в ширину строит дерево поиска, объединяющее все пути-кандидаты. Это дерево будет расширяться до тех пор, пока не захватит целевую вершину или не окажется тупиковым. Ключевую роль в программе будет играть отношение 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 расширяется до Рисунок 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)). Задание. Написать программу, реализующую составление минимального плана перестановок кубиков поиском в ширину с древовидным представлением путей–кандидатов в решение. Определить ее вычислительную сложность.
|