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

Монотонное ограничение h-функции

Поиск в ширину «разворачивает» наше пространство состояний в дерево. Так как запись просмотренных вершин не ведется, то одна и та же вершина может попасть в разные ветви, причем g1(u)≠g2(u). С помощью очень небольшого и вполне разумного ограничения на функцию h можно добиться, что автоматически при выборе вершины для продолжения будет находиться минимальный путь к ней, т.е. минимальное g(u).

Опр. 4. Эвристическая функция h удовлетворяет монотонному ограничению, если всех вершин u_i и u_i таких, что u_i является отцом u_j на дереве поиска

h(u_i)-h(u_j)≤c(u_i,u_j),

где c(u_i,u_j) — стоимость перехода из состояния u_i в состояния u_j и для любой целевой вершины h(t)≡0.

Теорема 3.

Если эвристические функция h удовлетворяет монотонному ограничению, то A* -алгоритм, выбирая вершину для продолжения, автоматически обнаруживает минимальный путь к ней, то есть g*(u)=g(u).

Контрольные вопросы к пп. 1.1–1.4.

1. Что такое пространство состояний? Каковы основные типы стратегий управления поиском в пространстве состояний?

2. Перечислите основные стратегии неинформированного поиска в пространстве состояний. Какова их вычислительная сложность?

3. В чем состоит основное отличие эвристического поиска от всех видов неинформированного поиска?

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

5. В чем заключается отличие между «малыми» и «большими» эвристиками? Как выбор эвристики влияет на количество вершин пространства состояний, просмотренных во время поиска?

1.5. Программная реализация эвристического поиска. Игра в «8»

Мы знаем, как подсчитать 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).

Дата добавления: 2015-06-27