3.9. Важная роль функции ĝ

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

Интуитивное соображение против включения функции ĝ в оценочную функцию

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

Интуитивное соображение за включение функции ĝ в оценочную функцию

Даже в том случае, когда не существенно, чтобы найденный путь имел минимальную стоимость, функцию ĝ следует вклю­чить в ĵ для того, чтобы быть уверенным, что хотя бы какой-нибудь путь будет в конечном итоге найден. Такой уверенностью необходимо заручаться всегда, когда ĥ не достаточно хорошая оценка для h, поскольку, если всегда раскрываются вершины с минимальным ĥ, то может случиться так, что в нашем процессе перебора будут все время раскрываться ложные вершины, а целевая вершина достигаться не будет. Включение функции ĝ как бы вносит определенную компоненту полного перебора и га­рантирует, что нет такой части у графа, которую процесс пере­бора постоянно обходит.

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

Рассмотрим случай бесконечного графа в форме бесконеч­ного m-арного дерева. (Бесконечное m-арное дерево - это де­рево, в котором у каждой вершины имеются в точности m непосредственно следующих за ней вершин.) В этом графе имеется единственная целевая вершина, которая расположена на k-м уровне. Заметим, что цель достижима из любой вершины этого конкретного графа. Пример такого графа приведен на рис. 3.9, стоимости ребер предполагаются единичными.

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

ĥ(n) = h(n) + E для вершин n на кратчайшем пути,

ĥ (n) = h(n) - Е для вершин n вне кратчайшего пути,

где Е— некоторая целочисленная ошибка. То есть наша функция ĥ всегда содержит ошибку, величина которой равна некоторому целому Е (в этом случае ĥ не дает нижней границы для h).

Кроме того, знак этой ошибки выбран так, чтобы вызвать наибольшие затруднения. Проанализировав самый худший случай мы покажем, что при такой функции ĥ перебор с функцией ĵ=ĝ + ĥ более эффективен, чем перебор с функцией ĵ = ĥ, если только Е > 1.

Мы должны сопоставить следующие два случая:

Случай 1. ĵ = ĝ + ĥ. Пусть N_g+h — число вершин, которые были раскрыты до достижения цели. Здесь мы обязаны раскрывать вершину, если она расположена в пределах Е единиц от какой-либо вершины на кратчайшем пути. (В духе рассматриваемого нами самого худшего случая мы всегда будем выбирать наихудшую из возможностей, если число вершин равно Е.) Видно тогда, что

N_g+h=k{1 + (m - 1) (число вершин в m-арном дереве глубиной

(Е - 1))} = k = km^E.

Случай 2. ĵ = ĥ. Пусть N_h - число вершин, которые были раскрыты до достижения цели. Здесь мы обязаны раскрывать вершину, если она расположена в пределах 2Е — 1 единиц от вершины на кратчайшем пути. (Обманчиво перспективные вершины в этом случае заставляют процесс перебора отойти на большее расстояние от кратчайшего пути к цели.) Итак, для Е >= 1 имеем:

N_h= k{1 + (т— 1) (число вершин в m-арном дереве глубины

(2Е - 2))} = k = km^2E-1.

(Отдельно можно показать, что N_h = k для Е = 0.)

Рис. 3.9. Граф, изображающий бесконечное m-арное дерево.

Мы видим, что nh больше N_g+h для Е> 1, а это означает, что (для нашего графа) для эффективного перебора необходимо в оценочную функцию включить функцию ĝ. Отношение Ng+h / Nh не зависит от k и дается просто выражением

для Е>=1.

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

Задачи

3.1. Рассмотрите представление в пространстве состояний для задачи о коммивояжере, описанной в разд. 26. Предложите по крайней мере две функции ĥ (ĥ  0), являющиеся нижней границей для h Какая из этих функций, приведет к более эффективному перебору? Примените алгоритм А* с такими функциями к задаче о коммивояжере для 5 горо­дов, которая показала на рис. 2 4.

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

*3.3. Рассмотрите возможные достоинства следующей стратегии перебора в пространстве состояний любым удобным методом получить некоторый путь к цели и его стоимость С. Эта стоимость не обязательно минимальна, но она дает некоторую верхнюю границу для минимальной стоимости. Теперь воспользуйтесь алгоритмом А* с некоторой функцией ĥ, гарантирующей допусти­мость, и сразу же отбросьте те полученные открытые вершины, значения ĵ для которых больше, чем С. Означает ли факт возможного отбрасывания некоторых из открытых вершин в этом алгоритме, что число вершин, которые будут раскрыты, может оказаться меньше?

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