5.6. Алгоритм А*

Всякой ситуации полученной из исходной ситуации в результате определенной последовательности действий, придается численная оценка

где — реальная текущая стоимость ситуации — эвристическая функция, которая оценивает стоимость наилучщей

последовательности действий, начинающейся с S и заканчивающейся решением. Следовательно, является мерой стоимости решений, «подчиненных» ситуации т. е. решений, включающих то же подмножество исходных действий, что и S. Так, например, когда каждому действию соответствует элементарная стоимость представляющая собой стоимость Перехода из с помощью действия а, подсчитать функцию очень просто: она равна сумме стоимостей действий, кото надо выполнить, чтобы дойти до данной точки от исходной ситуации Так как стоимости предполагаются положительными, функция будет строго аддитивной.

Алгоритм А

(см. скан)

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

Следовательно, функция является оценочной для оптимальной функции определяемой выражением

где - наилучшая стоимость решений, проходящих через - наилучшая стоимость пути от до -наилучшая стоимость пути от до цели.

Теорема. Алгоритм А приводит к цели за конечное число шагов, если существует конечная последовательность действий, которая ведет от исходной ситуации к решению.

Доказательство. Сначала заметим, что если число возможных действий для каждой ситуации всегда конечно и число самих ситуаций тоже конечно, то алгоритм А заведомо сходится. В самом деле, ведь каждая итерация вычеркивает из множества О одну вершину и добавляет в него некоторое конечное число новых; при этом поисковый граф останется конечным, и его проверка потребует лишь конечного числа итераций.

Итак, допустим, что поисковый граф бесконечен и условия нашей теоремы выполняются. Будем рассуждать от противного и предположим, что алгоритм А работает неограниченно долго. Это возможно только при условии, что само множество О возрастает бесконечно. Покажем, что в этом случае наименьшее из значений также оказалось бы бесконечным и тогда, следовательно, не могло бы существовать решения за конечное число шагов. Пусть для всякой ситуации — минимальное число действий, необходимых для того, чтобы попасть из в 5 (алгоритм А не обязательно достигает стоимости и поэтому она остается неизвестной). Несмотря на это, поскольку любая дуга имеет строго положительную стоимость, для оптимальной стоимости мы получаем

Тем самым реальное значение вычисляемое алгоритмом А, удовлетворяет неравенству

Поскольку эвристическая функция из этого также вытекает, что

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

Докажем теперь, что на каждом этапе работы алгоритма вплоть до его остановки в множестве О обязательно присутствует вершина такая, что

Пусть существует конечная последовательность действий и ситуаций, ведущая от к цели. Тогда первая из входящих в эту последовательность ситуаций, которая принадлежит также множеству О. Такая вершина существует до тех пор, пока алгоритм А не завершит работу. Как и для любой другой ситуации, но здесь (так как по определению все предыдущие ситуации принадлежат Кроме того, по построению алгоритма А выполняется неравенство ? В конце концов мы получаем

В частности, если исходная последовательность была оптимальной, то

Итак, предположение о бесконечности и тем самым о бесконечности работы алгоритма А оказалось противоречивым (при условии, что существует решение с конечным расстоянием даже для локально бесконечных графов). Кроме того, найденное решение обладает оптимальной стоимостью. Если бы алгоритм А остановился в узле для которого то в соответствии с приведенным выше доказательством получилось бы, что существует узел такой, что , следовательно, на этапе 1 был бы выбран не узел а узел . В самом деле, любой узел полученный в результате работы алгоритма А, имеет стоимость которая не превышает поскольку в противном случае либо был бы узлом-решением, либо не был бы выбран.

Конечно, значения функции должны быть как можно ближе к значениям оставаясь при этом меньше их. Алгоритм будет тем эффективнее, чем больше значение Действительно, легко доказать, что если то любая вершина, полученная с помощью функции может быть получена

и с помощью Если функция обладает свойством монотонности по отношению к локальным стоимостям, т. е. если

мы можем доказать, что для каждой полученной вершины алгоритм А уже построил оптимальную последовательность, заканчивающуюся в этой вершине.

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

Последний случай является вариантом алгоритма Моора— Дейкстры (1957) поиска кратчайшего пути на графе (разд. 4.2). Несомненно, большим недостатком этого алгоритма является его поведение при отсутствии решения поставленной задачи.

Пример применения алгоритма А*

Рассмотрим знаменитую головоломку, которую изобрел гениальный Сэм Лойд, — игру в 8.

На -клеточном поле перейти от конфигурации

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

Выберем в качестве оценочных функций: - число ходов от до число фишек, расположенных не на своих местах.

Итак, мы имеем

1) (по построению g),

