Программирование на языке Пролог для искусственного интеллекта


         

такой ветви, что она либо


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

            Решение

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

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

терпит неудачу.

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

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

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

line();

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

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

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

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


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

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

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

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


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

Содержание  Назад  Вперед