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




Стратегия поиска в глубину - часть 4


Это правило можно сформулировать в виде отношения

        вглубину( Путь, Верш, Решение)

Как видно из рис. 11.6, Верш - это состояние, из которого необходимо найти путь до цели; Путь - путь (список вершин) между стартовой вершиной и Верш; Решение - Путь, продолженный до целевой вершины.

fig11_6.gif (1223 bytes)

Рис. 11. 6.  Отношение вглубину( Путь, В, Решение).

Для облегчения программирования вершины в списках, представляющих пути, будут расставляться в обратном порядке. Аргумент Путь нужен для того,

(1)        чтобы не рассматривать тех преемников вершины Верш, которые уже встречались раньше (обнаружение циклов);

(2)        чтобы облегчить построение решающего пути Решение. Соответствующая программа поиска в глубину показана на рис. 11.7.

line();

        решить( Верш, Решение) :-
                вглубину( [ ], Верш, Решение).

        вглубину( Путь, Верш, [Верш | Путь] ) :-
                цель( Верш).

        вглубину( Путь, Верш, Реш) :-
                после( Верш, Верш1),
                not принадлежит( Верш1, Путь),
                                        % Цикл ?
                вглубину( [Верш | Путь], Верш1, Реш).

line();

Рис. 11. 7.  Программа поиска в глубину без зацикливания.

Теперь наметим один вариант этой программы.


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