5.8. ДОПУСТИМОСТЬ АЛГОРИТМА УПОРЯДОЧЕННОГО ПОИСКА (ПЕРЕБОРА)

Как и при переборах в пространстве состояний, алгоритм поиска на дереве «И/ИЛИ» называется допустимым, если его применение всегда приводит к решению минимальной стоимости, при условии что дерево решения существует. Мы докажем сейчас, что если оценка является нижней границей величины для открытых вершин, то алгоритм упорядоченного перебора допустим. Сначала докажем следующую лемму:

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

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

Предположим теперь, что лемма верна для деревьев перебора любого уровня, меньшего или равного некоторому произвольному числу и докажем, что она верна для деревьев перебора уровня

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

Но по предположению индукции для так что

Правая часть этого неравенства по определению равна и поэтому

Далее, если вершина разрешима, то алгоритм обязан был закончить свою работу, выдав дерево решения то, в котором некоторая вершина, скажем является дочерней для По определению то

Но так как то — дерево решения для то для него вершина также должна быть разрешимой. По предположению индукции Следовательно,

Поскольку для ясно, что

Так как вершина то является одной из указанных вершин то

Поэтому по определению

и лемма для случая, когда вершина разрешима, доказана. Аналогичные рассуждения приводят к тому же результату и в случае, когда есть дочерние вершины типа «И» (и для суммарных, и для максимальных стоимостей). Доказательство закончено.

Заметим, что так как для всех разрешимых вершин в дереве перебора, то поиску дерева минимальной стоимости не препятствует то, что на шаге (7) нашего алгоритма мы выбрасываем из списка ОТКРЫТ все вершины, имеющие разрешимые предшествующие им вершины. Не может произойти так, чтобы отброшенные вершины составили часть дерева решения минимальной стоимости.

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

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

Доказательство. Стратегия доказательства этой теоремы совпадает с использованной при доказательстве теоремы 3.1. Предположим, что наш метод не приводит к построению оптимального дерева решения, но дерево решения в действительности существует. Снова мы имеем три случая: 1) алгоритм заканчивает свою работу, но дерево решения остается ненайденным; 2) алгоритм вообще не прекращает работу; 3) алгоритм заканчивает свою работу, построив дерево решения, стоимость которого неминимальна.

Случай 1. Алгоритм заканчивает работу без построения дерева решения. Окончание может произойти лишь на шагах (6) и (11) (стр. 144, 145). Если окончание произошло на шаге (6), то начальная вершина разрешима, а это может случиться, лишь если дерево решения было найдено. Если же окончание произошло на шаге (11), то, начальная вершина неразрешима. Но этот случай можно отбросить, поскольку мы предположили, что дерево решения на самом деле существует.

Случай 2. Нет окончания вообще. В этом случае в конце концов будет раскрыта вершина, имеющая глубину По определению величины Н (неважно, для суммарной стоимости или максимальной) тогда будет что противоречит лемме 5.1.

Случай 3. Алгоритм заканчивает работу построением дерева решения неминимальной стоимости. В момент окончания вершина должна оказаться разрешимой и, следовательно, по лемме 5.1 . Но величина по окончании должна быть равна стоимости дерева То, т. е. найденного дерева решения, и, таким образом, это решение имеет минимальную стоимость.