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