Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Эвристическая оценочная функция для И-ИЛИ графовПрипишем дугам И-ИЛИ графа стоимости. Положим стоимость решающего дерева равной стоимости входящих в него дуг. Цель оптимизации — поиск дерева решения минимальной стоимости. Определим стоимость вершины как стоимость минимального решающего дерева с корнем в этой вершине. Определим эвристическую функцию на вершинах И-ИЛИ графа. Эвристическая оценка листов равна непосредственно значению эвристики h(u) на вершине u. Внутренние вершины имеют преемников. Они будут оцениваться с помощью возвращенной эвристической оценки — оценки стоимости минимального решающего дерева с корнем в u. — оценка для ИЛИ-вершины (рис. 20). Рисунок 20. Возвращенная эвристика «ИЛИ»-вершины — оценка для И-вершины (рис. 21). Рисунок 21. Возвращенная эвристика «И»-вершины 3) — оценка для листа В нашем дереве поиска у каждой вершины только один отец. Пусть u0 — отец, u — сын (рис.22). Рисунок 22. f-оценка сына u1 с отцом u0 f-оценка вершины u складывается как стоимость дуги, входящей в u от родительской вершины, плюс ее возвращенная эвристическая оценка . Начальная вершина не имеет родителя, поэтому будем считать, что в нее входит фиктивная дуга стоимости 0. 1.8.2. АО*-алгоритм эвристического поиска на И-ИЛИ графе Каждый преемник ИЛИ-вершины соответствует альтернативному дереву — кандидату в решение. АО*-алгоритм на каждом шаге будет расширять дерево с минимальной f-оценкой, вычисленной следующим образом: — для И-вершины; — для ИЛИ-вершины. Рассмотрим эвристический поиск на примере модельного И-ИЛИ графа (рис. 23) с эвристиками всех вершин тождественно равными 0 (h(u)≡0 для всех u). Рисунок 23. Модельный граф с эвристиками всех вершин тождественно равными нулю Начнем поиск из начальной вершины а. f(a) = 0 + h(a) = 0 (рис. 24): Рисунок 24. Трассировка алгоритма. Шаг 1 Далее находим всех преемников а, вычисляем их f –оценки и пересчитываем f — оценку а (рис. 25): f(b) = 1 + h(b) =1; f(c) = 3 + h(c) = 3; f(a) = 0 + min{f(b),f(c)} = min{1,3} = 1. Рисунок 25. Трассировка алгоритма. Шаг 2 Дерево с корнем в b является минимальным, поэтому оно расширяется (рис. 26), его оценка пересчитывается и пересчитывается оценка вершины а: f(d) = 1 + h(d) =1; f(e) = 1 + h(e) =1; f(b) = 1 + f(d) + f(e) =3. Рисунок 26. Трассировка алгоритма. Шаг 3 f(b) ≤ f(c), поэтому продолжаем расширять дерево с корнем в b. При попытке расширить d обнаруживаем что d — целевая вершина, для e находим преемника h (рис. 27): f(h) = 6 + h(h) =6; f(e) = 1 + h(h) =1 + 6 =7; f(b) = 1 + f(d) + f(e) = 1 + 1 + 7 = 9 Рисунок 27. Трассировка алгоритма. Шаг 4 Поиск не успел понять, что h — целевая вершина; стоимость дерева с корнем в b равна 9, поэтому происходит переключение на дерево с корнем в с, причем рост дерева с корнем в с ограничивается величиной 9: f(c) ≤ 9 (рис. 28): f(f) = 2 + h(f) =2; f(g) = 1 + h(g) =1; f(c) = 3 + f(f) +f(g) = 3 + 2 + 1 =6; Рисунок 28. Трассировка алгоритма. Шаг 5 f(b) ≤ 9, поэтому продолжаем расширять дерево с корнем в с (рис. 29). Обнаруживаем, что g — целевая вершина и для f находим двух преемников: f(h) = 2 + h(h) = 2; f(i) = 3 + h(i) = 3; f(f) = 2 +min {2,3} = 4; f(c) = 3 + f(f) + f(g) = 8 f(a) = 0 + f(c) = 8. Рисунок 29. Трассировка алгоритма. Шаг 6 Штриховой линией обведено активное дерево поиска. Заметим, что вершина h включена в разные деревья поиска и имеет разные f оценки: 6 и 2. f(c)≤8≤9, поэтому продолжаем расширять дерево с корнем в c. При попытке расширить h обнаруживаем целевую вершину и получаем дерево решения. Так как все h(u) ≡ 0, то оценка вершины а — f(a) есть стоимость дерева решения. 1.8.3. Некоторые свойства АО*-алгоритма Обозначим стоимость минимального дерева решения, связывающего вершину u с терминальными вершинами. Если для всех u, то эвристический поиск построит минимальное дерево решения. Это условие для эвристики h можно заменить другим — условием монотонности эвристики h. Пусть у вершины u имеется несколько связок, одна связка состоит из k потомков u1,…, uk. Если для каждой связки имеет место неравенство где с(u,ui) — стоимость дуги от вершины u до потомка ui, h(ui) — эвристика вершины ui, и для каждой терминальной вершины t h(t)≡0. Это условие аналогично условию монотонности для обычного графа пространства состояний: т.е. эвристики вершин не меняются резко и согласованы со стоимостью дуг.
|