Intel_Nils (526801), страница 27
Текст из файла (страница 27)
Провести от них казахски к и Па Есть ли Пет у и дочерние вершины? Применить процедуру разметки неразрешимых вершин Пет Яеллеиюлли Па е неразреш- имойй? Уделать нз списио ОТКРЫТ юп шршины с ясрозрешимыми предшествующимиоерши- коми Неудача Удалить из списка ОГНРЫ7 вершины с раз!юшимыми предшествующими верши- нами Успех Р но 5.3. Блок-схема программы перебора в глубину на «И/ИЛИ» деревьях. Разрешимо ли зг Глубина?и) лраничной глубине ? Пометить и кан неразреитмую б.4. Перебор на графах типа «И(ИЛИ» (12) Изъять из списка ОТКРЫТ все вершины, являющиеся разрешимыми илн имеющие разрешимые предшествующие им вершины. (!3) Перейти к (2).
Пример последовательности, в которой раскрываются вершины в методе перебора в глубину, приведен га рис. 5.4. В этом примере граничная глубина принята равной 4. Черными 1 я ещм кипя кружочками показаны разрешимые вершины, белыми неразрешимые, а дерево решения выделено жирными ветвями. 5.4. ПЕРЕБОР НА ГРАФАХ ТИПА «И(ИЛИ» Всегда, когда процесс сведения задачи к совокупности подзадач приводит к построению дочерней верши- Р и с б.4.
«Н(или» дерево, показыны, эквивалентной некото иаюшее порядок, а котором раскры- ваются вершины прн переборе и глурому описанию задачи, уже бину (предел»иая глубина равна 4). построенному ранее в процессе перебора, результирующую структуру можно представить эффективнее не в виде дерева, а в виде <И(ИЛИ» графа, в котором вершины могут иметь более одной родительской вершины.
Если у нас есть возможность распознавать случаи эквивалентности описаний задач, то задачу поиска можно в общем случае существенно упростить, так как идентичные подзадачи достаточно решить один раз. К тому же обшая,графовая структура может содержать бесполезные циклы (давая циклические цепочки рассуждений), которые мы могли бы встретить, но не быть в состоянии их обнаружить, если бы считали разными в действительности идентичные описания задач.
Некоторые примеры «И/ИЛИ» графов, вершины которых могут иметь более одной родительской вершины, показаны на рис. 5.5. Заключительные вершины отмечены буквой г, а решающие графы выделены жирными ребрами. Заметим, что у графов на рнс. 5.5, а, б есть решающие подграфы, а у графа на рис. 5.5,в таких подграфов нет, поскольку на нем никак нельзя избежать зацикливания. Казалось бы, можно предположить, что для того, чтобы не попасть в цикл, следует отказываться от построения тех дочерних вершин для данной вершины, которые были бы для этой вершины предшествующими.
В действительности такое правило могло бы привести к исключению из рассмотрения некоторых 138 Гл. б. Методы поиска при сведении задач к подзадачам верных нециклических решений. Например, если вершины раскрываются в порядке, указанном на рнс. 5.6, мы, безусловно, захотим включить вершину 2 в число дочерних вершин для 6 (хотя вершина 2 в то же время предшествует 6), так как в противном случае мы не получили бы решения (возможно, единственного), показанного жирными ветвями.
в Рис. 5.5. Некоторые «И/ИЛИ» графы. При попытке определить процедуру перебора для графа (а ие дерева) типа «И/ИЛИ» возникает ряд осложнений. Во-первых, разумное определение процедуры полного перебора было бы, вероятно, связано с выбором для очередного раскрытия той вершины из списка ОТКРЫТ, которая имеет наименьшую глубину. Теперь, однако, несколько труднее, чем в случае деревьев, дать хорошее определение глубины.
Как и для обычных графов, глубина вершины в «И/ИЛИ» графе определяется следующим образом: Глубина начальной вершины равна О. Глубина любой другой вершины на 1 больше глубины салсой ближайшей ее родительской вершины. 139 б.б. Стоимости деревьев решения Второе осложнение связано с необходимостью установки указателей, идущих от данной вершины к более чем одной родительской вершине. Все эти указатели могут оказаться необходимыми при определении решающего графа. (Например, на рис. 5.6 обязательно должны содержаться в решении указатели, идущие от вершины 2 к вершинам 1 и 6.) С другой стороны, некоторые из этих кратных указателей могут и не потребоваться в решении (например, на рис.
5.6 в решение не должен входить указатель, идущий от вершины 3 назад к вершине4). Поэтому в процедуре перебора на «И/ИЛИ» графе должна быть предусмотрена возможность проанализировать после окончания работы структуру указателей графа перебора, с тем чтобы отбросить несущественные указатели и сохранить те, которые необходимы в решающем графе. Аналогично когда строятся дочерние вершины, следует провести специальную Рис. 6.6 Пример, показывающий, что ПРОВЕРКУ, НЕт ЛИ УжЕ КаКИХ- вершиие й может быть дочерией хля нибУдь нз этих веРшин в вершины 6 (через дугу а), хотя при списке ЗАКРЫТ н не были этом и возиикает цикл. ли они прежде помечены как разрешимые или как неразрешимые.
Если при этом мы пришли к уже разрешимой (или неразрешимой) дочерней вершине по новому пути, то небходимо воспользоваться процедурой разметки, чтобы проверить, разрешима ли (или неразрешима ли) начальная вершина. Разработку алгоритмов перебора на произвольных графах типа «И/ИЛИ» мы оставляем читателю в качестве упражнеыия.
Нашей ближайшей задачей будет исследование способов эффективного упорядочения процесса раскрытия вершин с использованием оценочных функций. Снова наше рассмотрение существенно упростится, если ограничиться случаем «И/ИЛИ» деревьев. 6.6. СТОИМОСТИ ДЕРЕВЬЕВ РЕШЕНИЯ В переборах в пространстве состояний у нас была возможность воспользоваться для упорядочения процесса раскрытия вершин эвристически выводимыми оценочными функциями. Ключевым понятием при определении этих оценочных функций 140 Гм Д Методы поиска при сведении задач и подзадачам было понятие эвристической функции, оценивающей стоимость оптимального яути от некоторой вершины до цели. В «И/ИЛИ» деревьях соответствующее понятие связано с оценкой стоимости дерева решения с корнем в данной вершине.
Разумеется, прежде чем решать, как давать оценку стоимости дерева решения с корнем в данной вершине, надо определить, что мы будем понимать под стоимостью «И/ИЛИ» решения. Нетрудно определить два различных понятия, каждое из которых приписывает определенные стоимости дугам дерева реше- ния: суммарную стоимость, 4 представляющую собой сумму стоимостей всех дуг в дереве решения, и максиь 3 6 мальную стоимость, определение которой основано на понятии пути по дереву реп 3 щения.
(Назовем путем по дереву с корнем в вершине и последовательность вершин (и„ п„ ..., пн) дерева, Рис. 5.7. два решающих дерева и их где пт = и, па — заключи- тельная вершина, а вершина Решение В и,— дочерняя для пт, при ств-1в / = 2, ..., й.) Сумму стонстои- Маасимааьиаа стоимость 17 мастей дуг, связывающих вершины некоторого пути, будем называть стоимостью пути. Максимальная стоимость— это стоимость пути по дереву решения, имеющего максимальную стоимость. Эти определения можно пояснить на деревьях решений, показанных на рис.
5.7, на котором числа, стоящие около дуг„ указывают стоимости последних. Здесь имеются два решения. Одно из них вь1делено жирными линиями (решение А), а другое (решение В) — перечеркнутыми линиями. У решения А суммарная стоимость равна 20, максимальная равна !5, а у решения В суммарная стоимость равна !8, максимальная равна 17. Какое из этих решений предпочтительнее, зависит, конечно, от того, какую стоимость мы пытаемся минимизировать. Часто стоимости дуг полагаются равными единице.
В этом случае суммарная стоимость есть просто число вершин в дереве решения без единицы. Подобным образом максимальная стоимость дает длину самой длинной цепочки шагов в дереве решения. В любом случае достаточно хорошую оценку любой из этих стоимостей можно с пользой применить в оценочной функции н тем самым эффективно упорядочить перебор. Дерево решения само по себе является поддеревом некото- рого неявно заданного «И/ИЛИ» дерева, определяемого началь- б.б. Испольеоеоние оценок стоимости для прямого перебора 141 ным описанием задачи, множеством операторов сведения задачи к подзадачам и множеством элементарных задач. Внутри всего неявно заданного «И»ИЛИ» деревй мы хотим найти дерево решения с минимальной стоимостью.
Такое дерево решения будем называть оптимальным деревом. Обозначим через й(э) стоимость оптимального дерева решения с корнем в начальной вершине э. Дадим рекурсивное определение минимальной стоимости й(э) через минимальную стоимость й(а) дерева решения с корнем в любой вершине а. Будем обозначать стоимость дуги между вершиной а» и ее дочерней вершиной л» через с(пил;).
1. Если л — заключительная вершина (отвечающая элементарной задаче), то й(п) =О. 2. Если л не является заключительной вершиной и имеет в качестве своих дочерных вершин вершины пь ..., пь типа «ИЛИ», то й(л) = пни[с(а, и,) + й(л»)]. 3. Если л не является заключительной вершиной и имеет в качестве своих дочерних вершин вершины аь ..., ля типа «И», то для суммарных стоимостей й(л) = 2.", [с(л, а»)+й(п,)], » а для максимальных стоимостей й(а)= шах[с(п, и,) + й(а;)]. Разумеется, функция й(п) не определена,' если вершина и не- разрешима. В,а. ИСПОЛЬЗОВАНИЕ ОПЕНОК СТОИМОСТИ ДЛЯ ПРЯМОГО ПЕРЕБОРА Нас будет интересовать поиск деревьев решения, обеспечивающих минимальную стоимость (либо суммарную, либо максимальную в зависимости от ситуации).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
