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




Древовидное представление множества кандидатов - часть 4


        расширить( П, Л( В), д( В, Пд), нет, _ ) :-
                bagof( л( B1),
                            ( после( В, B1), not принадлежит( В1, П)), Пд).

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

        расширитьвсе( _, [ ], [Д | ДД], [Д | ДД], нет, _ ).
                                % По крайней мере одно дерево должно вырасти

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

line();

Рис. 11. 13.  Реализация поиска в ширину с использованием
древовидного представления множества путей-кандидатов.

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




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