Неизвестно - Prolog

Рис. 11. 12. Отношение paсширить( Путь, Дер, Дер1, ЕстьРеш, Решение):

s- стартовая вершина, g- целевая вершина. Решение- это Путь,

продолженный вплоть до g. Дер1- результат расширения дерева

Дерна один уровень вниз.

получить поддерево Дер1как результат расширения Дерна один уровень. Но в случае, когда в процессе расширения поддерева Дервстретится целевая вершина, процедура расширитьдолжна сформировать соответствующий решающий путь.

Итак, процедура расширитьбудет порождать два типа результатов. На конкретный вид результата будет указывать значение переменной ЕстьРеш:

(1) ЕстьРеш= да

Решение= решающий путь, т. е. Путь, продолженный до целевой вершины.

Дер1= неконкретизировано.

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

(2) ЕстьРеш= нет

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

Решение= неконкретизировано.

Если в дереве Дернет ни одной целевой вершины и, кроме того, оно не может быть расширено, то процедура расширитьтерпит неудачу.

Процедура верхнего уровня для поиска в ширину

вширину( Дер, Решение)

отыскивает Решениелибо среди множества кандидатов Дер, либо в его расширении. На рис. 11.3 показано, как выглядит программа целиком. В этой программе имеется вспомогательная процедура расширитьвсе. Она расширяет все деревья из некоторого списка , и затем, выбросив все "тупиковые" деревья", собирает все полученные расширенные деревья в один новый список. Используя механизм возвратов, она также порождает все решения, обнаруженные в деревьях из списка. Имеется одна дополнительная деталь: по крайней мере одно из деревьев должно "вырасти". Если это не так, то процедуре расширитьвсене удается получить ни одного расширенного дерева - все деревья из списка оказываются "тупиковыми".

% ПОИСК В ШИРИНУ

% Множество кандидатов представлено деревом

решить( Старт, Решение) :-

вширину( л( Старт), Решение).

вширину( Дер, Решение) :-

расширить( [ ], Дер, Дер1, ЕстьРеш, Решение),

( ЕстьРеш = да;

ЕстьРеш = нет, вширину( Дер1, Решение) ).

расширить( П, Л( В), _, да, [В | П] ) :-

цель( В).

расширить( П, Л( В), д( В, Пд), нет, _ ) :-

bagof( л( B1),

( после( В, B1), not принадлежит( В1, П)), Пд).

расширить( П, д( В, Пд), д( В, Пд1), ЕстьРеш, Реш) :-

расширитьвсе( [В | П], Пд, [ ], Пд1, ЕстьРеш, Реш).

расширитьвсе( _, [ ], [Д | ДД], [Д | ДД], нет, _ ).

% По крайней мере одно дерево должно вырасти

расширитьвсе( П, [Д | ДД], ДД1, Пд1, ЕстьРеш, Реш) :-

расширить ( П, Д, Д1, ЕстьРеш1, Реш),

( ЕстьРеш 1= да, ЕстьРеш = да;

ЕстьРеш1 = нет, !,

расширитьвсе( П, ДД, [Д1 | ДД1], Пд1, ЕстьРеш, Реш));

расширитьвсе( П, ДД, ДД1, Пд1, ЕстьРеш, Реш ).

Рис. 11. 13. Реализация поиска в ширину с использованием

древовидного представления множества путей-кандидатов.

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

Упражнения

11. 5. Перепишите программу поиска в ширину рис. 11.10, используя разностное представление для списка путей-кандидатов и покажите, что в результате получится программа, приведенная на рис. 11.11. Зачем в программу рис. 11.11 включена цель

Пути \== Z

Проверьте, что случится при поиске в пространстве состояний рис. 11.9, если эту цель опустить. Различие в выполнении программы, возникнет только при попытке найти новые решения в ситуации, когда не осталось больше ни одного решения.