Intel_Nils (526801), страница 29
Текст из файла (страница 29)
5.В. Блок-алема программы упорядочеаиого перебора для «И/ИЛИ» деревьев. Удалить иэ списки ПТНРЫТ вершины с разрешимыми предшествующими верши- нами Паиестить дочерние вершины в список ОТНРЫТ. Устиновить от них и п указатели. Вычислить Й для дочерних верьуин и пересчитать величины Н для пи пред- шесте ющиХ ей вершин Удалить из списка ПТНРЫТ першины с нероэре шимыии предшествующими верши. нами 8 О 0 2 а Р в е. 8.9.
Ряд деревьев перебора, построенных алгоритмом упорядочеввого перебора. 148 Г*. б. Методы поиски лри сведении задач к лодзздаики- одного раскрытия мы, наконец, получаем дерево решения, выделенное на рис. 5.9, г жирными ветвями. Суммарная стоимость этого дерева равна 9, как показывают вычисления с использованием окончательных значений й'. 88. ДОПУСТИМОСТЬ АЛГОРИТМА УПОРЯДОЧЕННОГО ПОИСКА (ПЕРЕБОРА) Как и при переборах в пространстве состояний, алгоритм поиска на дереве «И/ИЛИ» называется допустимым, если его применение всегда приводит к решению минимальной стоимости, при условии что дерево решения существует. Мы докажем сейчас, что если оценка 6 является нижней границей величины й для открытых вершин, то алгоритм упорядоченного перебора допустим.
Сначала докажем следующую лемму: Лемма 5.1. Если Ю(п) ( й(п) для всех вершин из списка ОТКРЫТ, то на любом этапе процесса перебора для всех построенных вершин дерева перебора 6(п) ( й(п), причем длит вершин, уже полученных как разрешимые, здесь достигается равенство. Доказательство.
Доказательство поведем индукцией по. уровню дерева перебора '). Для деревьев перебора уровня О лемма тривиально выполняется, так как для таких деревьев единственной вершиной в дереве перебора будет начальная вершина з. Если з находится в списке ОТКРЫТ, то 6(з) ( й(з); если же вершина з разрешима, будучи заключительной вершиной, то 6(з) = 6(з) = О. Предположим теперь, что лемма верна для деревьев перебора любого уровня, меньшего или равного некоторому произвольному числу 1 (1 > О), и докажем, что она верна для деревьев перебора уровня 1 + !. Возьмем некоторое дерево перебора уровня 1 + 1.
Так как 1) О, то у начальной вершины э имеются вершины, непосредственно за ней следующие, скажем вершины пь ... пд. Эти вершины являются корнями поддеревьев уровня не выше 1, так что по предположению индукции лемма верна для всех вершин этих поддеревьев. Иными словами, для всех вершин этих поддеревьев 6 ( й (равенство достигается для разрешимых вершин). Таким образом, нам осталось доказать, что Й(з) ~ Й(з), а равенство достигается, когда вершина з разрешима, Предположим сначала, что пь ..., пе — вершины типа «ИЛИ».
Тогда по определению 6 . пс (з) = ппп (с (з, я,) + пе (п~)). ') Уровень дерева перебора опрецелкесев как глубина наиболее глубокой вз его концевых вершин. 5.8. Допустимость аегоритма упорпооиенного поиска (перебора) 149 Но по пРеДположению инДУкЦии 6(лт) ( Л(лт) ДлЯ =1, ..., А,такчто ле(з) ~поп (с(з, лт)+ й(лт)).
Правая часть этого неравенства по определению равна й(з)„ и поэтому )т (з) ( 'л (з). Далее, если вершина з разрешима, то алгоритм обязан был закончить свою работу, выдав дерево решения то, в котором некоторая вершина, скажем лм, является дочерней для з. По определению то 6(з) =с(з. лго)+6(лто) = ппп(с(з, лт) +6(л,)). т Но так как ть — дерево решения для з, то для него вершина л ь также должна быть разрешимой. По предположению индукции б(л ь) = й(л ь). Следовательно, " (з) = с (з, л м) + 6 (ль) = ш1 п [с (з, лт) + л (л)). Поскольку 6(лт) ( й(лт) для 1= 1, ..., й, ясно, что л(з) =с(з, лм)+ й(лто)(ш(п(с(з, л,)+ й(л,)].
Так как вершина лм является одной нз указанных вершин ль то й(з) = с(з, лм)+ Ь(лм) = ппп [с(з, л;) + Ь (л,)). Поэтому по определению л(з) Ь (з) = 6 (з), и лемма для случая, когда вершина з разрешима, доказана. Аналогичные рассуждения приводят к тому же результату н в случае, когда у з есть дочерние вершины типа «И» (и для суммарных, и для максимальных стоимостей). Доказательство закончено.
Заметим, что так как 6(л) = 6(л) для всех разрешимых вершин в дереве перебора, то поиску дерева минимальной стоимости не препятствует то, что на шаге (7) нашего алгоритма мы выбрасываем из списка ОТКРЫТ все вершины, имеющие разрешимые предшествующие им вершины. Не может произойти так, чтобы отброшенные вершины составили часть дерева решения минимальной стоимости. !оо Гл.
З, Методы поиска при сведении задач к подзадачам Теперь мы готовы сформулировать н доказать утверждение о том, что наш алгоритм упорядоченного перебора допустим в том случае, когда й' является нижней границей величины Ь для всех вершин из списка ОТКРЫТ. Теорема 5.1. Если 6(п) ( й(п) для любой открытой вершины п и стоимости всех дуг превосходят некоторую положительную величину б, то алгоритм упорядоченного перебора допустим. Доказательство.
Стратегия доказательства этой теоремы совпадает с использованной прн доказательстве теоремы 3.1. Предположим, что наш метод не приводит к построению оптимального дерева решения, но дерево решения в действительности существует. Снова мы имеем трн случая: !) алгоритм заканчивает свою работу, но дерево решения остается ненайденным; 2) алгоритм вообще не прекращает работу; 3) алгоритм заканчивает свою работу, построив дерево решения, стоимость которого неминнмальна. Случай 1. Алгоритм заканчивает работу без построения дерева решения.
Окончание может произойти лишь на шагах (б) и (1!) (стр, 144, 145). Если окончание вронзошло на шаге (6), то начальная вершина разрешима, а это может случитьсн, лишь если дерево решения было найдено. Если же окончание произошло на шаге (1!), то начальная вершина неразрешима. Но этот случай можно отбросить, поскольку мы предположили, что дерево решения на самом деле существует. Случай 2, Нет окончания вообще. В этом случае в конце концов будет раскрыта вершина, имеющая глубину а ) й(з)/6.
По определению величины 6 (неважно, для суммарной стоимости или максимальной) тогда будет Ж(з) ) Ю ) Й(з), что противоречит лемме 5.!. Случай 3. Алгоритм заканчивает работу построением дерева решения неминимальной стоимости. В момент окончания вершина з должна оказаться разрешимой и, следовательно, по лемме 5.1 Ь(з) = й(з). Но величина й(з) по окончании должна быть равна стоимости дерева тв, т. е. найденного дерева ре-шения, и, таким образом, это решение имеет минимальную стоимость. З.Э. ВЫБОР ВЕРШИНЫ В ее ДЛЯ ОЧЕРЕДНОГО РАСКРЫТИЯ Ясно, что свойство допустимости алгоритма упорядоченного перебора с величиной 6, являющейся нижней границей функции й для открытых вершин, не зависит от того, какие нз концевых вершин в списке ОТКРЫТ выбираются для раскрытия.
Мы Б.У. Выбор вершикы е т«длл очередного раскрытия 151 уже говорили, что, возможно, наиболее разумным было бы выбрать ту из концевых вершин в тш которая с наибольшей вероятностью ) приведет к опровержению гипотезы о том, что та служит верхней частью дерева решения,. имеющего минимальную стоимость. Если то на самом деле служит частью дерева минимальной стоимости, то безразлично, какую из открытых вершин в то раскрывать,в первую очередь, нбо в этом случае они так или иначе все должны быть выбраны для раскрытия.
Однако если тз не составляет части дерева решения минимальной стоимости, та нет смысла вкладывать слишком много сил в ненужный перебор. Тогда следует раскрыть в первую очередь ту вершину в т,, которая с наибольшей вероятностью обнаружит ошибку, допущенную при выборе то. Если используются суммарные стоимости, то вершиной, которая с наибольшей вероятностью показала бы непригодность тз, может оказаться открытая вершина в то, имеющая наибольшее значение б.
Так как она представляется концевой вершиной для решения максимальной стоимости, то, быть может, ее раскрытие в наибольшей степени повысит оцениваемую (суммарную) стоимость дерева то. В случае же максимальных стоимостей, по-видимому, полезным окажется метод выбора открытой вершины в тз, при котором, отправляясь от вершины з, мы идем по дереву то к некоторой открытой концевой вершине, выбирая под каждой из вершин конкретную дугу следующим образом. Всякий раз, когда в то мы встречаем вершину п с несколькими дочерними вершинами (типа «Ив) пь и,, ..., пш то переходим к той из неразрешимых дочерних вершин, которая малоимизирует величину (с(п,аг) + 6(пз)).
Достигнутая в результате такого процесса концевая вершина и должна быть той, вершиной, раекрытне которой с наибольшей вероятностью окажет неблагоприятное воздействие на оценку максимальной стоимости дерева ть Во всяком случае мы не можем доказать оптимальность ни одного из этих методов выбора открытых вершин. По-видимому, для «И/ИЛИ» деревьев нет результата, аналогичного результату для пространства состояний, касающемуся раскрытия наименьшего числа вершин.
Интуитивно, однако, кажется правдоподобным, что при любом способе выбора открытой вершины в то эффективность перебора выше для тех функций Н, которые лучше аппроксимируют истинную величину Ь, Чем лучше нижняя граница для й, используемая в й', тем направленнее будет идти перебор к дереву решения минимальной стоимости. ') Мы пользуемся словами «нанбольшая вероятностьь, яе вкладывая в ннл формального смысла, Мы не будем даже пытаться определить вероятности нлн пронзвестн статнстнческня анализ. 152 Гл. 5.
Методы поиска пии сведении задач к подзадачам 5.10. МОДИФИКАЦИИ Как и в случае переборов в пространстве состояний, существует ряд способов модификации основного алгоритма упорядоченного перебора, делающих его более практическим в конкретных ситуациях. Прежде всего, вместо того, чтобы после каждого раскрытия вершины заново строить новое потенциальное дерево решения, можно было бы не прерываясь раскрыть одну или более вершин в то и несколько их дочерних вершин, а затем уже строить новое дерево то. Такая стратегия приводит < снижению общих затрат на построение то, но в то же время возникает риск, что некоторые из раскрытых вершин не будут расположены на наилучшем потенциальном дереве решения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
