F-оценки поддеревьев

Мы знаем, как подсчитать f-оценку листа l(x):

f(X) = g(X) + h(X), где

g(X) — стоимость пути от стартовой вершины до вершины X, h(X) — эвристика вершины X.

Рассмотрим теперь f-оценки на деревья, имеющие корень и список поддеревьев.

Пусть дерево T имеет корень Х и список поддеревьев DD=[D₁,D₂,...,D_k] (рис. 8):

Рисунок 8. Дерево с корнем и списком поддеревьев

Вычислим оценки его поддеревьев D_i, i=1..k и выберем минимальную. Таким образом, f-оценка дерева совпадает с f-оценкой его минимального поддерева. Оценки поддеревьев в свою очередь определяются как минимальные из f-оценок их поддеревьев.

Так мы опускаемся до минимального листа.

ДЕРЕВУ Т ПРИПИСЫВАЕТСЯ ОЦЕНКА ЕГО МИНИМАЛЬНОГО ЛИСТА.

КОРНЮ ДЕРЕВА Т ВЕРШИНЕ Х ПРИПИСЫВАЕТСЯ ОЦЕНКА ДЕРЕВА Т.

f(X)=f(T)=min_i=1..k {f(D_i)},

где D_i — поддеревья дерева Т.

Такая оценка для вершины, являющейся корнем дерева, в отличие от оценки вершины-листа называется уточненной.

Определим теперь структуру для хранения дерева вместе с его f-оценкой.

Тип листа: l(тип_сост, est), где

est = e(integer, integer).

Например, для листа, состоящего из вершины Х:

l(X,e(F,G)), где F=f(X) и G=g(X).

(Напомним, что f(X) — оценка листа, g(X) — длинна пути от стартовой вершины до вершины X.)

Тип дерева: t(тип_сост, est, tlist), где

est = e(integer, integer) — структура для хранения f и g-оценок корня дерева Х;

tlist — список поддеревьев.

Например, для дерева D с корнем Х и списком поддеревьев DD:

t(X,e(F,G),DD), где

F=f(X) и G=g(X).

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

son = s(тип_сост., integer).