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

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. Оставим это преобразование читателю в качестве упражнения.

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

Случай 1: Дерево состоит только из одной вершины В; В этом случае оно имеет вид терма л( В); Функтор луказывает на то, что В — это лист дерева.

Случай 2: Дерево состоит из корневой вершины В и множества поддеревьев Д1, Д2, …. Такое дерево представляется термом

д( В, Пд)

где Пд — список поддеревьев:

Пд = [ Д1, Д2, ...]

В качестве примера рассмотрим ситуацию, которая возникает после того, как порождены три уровня дерева рис. 11.9. Множество путей-кандидатов в случае спискового представления имеет вид:

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

В виде дерева это множество выглядит так:

д( а, [д( b, [л( d), л( e)] ), д( с, [л( f), л( g)] )] )

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

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

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

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

Рис. 11.12. Отношение paсширить( Путь, Дер, Дер1, ЕстьРеш, Решение): s — стартовая вершина, g — целевая вершина. Решение — это Путь, продолженный вплоть до g. Дер1 — результат расширения дерева Дерна один уровень вниз.

Итак, процедура расширитьбудет порождать два типа результатов. На конкретный вид результата будет указывать значение переменной ЕстьРеш:

(1) ЕстьРеш= да

Решение= решающий путь, т.е. Путь, продолженный до целевой вершины.

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

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

(2) ЕстьРеш= нет

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

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

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

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

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

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