3.11. ВАЖНАЯ РОЛЬ ФУНКЦИИ

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

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

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

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

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

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

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

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

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

Кроме того, знак этой ошибки выбран так, чтобы вызвать наибольшие затруднения.

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

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

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

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

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

(Отдельно можно показать, что для

Мы видим, что больше для а это означает, что (для нашего графа) для эффективного перебора необходимо в оценочную функцию включить функцию Отношение не зависит от и дается просто выражением

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