д( В, Пд)
где Пд - список поддеревьев:
Пд = [ Д1, Д2, ...]
В качестве примера рассмотрим ситуацию, которая возникает после того, как порождены три уровня дерева рис. 11.9. Множество путей-кандидатов в случае спискового представления имеет вид:
[ [d, b, a], [e, b, а], [f, c, a], [g, c, a] ]
В виде дерева это множество выглядит так:
д( а, [д( b, [л( d), л( е)] ), д( с, [л( f), л( g)] )] )
На первый взгляд древовидное представление кажется еще более расточительным, чем списковое, однако это всего лишь поверхностное впечатление, связанное с компактностью прологовской нотации для списков.
В случае спискового представления множества кандидатов эффект распространения процесса в ширину достигался за счет перемещения продолженных путей в конец списка. В нашем случае мы уже не можем использовать этот прием, поэтому программа несколько усложняется. Ключевую роль в нашей программе будет играть отношение
расширить( Путь, Дер, Дер1, ЕстьРеш, Решение)
На рис. 11.12 показано, как связаны между собой аргументы отношения расширить. При каждом обращении к расширить переменные Путь и Дер будут уже конкретизированы. Дер - поддерево всего дерева поиска, одновременно оно служит для представления множества путей-кандидатов внутри этого поддерева. Путь - это путь, ведущий из стартовой вершины в корень поддерева Дер. Самая общая идея алгоритма -
Рис. 11. 12. Отношение paсширить( Путь, Дер, Дер1, ЕстьРеш, Решение):
s - стартовая вершина, g - целевая вершина. Решение - это Путь,
продолженный вплоть до g. Дер1 - результат расширения дерева
Дер на один уровень вниз.
получить поддерево Дер1 как результат расширения Дер на один уровень. Но в случае, когда в процессе расширения поддерева Дер встретится целевая вершина, процедура расширить должна сформировать соответствующий решающий путь.
Итак, процедура расширить будет порождать два типа результатов. На конкретный вид результата будет указывать значение переменной ЕстьРеш:
(1) ЕстьРеш = да
Решение = решающий путь, т. е. Путь, продолженный до целевой вершины.
Дер1 = неконкретизировано.
Разумеется, такой тип результата получится только в том случае, когда Дер будет содержать целевую вершину. Добавим также, что эта целевая вершина обязана быть листом поддерева Дер.
(2) ЕстьРеш = нет
Дер1 = результат расширения поддерева Дер на один уровень вниз от своего 'подножья'. Дер1 не содержит ни одной 'тупиковой' ветви из Дер, т. е. такой ветви, что она либо не может быть продолжена из-за отсутствия преемников, либо любое ее продолжение приводит к циклу.
Решение = неконкретизировано.