2) (по условию задачи).

Монотонность ничем не гарантирована. На рис. 5.7 представлено поисковое дерево, полученное с помощью алгоритма А, причем справа от каждой ситуации приводится пара значений —

Было предложено несколько вариантов этого алгоритма. Так, наиболее общая форма функции была определена в работе (Pohl, 1970):

где — действительная константа, выбираемая на отрезке от 0 до 1. Таким образом здесь указывается определенный баланс

Рис. 5.7. Алгоритм А для игры в 8: дерево поиска.

в оценке между бесспорной составляющей и составляющей эвристической Алгоритму А соответствует значение а Случай - чисто градиентный метод. Другой крайний случай — — ведет к методу полного перебора.

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

Критические замечания. Алгоритм А, как и другие градиентные алгоритмы, рассмотренные в данной главе, является строго численным, поэтому исключается формальный анализ каждой ситуации. Алгоритм основан на оценке стоимости некоторого решения. Но существует большое число задач, для которых эта оценка не имеет смысла, потому что, например, в них необходимо найти единственное осуществимое решение. Он не

дает способа подсчета интеграла, решения системы уравнений или установления медицинского диагноза. Нельзя заранее обнаружить тупики и петли. Так, если в игре в 8 (рис. 5.7) заменить верхний ряд исходной ситуации на (8 2 3), то чтобы доказать, что эта задача не имеет решения, алгоритм А должен будет исследовать абсолютно все возможные случаи и поэтому оказывается бесполезным. Следовательно, рассматриваемый тип алгоритма может использоваться только при решении задач, возникающих в малоизвестных пространствах, т. е. там, где мало информации (плохое знание контекста, недостаток опыта, отсутствие формальных аргументов).

Задача о взвешивании

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

Эта задача довольно известна, но нас сейчас интересует, каким именно образом приступить к ее решению. Конечно, мы можем сравнивать шарики на весах попарно. Поскольку от других отличается не более чем один шарик, мы может быть уверены в том, что получим ответ не более чем за 12 взвешиваний (11 сравнений шарика № 1 со всеми остальными определение характера различия). Если, наоборот, мы решим начать со взвешивания “шесть против шести”, то мы, очевидно, ничего не узнаем. Таким образом, первый вопрос, который возникает в данной ситуации, как определить число шариков в каждой чашке весрв при первом взвешивании (естественно, рассматриваются только взвешивания равного числа шариков).

Ответ на этот вопрос можно получить, определив оценочную функцию и ее градиент. Каждое взвешивание должно увеличивать имеющуюся информацию о множестве шариков. Следовательно, речь идет о том, чтобы сделать как можно меньшим математическое ожидание числа неизвестных шариков (здесь имеется в виду вероятностное ожидание, так как до последнего шага мы ни в чем не уверены). Итак, если мы начинаем с 6 шариков на каждой чашке, то коромысло либо покажет равенство (и тогда останется (12 — 26) шариков с неизвестным весом), либо наклонится в одну сторону (и тогда (12 — 26) шариков обязательно имеют стандартный вес, а из взвешенных шариков шариков являются более легкими либо более тяжелыми, причем эти два случая, разумеется, исключают друг друга). Допустим, что 6 шариков обладают неизвестным весом.

В качестве оценочной функции вычисляющей, насколько выгодно начать взвешивание с шариков, естественно выбрать в каждом случае число шариков неизвестного веса, умноженное на вероятность появления этого случая. Поскольку существует способов выбора объектов из вероятность получить равенство составляет так как для этого мы должны были бы оставить нестандартный шарик, а выборку производить из оставшихся 11 шариков. Вероятность отклонения коромысла в ту или иную сторону является дополнительной к 1 по сравнению с предыдущей. Так как оценочная функция имеет вид

Минимум функции можно получить путем дифференцирования, так как следовательно, должно удовлетворять уравнению (в общем случае, если имеется шариков,

Конечно, данное значение лишь указывает на наилучший путь к решению, не использующий интуицию. Следуя по нему, легко получить решение за три взвешивания. Интересно, что эти взвешивания можно задать заранее независимо от результатов каждого из них. Обозначив шарики буквами от А до мы получаем, например, следующую схему:

Она позволяет различать возможности.

В самом деле, легко доказать, что 3 является минимальным числом взвешиваний. Поскольку в результате каждого взвешивания возникают три возможности, два взвешивания позволяют различить только случаев, а этого недостаточно. Следовательно, метод градиента привел здесь к оптимуму.