Построение эвристической

Мы будем в дальнейшем предполагать, что для дуг пространства состояний определена функция стоимости с(n, n')  - стоимость перехода из вершины n  к вершине-преемнику n'.

Пусть f  - это эвристическая оценочная функция, при помощи которой мы получаем для каждой вершины n  оценку f( n)   "трудности" этой вершины. Тогда наиболее перспективной вершиной-кандидатом следует считать вершину, для которой  f   принимает минимальное значение. Мы будем использовать здесь функцию  f   специального вида, приводящую к хорошо известному А*-алгоритму. Функция  f( n)   будет построена таким образом, чтобы давать оценку стоимости оптимального решающего пути из стартовой вершины  s  к одной из целевых вершин при условии, что этот путь проходит через вершину  n.  Давайте предположим, что такой путь существует и что  t  -  это целевая вершина, для которой этот путь минимален. Тогда оценку  f( n) можно представить в виде суммы из двух слагаемых (Рисунок 12.1):

        f( n) = g( n) + h( n)

Здесь  g( n)  - оценка оптимального пути из  s  в  n;  h( n) -  оценка оптимального пути из  n  в  t.

Когда в процессе поиска мы попадаем в вершину   n,  мы оказываемся в следующей ситуация: путь из  s  в  n  уже найден, и его стоимость может быть вычислена как сумма стоимостей составляющих его дуг. Этот путь не обязательно оптимален (возможно, существует более дешевый, еще не найденный путь из  s   в  n),  однако стоимость этого пути можно использовать в качестве оценки  g(n)   минимальной стоимости пути из  s  в   n.  Что же касается второго слагаемого   h(n),  то о нем трудно что-либо сказать, поскольку к этому моменту область пространства состояний, лежащая между  n  и  t,   еще не "изучена" программой поиска. Поэтому, как правило, о значении  h(n)   можно только строить догадки на основании эвристических соображений, т.е. на основании тех знаний о конкретной задаче, которыми обладает алгоритм. Поскольку значение  h   зависит от предметной области, универсального метода для его вычисления не существует. Конкретные примеры того, как строят эти "эвристические догадки", мы приведем позже. Сейчас же будем считать, что тем или иным способом функция  h  задана, и сосредоточим свое внимание на деталях нашей программы поиска с предпочтением.

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