Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 33
Текст из файла (страница 33)
Таким образом, требуется только 0(ли памяти, а не О(Ьт) . При поиске с возвратами применяется еще один прием, позволяющий экономить память (и время); иден его состоит в том, чтобы при формировании преемника должно непосредственно модифицироваться описание текущего состояния, а не осуществляться его предварительное копирование. При этом потребность в памяти сокращается до объема, необходимого для хранения только одного описания состояния и о(т) действий. Но для успешного применения данного приема нужно иметь возможность отменять каждую модификацию при возврате, выполняемом для формирования следующего преемника.
При решении задач с объемными описаниями состояния, таких как роботизированная сборка, применение указанных методов модификации состояний становится важнейшим фактором успеха. Недостатком поиска в глубину является то, что в нем может быть сделан неправильный выбор и переход в тупиковую ситуацию, связанную с прохождением вниз по очень длинному (или даже бесконечному) пути, притом что другой вариант мог бы привести к решению, находящемуся недалеко от корня дерева поиска. Например, на рис.
3.8 поиск в глубину потребовал бы исследования всего левого поддерева, даже если бы целевым узлом был узел ~, находящийся в правом поддереве. А если бы целевым узлом был также узел,т, менее приемлемый по сравнению с узлом с, то поиск в глубину возвратил бъ1 в качестве решения именно его; это означает, что поиск в глубину не является оптимальным.
Кроме того, если бы левое поддерево имело неограниченную глубину, но не содержало бы решений, то поиск в глубину так никогда бы и не закончился; это означает, что данный алгоритм — не полный. В наихудшем случае поиск в глубину формирует все о(Ь ) узлов в дереве поиска, где т— максимальная глубина любого узла.
Следует отметить, что т может оказаться гораздо больше по сравнению с с( (глубиной самого поверхностного решения) и является бесконечным, если дерево имеет неограниченную глубину. Поиск с ограничением глубины Проблему неограниченных деревьев можно решить, предусматривая применение во время поиска в глубину заранее определенного предела глубины г".
Это означает, что узлы на глубине Г рассматриваются таким образом, как если бы они не имели Часть 11. Решение проблем 132 преемников. Такой подход называется |в. поиском с ограничением глубины. Применение предела глубины позволяет решить проблему бесконечного пути. К сожалению, в этом подходе также вводится дополнительный источник неполноты, если будет выбрано значение Е<д, иными словами, если самая поверхностная цель выходит за пределы глубины. (Такая ситуация вполне вероятна, если значение д неизвестно.) Кроме того, поиск с ограничением глубины будет неоптимальным при выборе значения Е>д.
Его временная сложность равна 0(Ъ'), а пространственная сложность— 0(ЬЕ) . Поиск в глубину может рассматриваться как частный случай поиска с ограничением глубины, при котором Е= Иногда выбор пределов глубины может быть основан на лучшем понимании задачи. Например, допустим, что на рассматриваемой карте Румынии имеется 20 городов. Поэтому известно, что если решение существует, то должно иметь длину не больше 19; это означает, что одним из возможных вариантов является Е=|9. Но в действительности при внимательном изучении этой карты можно обнаружить, что любой город может быть достигнут из любого другого города не больше чем за 9 этапов.
Это число, известное как ск диаметр пространства состояний, предоставляет нам лучший предел глубины, который ведет к более эффективному поиску с ограничением глубины. Но в большинстве задач приемлемый предел глубины остается неизвестным ло тех пор, пока не будет решена сама задача. Поиск с ограничением глубины может быть реализован как простая модификация общего алгоритма поиска в дереве или рекурсивного алгоритма поиска в глубину.
Псевдокод реализации рекурсивного поиска с ограничением глубины приведен в листинге 3.4. Обратите внимание на то, что поиск с ограничением глубины может приводить к неудачным завершениям двух типов: стандартное значение Еаз|иге указывает на отсутствие решения, а значение сисоЕЕ свидетельствует о том, что на заданном пределе глубины решения нет. Листинг 3.4. Рекурсивная реализация поиска с ограничением глубины Еипосзоп перси-Ь|т|сед-ЯеагсЬ(ргоЬ|ет, 1|тзс) гесигпв решение геяи|с или индикатор неудачи Еа|1иге/сиеоЕЕ гееигп Весигязче-ПЬЯ(нане-иоде(1л|сьа1-ЯСаге[ргоЫет]), ргоЬ1ет,|зли'с) ЕипоСЕоп Весигя|че-ПЬЯ(лоде, ргоЪ|ет, 1зт|с) гесиглв решение геяи|с или индикатор неудачи гад|иге/сисоЕЕ сигоЕЕ оссиггедг < — ложное значение ЕЕ Ооа1-Теяг[ргоЫет] (влаге[лоде]) сЬеп гееигп Яо1исдол(лоде) е1ве ЕЕ рерсЬ[лоде) = 1|т|с сЬеп гесигп индикатор неудачи сисоЕЕ е1ве Еог еасЬ преемник яиссеяяог ап Вкралд(лоде, ргоЫет) до геяи1С ~ — Делила|те-ПЬЯ(яиссеяяог, ргоЫет, 1зтзС) ЕЕ геяи|с = сисоЕЕ сЬеп сисоЕЕ оссиггедг +- истинное значение е1ве ЕЕ геяи|с Ф Еа|1иге сЬеп гесигп решение геяи1с аЕ сиеоЕЕ оссиггеда сЬеп гесигп индикатор неудачи сисоЕЕ е1ве гесигп индикатор неудачи Еаз1иге 133 Глава 3.
Решение проблем посредством поиска Поиск в глубину с итеративным углублением Ъ. Поиск с итеративным углублением (или, точнее, поиск в глубину с итеративным углублением) представляет собой общую стратегию, часто применяемую в сочетании с поиском в глубину, которая позволяет найти наилучший предел глубины. Это достигается путем постепенного увеличения предела (который вначале становится равным О, затем 1, затем 2 и т.д.) до тех пор, пока не будет найдена цель.
Такое событие происходит после того, как предел глубины достигает значения с), глубины самого поверхностного целевого узла. Данный алгоритм приведен в листинге 3.5. В поиске с итеративным углублением сочетаются преимущества поиска в глубину и поиска в ширину. Как и поиск в глубину, он характеризуется очень скромными требованиями к памяти, а именно, значением 0(ьс() .
Как и поиск в ширину, он является полным, если коэффициент ветвления конечен, и оптимальным, если стоимость пути представляет собой неубывающую функцию глубины узла. На рис. 3.9 показаны четыре итерации применения процедуры 1гегаезне-Реерепьпд-Яеагс)т к бинарному дереву поиска, где решение найдено в четвертой итерации.
Лнстнпг 3.5. Алгоритм поиска с итеративным углублением, в котором повторно применяется попок с ограничением глубины прн последовательном увеличении пределов. Оп завершает свою рабату после того, кап обнаруживается решение, плн процедура поиска с ограниченном глубины возвращает значение Еа11пге, а зто означает, что решение пе существует еппоееоп 1еегасече-Реерепепд-Беагсь(ргоь1ем) геепгпв рееение геяи1с или индикатор неудачи Еа11иге Еорпев: ргоыегп, задача Еог дерИ +- 0 ео йо геяи1с ~ — Ререн-ьетесес)-яеагсь(ргоыем, нери) ЕЕ геяи1с Ф оиеоЕЕ еиеп гесигп рееение геяи1е Поиск с итеративным углублением может на первый взгляд показаться расточительным, поскольку одни и те же состояния формируются несколько раз.
Но, как оказачось, такие повторные операции не являются слишком дорогостоягдими. Причина этого состоит в том, что в дереве поиска с одним и тем же (или почти одним и тем же) коэффициентом ветвления на каждом уровне большинство узлов находится на нижнем уровне, поэтому не имеет большого значения то, что узлы на верхних уровнях формируются многократно. В поиске с итеративным углублением узлы на нижнем уровне (с глубиной с)) формируются один раз, те узлы, которые находятся на уровне, предшествующем нижнему, формируются дважлы, и т.д., вплоть до дочерних узлов корневого узла, которые формируются с) раз.
Поэтому общее количество формируемых узлов выражается следуюшей формулой: )Ч(1РВ) = (г()Ь + (г(-1)Ь' + ... ч (1)Ьа которая соответствует временной сложности порядка 0(Ьа) . Это количество можно сравнить с количеством узлов, формируемых при поиске в ширину: и(врв) = ь+ ь'+ ... -ь - (,ь"-Ы Глава 3. Решение проблем посредством поиска 135 унаследовал бы от последнего алгоритма гарантии оптимальности, позволяя вместе с тем исключить его высокие требования к памяти. Идея состоит в том, чтобы вместо увеличивающихся пределов глубины использовались увеличивающиеся пределы стоимости пути. Результирующий алгоритм, получивший название ск поиска с итеративным удлинением, рассматривается в упр. 3.11.
Но, к сожалению, было установлено, что поиск с итеративным удлинением характеризуется более существенными издержками, чем поиск по критерию стоимости. Двунаправленный поиск В основе двунаправленного поиска лежит такая идея, что можно одновременно проводить два поиска (в прямом направлении, от начального состояния, и в обратном направлении, от цели), останавливаясь после того, как два процесса поиска встретятся на середине (рис. 3.10).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
