5.1.1. АЛГОРИТМЫ А И А*

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

Применение произвольного оператора к некоторому выделенному состоянию («родительскому” состоянию) представляется в виде дуги, направленной от этого родительского состояния к вершине — потомку, называемой «дочерним” состоянием. Каждой дуге приписывается некоторая стоимость,

характеризуемая положительным числом. Цель поиска заключается в построении пути между начальным состоянием и одним из конечных состояний, имеющего минимальную стоимость, причем стоимость пути рассчитывается как сумма стоимостей составляющих его дуг. Методология поиска состоит в последовательном спуске по дереву от начального состояния до тех пор, пока не будет достигнуто некоторое конечное состояние Граф, соответствующий заданному этапу поиска, называется графом поиска Когда не удается достичь конечного состояния в графе поиска, возникает задача выбора некоторого состояния, на которое будут действовать операторы с целью порождения новых состояний ("раскрытие” состояния). Этот выбор направляется оценочной функцией, которая каждому способному к раскрытию состоянию ставит в соответствие положительное число определяемое в виде суммы

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

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

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

В более общем случае если не обеспечивается существование такой нижней оценки алгоритм имеет всего лишь тип А (а не А и выполняются только свойства а) и б). При использовании ряда дополнительных предположений эти свойства сохраняются и для бесконечных графов поиска [3]. Далее описывается пример использования алгоритма типа А в так называемой задаче о коммивояжере. Затем он адаптируется к случаям, когда стоимости дуг известны лишь приближенно в виде обычных или нечетких интервалов