Prolog

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

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

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

отыскивает Решение либо среди множества кандидатов Дер, либо в его расширении. На рис. 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, используя разностное представление для списка путей-кандидатов и покажите, что в результате получится программа,