Точно Не проект 2 / Не books / Источник_1

ции hˆ(n). Отличие состоит в том, что на каждом этапе выполняется не локальное сравнение вершин, полученных при раскрытии текущей вершины, а глобальное сравнение всех вершин-кандидатов, находящихся в списке OPEN. Для этого список открытых вершин сортируется в порядке возраста-

ния значений hˆ(n). Наилучшая вершина для продолжения пути будет находиться на первом месте в списке OPEN. Поэтому данный алгоритм называют также алгоритмом выбора первой наилучшей вершины (Best-First).

Рисунок 2.7 – Графы состояний

Процедура поиска, основанная на данном алгоритме, похожа на процедуру Optimal_Search. Отличие состоит в том, что вместо функции стоимо-

сти gˆ(n) применяется эвристическая функция hˆ(n), т.е. учитываются только предстоящие затраты:

Procedure Best_First_Search; Begin

Поместить начальную вершину в OPEN; CLOSED:=‘пустой список’;

While OPEN<>‘пустой список’ Do Begin

n:=first(OPEN);

If n=‘целевая вершина’ Then Выход(УСПЕХ);

Переместить вершину n из списка OPEN в список CLOSED; Раскрыть вершину n, для каждой дочерней вершины вычислить hˆ(ni );

Поместить дочерние вершины, которых нет в списках OPEN и CLOSED, в список OPEN, связав с каждой дочерней вершиной ука-

затель на вершину n;

Упорядочить список OPEN по возрастанию значений hˆ(n)

End;

Выход(НЕУДАЧА); End.

While OPEN<>‘пустой список’ Do Begin

n:=first(OPEN);

If n=‘целевая вершина’ Then Выход(УСПЕХ);

Переместить n из OPEN в CLOSED;

Раскрыть n и для всех ее дочерних вершин ni вычислить оценку

fˆ (n, ni ) gˆ (n, ni ) hˆ(ni ) ;

Поместить дочерние вершины, которых нет в списках OPEN и

CLOSED, в список OPEN, связав с каждой вершиной указатель на вершину n;

Для дочерних вершин ni , которые уже содержатся в OPEN, срав-

нить оценки fˆ(n,ni ) и fˆ(ni ), если fˆ(n,ni )< fˆ(ni ), то связать с вер-

шиной ni новую оценку fˆ(n,ni ) и указатель на вершину n;

Если вершина ni содержится в списке CLOSED и fˆ(n,ni)< fˆ(ni ) , то

связать с вершиной n i новую оценку fˆ(n,ni ), переместить её в список OPEN и установить указатель на n;

Упорядочить список OPEN по возрастанию fˆ(ni );

End;

Выход(НЕУДАЧА); End.

Укажем свойства А-алгоритма. Если для всех вершин hˆ(n)=0, то А- алгоритм будет соответствовать алгоритму равных цен. В этом случае гарантируется нахождения оптимального пути, но эффективность поиска будет низкой, и если пространство поиска будет бесконечно, то поиск просто не осуществим.

А-алгоритм не даёт гарантии, что найденный путь будет оптимальным. Путь может быть не оптимальным в случае, если оценка затрат на пути из вершины n в целевую вершину будет преувеличена (переоценена),

т.е. если hˆ(n)>h(n). Сказанное можно пояснить с помощью рисунка 2.8.

(4)

2 A 5

(6)

Рисунок 2.8 – Граф состояний с переоценкой затрат h(n)

Таблица 2.1—Выполнение А*-алгоритма

Чтобы А*-алгоритм не раскрывал несколько раз одну и ту же вершину, необходимо учитывать условие монотонности

где ni – родительская вершина; nj – дочерняя вершина; c(ni, nj ) – стоимость пути между вершинами ni и nj.

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

функция fˆ(n) для данной вершины в дальнейшем не меняет своих значений, и никакие вершины из списка CLOSED в список OPEN не возвращаются.

Ранее отмечалось, что А*-алгоритм недооценивает затраты h(n). Условие монотонности означает, что недооценка на пути к цели становится все меньше или, в крайнем случае, не изменяется. Действительно, если

Из условия монотонности следует, что uˆ(nj) uˆ(ni), т.е. недооценка

h(n) в родительских вершинах больше или равна недооценкам h(n) в дочерних вершинах. На графе, изображенном на рисунке 2.9, условие монотонности не выполняется для начальной вершины. Например, h(S)> h(D)+ c(S,D), т.е. 14>10+1.

Если hˆ(n)=h(n), то информированность является полной. В этом случае никакого поиска не происходит и приближение к цели идет по оптимальному пути.

Таким образом, свойства А-алгоритма существенно зависят от условий, которым удовлетворяет или не удовлетворяет эвристическая часть

оценочной функции fˆ(n):

1)А-алгоритм соответствует алгоритму равных цен, если h(n)=0;

2)А-алгоритм гарантирует оптимальное решение, если hˆ(n) h(n); в этом случае он называется А* – алгоритмом;

