Неизвестно - Prolog

вширь( Пути-Z, Решение).

Рис. 11. 11. Программа поиска в ширину более эффективная, чем

программа рис.11.10. Усовершенствование основано на разностном

представлении списка путей-кандидатов.

(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. Древовидное представление множества кандидатов

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

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

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

д( В, Пд)

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

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

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

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

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

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

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

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

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

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