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

то одного множества вершин недостаточно. Поэтому мы будем хранить не множество вершин-кандидатов, а множество путей-кандидатов. Таким образом, цель

вширину( Пути, Решения)

истинна только тогда, когда существует путь из множества кандидатов Пути, который может быть продолжен вплоть до целевой вершины. Этот продолженный путь и есть Решение.

11.3.1. Списковое представление множества кандидатов

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

[ [СтартВерш] ]
решить( Старт, Решение) :-
 вширину( [ [Старт] ], Решение).
вширину( [ [Верш | Путь] | _ ], [Верш | Путь] ) :-
 цель( Верш).
вширину( [ [В | Путь] | Пути], Решение ) :-
 bagof( [B1, В | Путь ],
 ( после( В, В1), not принадлежит( В1, [В | Путь])),
   НовПути),
    % НовПути - ациклические продолжения пути [В | Путь]
 конк( Пути, НовПути, Пути1), !,
 вширину( Путь1, Решение);
 вширину( Пути, Решение).
  % Случай, когда у В нет преемника

Рис. 11.10. Реализации поиска в ширину.

Общие принципы поиска в ширину таковы:

Для того, чтобы выполнить поиск в ширину при заданном множестве путей-кандидатов, нужно:

• если голова первого пути — это целевая вершина, то взять этот путь в качестве решения, иначе

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

решить( Старт, Решение) :-
 вширь( [ [Старт] | Z ]-Z, Решение).
вширь( [ [Верш | Путь] | _ ]-_, [Верш | Путь] ) :-
 цель( Верш).
вширь( [ [В | Путь] | Пути]-Z, Решение ) :-
 bagof( [B1, В | Путь ],
 ( после( В, В1),
   not принадлежит( В1, [В | Путь]) ),
   Нов ),
 конк( Нов, ZZ, Z), !,
 вширь( Пути-ZZ, Решение);
 Пути == Z, % Множество кандидатов не пусто
 вширь( Пути-Z, Решение).

Рис. 11.11. Программа поиска в ширину более эффективная, чем программа рис. 11.10. Усовершенствование основано на разностном представлении списка путей-кандидатов.

В случае примера рис.11.9 этот процесс будет развиваться следующим образом:

(1) Начинаем с начального множества кандидатов:

[ [а] ]

(2) Порождаем продолжения пути [а]:

[ [b, а], [с, а] ]

(Обратите внимание, что пути записаны в обратном порядке.)

(3) Удаляем первый путь из множества кандидатов и порождаем его продолжения:

[ [d, b, a], [e, b, а] ]

Добавляем список продолжений в конец списка кандидатов:

[ [с, а], [d, b, a], [e, b, а] ]

(4) Удаляем [с, а], а затем добавляем все его продолжения в конец множества кандидатов. Получаем:

[ [d, b, a], [e, b, а], [f, c, a], [g, c, a] ]

Далее, после того, как пути [d, b, a] и [e, b, а] будут продолжены, измененный список кандидатов примет вид

[[f, c, a], [g, c, a], [h, d, b, a], [i, e, b, a], [j, e, b, a]]

В этот момент обнаруживается путь [f, c, a], содержащий целевую вершину f. Этот путь выдается в качестве решения.

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

Недостатком этой программы является неэффективность операции конк. Положение можно исправить, применив разностное представление списков (см. гл. 8). Тогда множество путей- кандидатов будет представлено парой списков Пути и Z, записанной в виде

Пути-Z

При введении этого представления в программу рис. 11.10 ее можно постепенно преобразовать в программу, показанную на рис. 11.11. Оставим это преобразование читателю в качестве упражнения.

11.3.2. Древовидное представление множества кандидатов

Рассмотрим теперь еще одно изменение нашей программы поиска в ширину. До сих пор мы представляли множества путей-кандидатов как списки путей. Это расточительный способ, поскольку начальные участки путей являются общими для нескольких из них. Таким образом, эти общие части путей