3)А-алгоритм обеспечивает однократное раскрытие вершин, если

выполняется условие монотонности hˆ(ni ) hˆ(nj ) c(ni ,nj ) ;

4)алгоритм А1* эвристически более сильный, чем алгоритм А2*

при hˆ1(n) hˆ2(n);

5)А*-алгоритм полностью информирован, если hˆ(n)=h(n);

6)при hˆ(n)>h(n) А-алгоритм не гарантирует получение оптималь-

ного решения, однако часто решение получается быстро. Рассмотренные алгоритмы поиска в пространстве состояний можно

систематизировать с помощью таблицы 2.2.

Таблица 2.2 – Алгоритмы поиска в пространстве состояний

Поиск решений в пространстве состояний может выполняться в нескольких направлениях: из начального состояния в целевое состояние (поиск, управляемый данными); из целевого состояния в начальное состояние (поиск, управляемый целью, или обратный поиск); одновременно в двух направлениях (комбинированный поиск). Так как поисковые графы (деревья) для практических задач велики, то двунаправленный поиск может быть

эффективнее однонаправленного [35].

Поиск решений в пространстве состояний – комбинаторная задача. Решение получается на основе перебора всех состояний. Однако для многих практических задач полный перебор невозможен. Были предложены различные меры для оценки сложности решаемой задачи. Одна из них – это степень разветвления вершин графа состояния. Она равна среднему числу дочерних вершин, приходящихся на одно состояние задачи. Если рассматривать дерево состояний, то можно вывести формулу, устанавливающую зависимость общего числа состояний N от степени разветвления B и глубины дерева L [77]:

N B(BL 1)/(B 1).

Пусть, например, необходимо подсчитать общее число состояний для игры-головоломки “8”.Укажем возможные перемещения фишек:

-по два перемещения из каждого угла, т.е. для четырех углов восемь перемещений;

-по три перемещения из центральных позиций вдоль каждой из сторон, т.е. всего двенадцать перемещений;

-четыре перемещения из центральной позиции.

Общее число возможных перемещений 24. Разделив это число на 9 (число различных положений для пустой ячейки), получим степень разветвления 2,67. Теперь можно определить общее число состояний при просмотре дерева состояний глубины L (таблица 2.3).

Таблица 2.3 – Число состояний при игре “в восемь”

Как видно из таблицы 2.2, даже для такой простой задачи количество просматриваемых состояний резко возрастает при увеличении глубины поиска.

Сложность решаемой задачи можно также оценивать размерами списков OPEN и CLOSED. Для того чтобы эти списки не разрастались, можно сохранять в списке OPEN только несколько наиболее “перспективных” состояний. Это, конечно, сокращает пространство поиска, но возникает опасность пропуска решения. Такие стратегии поиска, накладывающие ограничения на размер списка OPEN, соответствуют лучевому поиску (beam search). Более безопасны стратегии эвристического поиска, рассмотренные выше. Чем больше информированность о решаемой задаче, тем больший вес имеет эвристическая часть оценочной функции и тем больше сокращается пространство поиска. Следует обратить внимание на то, что вычисление

Пусть для каждого из элементов ni {n1,n2,...,nm} имеется конечное множество интерпретации (меток) Li мощностью Gi. Возможность или невозможность согласованной интерпретации двух элементов ni и nj с помощью меток li L i и l j L j задается бинарным отношением bij. Если

определенная метка li для элемента ni не согласуется с соответствующей меткой lj для элемента nj (т.е. не удовлетворяет отношению bij), то данная метка удаляется из множества Li. Аналогичным образом исследуются все метки, входящие во множество Lj. В ходе указанного процесса с каждой вершиной графа связывается метка (или множество меток). При этом метки на концах ребер графа должны удовлетворять заданным отношениям.

Рассмотрим пример согласованной разметки вершин графа, изображенного на рисунке 2.10 [86]. Около вершин графа указаны множества возможных меток, а ограничения, которым должны удовлетворять соответствующие метки, записаны рядом с ребрами. Основная идея состоит в сужении множества возможных меток для каждой из вершин, опираясь на заданные ограничения.

Рисунок 2.10 – Согласованная разметка узлов графа

Рассмотрим множества совместимых меток для вершин n1 и n2 при ограничении l1+l2=8. Сначала при заданном множестве L1={1,3,4,5,6} удалим из L2 все метки, не удовлетворяющие указанному условию. В данном случае отношение b12 выполняется для всех меток из L2, за исключением метки 6. Следовательно, данная метка удаляется, и L2={3,4,5,7}. Затем отношение b12 используется для проверки множества меток L1. В этом случае из L1 также удаляется метка 6, и множество L1 будет состоять из меток {1,3,4,5}. Таким образом, мы сначала распространили ограничение b12 из вершины n1 в вершину n2, а затем обратно из n2 в n1, удаляя соответствующие метки из множеств L2 и L1. Метки, входящие во множества L2 и L1, теперь согласованы.

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