Intel_Nils (526801), страница 28
Текст из файла (страница 28)
Для-этого мы воспользуемся представлением об оцененной стоимости дерева решения. Пусть й — такая функция, что для каждой вершины п, которая не является неразрешимой, й" (л) служит оценкой величины й(а), т. е. стоимости оптимального дерева решения с корнем в вершине и. Мы будем называть й' эвристической функцией и будем пользоваться ею для упорядочения процесса раскрытия вершин. В процессе перебора, который мы опишем, строится дерево перебора.
На любом этапе этого перебора внизу дерева перв- 142 Гл. и Методы поиска при сведении задач к аодзадачам бора располагаются вершины одного из следующих трех типов: !) вершины, признанные в процессе перебора заключительными; 2) вершины, относительно которых в процессе перебора было установлено, что они не являются заключительными и у них нет дочерних вершин; 3) вершины, для которых в процессе перебора еще не были построены дочерние вершины. Любую из таких вершин в дереве перебора мы будем называть концевой вершиной. Теперь мы опишем, каким образом для каждой вершины и дерева перебора должна строиться эвристическая функция 6(п).
и — концевая вер шина Если установлено, что и является заключительной вершиной. то й" (п) = О. Если установлено, что п не является заключительной вершиной и у нее нет дочерних вершин, то функция й(п) не определена. Если у вершины и еще не были построены дочерние вершины, то за 6(п) принимается некоторая эвристическая оценка стоимасти величины й(п) оптимального дерева решения с корнем в вершине п.
Такая оценка могла бы быть сделана на основе эвристической информации, касающейся происхождения задачи, представляемой нашим «И/1~ЛИ» деоевом. л — неконцевая вершина, имеющая дочерние вершины л~,...,ла типа „ИЛИ" Эвристическая функция Н(п) задается формулой й (П) Ш(П (С (П, Пе) + Пе (ПЕ)). л — неконцевая вершина, имеющая дочерние вершины л~,..., лз типа „Ии Эвристическая функция й(п) для суммарных стоимостей за дается формулой 6 (и) ~,е (с (и пе) + Ь (пе)1 1-1 а для максимальных стоимостей — формулой пе (и) шах [с (и, пе) + пе (пе)) б.б. Использование оценок стоимости для прямого перебора 143 Поскольку 6(п) = 0 для заключительных вершин, наше определение'дает гарантию, что при 6 ~ й в состав дерева перебора будет входить наше «И/ИЛИ» деревд целиком. Далее, в дереве поиска на каждом этапе содержится множество поддеревьев с корнем в з, каждое из которых могло бы в зависимости от результатов дальнейшего раскрытия вершин стать верхней частью полного дерева решения.
Назовем эти деревья потенциальными деревьями решений для з. Для каждой вершины, имеющей дочерние вершины типа «ИЛИ», в дереве поиска можно выбрать отдельное потенциальное дерево решения, соответствующее каждой из дочерних вершин типа «ИЛИ». Аналогично имеются также потенциальные деревья решений с корнем в вершине и, которые могли бы решать подзадачу, соответствующую этой вершине. (Конечно, если только эта вершина не помечена уже как неразрешимая.) На каждом этапе в процессе перебора можно извлечь нз дерева перебора это потенциальное дерево решения тс, корень которого расположен в з и которое по оценке служит верхней частью оптимального дерева решения с корнем в з.
В процедуре извлечения используются величины й; основана процедура на следующем определении: !. Начальная вершина входит в то. 2. Если у вершины и, входяшей в то, в девеве перебора есть а) дочерние вершины пь..., пь типа «ИЛИ», то та нз ннх, для которой значение ~с(п,п;) + 6(пс)) минимально, также входит в то (в случае равных значений выбор произволен), б) дочерние вершины типа «И», то все они входят в то. Это потенциальное дерево решения то, по оценке служащее верхней частью оптимального дерева решения с корнем в з, является ключевым понятием в эвристическом' процессе перебора, ' который нам предстоит описать. Уместная здесь процедура упорядочения связана с вопросом «Какое из потенциальных деревьев решения наиболее перспективно для раскрытия», а не с вопросом «Какая нз вершин наиболее перспективна для раскрытия на следуюшем шаге», (Аналогично при переборе в пространстве состояний, выбирая вершину с минимальным значением Г = Д+ 6, мы продолжаем наиболее перспективный частичный путь.) Мы будем брать то в качестве наиболее перспективного потенциального дерева решения.
Для того чтобы в ходе нашего процесса перебора можно было извлечь дерево то, мы должны следить за величинами й в каждой вершине дерева поиска. После того как дерево то извлечено, раскрываются те его концевые вершины, которые еще не выбирались для раскрытия, н для такого выросшего дерева пересчитываются величины й". На самом деле достаточно пересчитать величины й" только для вершин, предшествуюшнх только 144 Ге. Ц Методы поиска при сведении задач к подэадачо и что раскрытой вершине, ибо для других вершин они не изменятся, (Величина б для вершины зависит лишь от величин Ю следующих за ней вершин.) Прежде чем точно описать процесс перебора, основанный на этих идеях, надо располагать средствами для решения вопроса о том, какую из концевых вершин дерева те раскрывать на следующем шаге.
Можно предложить различные методы. Возможно, хорошей идеей был бы выбор вершины, раскрытие которой с наибольшей вероятностью опровергало бы гипотезу о том, что те окажется верхней частью оптимального дерева решения. В самом деле, если то не является верхней частью оптимального дерева решения, хотя в данный момент оно и оценивается как таковое, то для эффективности процедуры перебора требуется, чтобы этот факт был обнаружен как можно быстрее. Дополнительные соображения по этому вопросу будут приведены в равд. 5.9. Пока же предположим, что у иас есть некие средства определения, какую из концевых вершин те раскрывать в следующую очередь.
З.т. АЛГОРИТМ УПОРЯДОЧЕННОГО ПЕРЕБОРА ДЛЯ ДЕРЕВЬЕВ ТИПА «И!ИЛИ» Мьс можем теперь дать перечень шагов, определяющий алгоритм упорядоченного перебора для деревьев «И/ИЛИ». Этн шаги лишь немного отличаются от этапов метода полного перебора: (1) Поместить начальную вершину з в список вершин с названием ОТКРЫТ и вычислить б(з). (2) Получить потенциальное дерево решения, которое по оценке служит верхней частью оптимального дерева решения с корнем в э, используя для этого величины 6 для вершин дерева перебора. (3) Выбрать некоторую концевую вершину дерева то, которая имеется в списке ОТКРЫТ, и поместить ее в список вершин с названием ЗАКРЫТ.
Обозначить эту вершину через л. (4) Если и — заключительная вершина, то пометить вершину и как разрешимую и продолжать. В противном случае перейти к (9). (5) Применить к те процедуру разметки разрешимых вершин, (б) Если начальная вершина помечена как разрешимая, то на выход выдается то в качестве дерева решения; в противном случае продолжать. (7) Изъять из списка ОТКРЫТ все вершины, имеющие разрешимые предшествующие нм вершины. (8) Перейти к (2).
(9) Применить к л оператор Г и построить все дочерние вершины для и. Если дочерних вершин нет, то пометить вер- д 7. Алгоритм упорядоченного пер«бора для деревьев типа «И!ИЛИ» НЗ шину п как неразрешимую и перейти к следующему этапу. В противной случае перейти к (14). (10) Применить к тв процедуру разметки неразрешимых вершин. (11) Если начальная вершина помечена как неразрешимая, то на выход подается сигнал о неудаче.
В противном случае продолжать далее. (12) Изъять из списка ОТКРЫТ все вершины, имеющие неразрешимые предшествующие им вершины. (13) Перейти к (2). (14) Поместить эти дочерние вершины в список ОТКРЫТ и провести от них указатели назад к вершине и. Вычислить величины б для этих вершин. Пересчитать величины 6 для вершины и и для предшествующих ей вершин.
(15) Перейти к (2). Блок-схема этой процедуры изображена на рис. 5.8. (Заметим, что в частном случае, когда не возникает вершин типа «И», в этой процедуре перебор дерева осуществляется способом, идентичным методу упорядоченного перебора в пространстве состояний. Кроме того, если стоимости дуг равны единице, б = 0 для концевых вершин и используется определение максимальной стоимости, то эта процедура приводит к тем же результатам, что и процедура полного перебора.) На рис.
5.9 приведена последовательность гипотетических деревьев перебора, нллюстонрующая работу нашего алгоритма упорядоченного перебора. Предположим, что раскрытие начальной вершины привело к дереву перебора, изображенному на рис. 5.9,а. Число, стоящее рядом с вершиной, указывает величину Н. Для концевых вершин эти величины служат эвристическими оценками суммарных стоимостей решений соответствующих задач. Величины й' для других вершин этого дерева получаются в результате применения определения й'(п) для суммарных стоимостей в предположении об единичной стоимости ребер. Исходя нз этих значений Н, можно получить потенциальное дерево решения тв, которое по оценке должно быть верхней частью оптимального дерева решения. Это дерево тв выделено жирными ветвями. Далее мы раскрываем некоторую концевую вершину в тв.
Предположим, что в результате возникает дерево перебора. изображенное на рис. 5.9,б. Из-за новых значений величин 6 дерево тв теперь переместится в другую часть дерева перебора. Раскрытие вершины в этом дереве тв приводит, скажем, к дереву перебора рис. 5.9,в. Здесь мы получили некоторые заключительные вершины, а значит, и некоторые разрешимые вершины. Они отмечены черными кружочками. Заметим, что величины 6 для заключительных вершин равны нулю. После еще Является ли Нет и заключительной? Пометить п кан лавре ишмую Применить Гк п Применить процедуру Разметки разрешимых ! вершин Есть ли - Не,я у п дочерние вершины? Да Пометить и нак неразреишмую да являетсв ли Нет и разреши- мои 1 Применить прицеду??у роэметни неразрешимых вершин Успех Нет ЯвлиетсЯ ли Да и неразрешимои? Неудача Р и с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
