Программирование на языке Пролог для искусственного интеллекта
По крайней мере одно дерево
цель( В).
расширить( П, Л( В), д( В, Пд), нет, _ ) :-
bagof( л( B1),
( после( В, B1), not принадлежит( В1, П)), Пд).
расширить( П, д( В, Пд), д( В, Пд1), ЕстьРеш, Реш) :-
расширитьвсе( [В | П], Пд, [ ], Пд1, ЕстьРеш, Реш).
расширитьвсе( _, [ ], [Д | ДД], [Д | ДД], нет, _ ).
% По крайней мере одно дерево должно вырасти
расширитьвсе( П, [Д | ДД], ДД1, Пд1, ЕстьРеш, Реш) :-
расширить ( П, Д, Д1, ЕстьРеш1, Реш),
( ЕстьРеш 1= да, ЕстьРеш = да;
ЕстьРеш1 = нет, !,
расширитьвсе( П, ДД, [Д1 | ДД1], Пд1, ЕстьРеш, Реш));
расширитьвсе( П, ДД, ДД1, Пд1, ЕстьРеш, Реш ).
line();
Рис. 11. 13. Реализация поиска в ширину с использованием
древовидного представления множества путей-кандидатов.
Мы разработали эту более сложную реализацию поиска в ширину не только для того, чтобы получать программу более экономичную по сравнению с предыдущей версией, но также и потому, что такое решение задачи может послужить хорошим стартом для перехода к усложненным программам поиска, управляемым эвристиками, таким как программа поиска с предпочтением из гл. 12.
