5.9. ВЫБОР ВЕРШИНЫ ДЛЯ ОЧЕРЕДНОГО РАСКРЫТИЯ

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

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

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

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

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