Программирование на языке Пролог для искусственного интеллекта
такой ветви, что она либо
е. такой ветви, что она либо не может быть продолжена из-за отсутствия преемников, либо любое ее продолжение приводит к циклу.
Решение
= неконкретизировано.
Если в дереве Дер нет ни одной целевой вершины и, кроме того, оно не может быть расширено, то процедура расширить
терпит неудачу.
Процедура верхнего уровня для поиска в ширину
вширину( Дер, Решение)
отыскивает Решение либо среди множества кандидатов Дер, либо в его расширении. На рис. 11.3 показано, как выглядит программа целиком. В этой программе имеется вспомогательная процедура расширитьвсе. Она расширяет все деревья из некоторого списка, и затем, выбросив все "тупиковые" деревья", собирает все полученные расширенные деревья в один новый список. Используя механизм возвратов, она также порождает все решения, обнаруженные в деревьях из списка. Имеется одна дополнительная деталь: по крайней мере одно из деревьев должно "вырасти". Если это не так, то процедуре расширитьвсе не удается получить ни одного расширенного дерева - все деревья из списка оказываются "тупиковыми".
line();
% ПОИСК В ШИРИНУ
% Множество кандидатов представлено деревом
решить( Старт, Решение) :-
вширину( л( Старт), Решение).
вширину( Дер, Решение) :-
расширить( [ ], Дер, Дер1, ЕстьРеш, Решение),
( ЕстьРеш = да;
ЕстьРеш = нет, вширину( Дер1, Решение) ).
расширить( П, Л( В), _, да, [В | П] ) :-
