Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 34
Текст из файла (страница 34)
Дело в том, что значение Ьагз+)зв'з гораздо меньше, чем )зв, или, как показано на этом рисунке, площадь двух небольших кругов меньше площади одного большого круга с центром в начале поиска, который охватывает цель поиска. Рис. 3. 10. Схеиатичекое представление двунаправленного поиска в таи состоянии, когда он долзкен вскоре завершиться успешно после того, ш~гда одна из ветвей, исходящих из начального узла, встретится с ветвььо из целевого узла Двунаправленный поиск реализуется с помощью метода, в котором предусматривается проверка в одном или в обоих процессах поиска каждого узла перед его развертыванием для определения того, не находится ли он на периферии другого дерева поиска; в случае положительного результата проверки решение найдено.
Например, если задача имеет решение на глубине с(=б и в каждом направлении осуществляется поиск в ширину с последовательным развертыванием по одному узлу, то в самом худшем случае эти два процесса поиска встретятся, если в каждом из них будут развернуты все узлы на глубине 3, кроме одного. Это означает, что при Ь=10 будет сформировано общее количество узлов, равное 22 200, а не 11 111 100, как при стандартном поиске в ширину.
Проверка принадлежности узла к другому дереву поиска может быть выполнена за постоянное время с помощью хэш-таблицы, поэтому временная сложность двунаправленного поиска определяется как о()звз ) . В памяти необходимо хранить по крайней мере одно из деревьев поиска, для того, чтобы можно было выполнить проверку принадлежности к другому дереву, поэтому пространственная сложность также определяется как 0 ()з~" ) . Такие требования к пространству являются одним из наиболее существенных недостатков двунаправленного поиска. Этот алгоритм является полным и оптимальным (при единообразных стоимостях эта- 136 Часть П. Решение проблем пов), если оба процесса поиска осуществляются в ширину; другие сочетания методов могут характеризоваться отсутствием полноты, оптимальности или того и другого. Благодаря такому уменьшению временной сложности двунаправленный поиск становится привлекательным, но как организовать поиск в обратном направлении? Это не так легко, как кажется на первый взгляд.
Допустим, что 'оь предшественниками уздаип, определяемыми с помощью функции Рхес) (п), являются все те узлы, для которых и служит преемником. Для двунаправленного поиска требуется, чтобы функция определения предшественника рхес)(п) была эффективно вычислимой. Простейшим является такой случай, когда все действия в пространстве состояний обратимы таким образом, что рхес) (и ) = ~исо " (и ), а другие случаи могут потребовать проявить значительную изобретательность. Рассмотрим вопрос о том, что подразумевается под понятием "цель" при поиске "в обратном направлении от цели". В задачах игры в восемь и поиска маршрута в Румынии имеется только одно целевое состояние, поэтому обратный поиск весьма напоминает прямой поиск. Если же имеется несколько явно перечисленных целевых состояний (например, два показанных на рис.
3.2 целевых состояния, в которых квадраты пола не содержат мусор), то может быть создано новое фиктивное целевое состояние, непосредственными прелшественниками которого являются все фактические целевые состояния. Иным образом, формирования некоторых избыточных узлов можно избежать, рассматривая множество целевых состояний как единственное целевое состояние, каждым из предшественников которого также является множество состояний, а именно, множество состояний, имеющее соответствующего преемника в множестве целевых состояний (см.
также раздел 3.6). Наиболее сложным случаем для лвунаправленного поиска является такая задача, в которой для проверки цели дано только неявное описание некоторого (возможно, большого) множества целевых состояний, например всех состояний, соответствующих проверке цели "мат" в шахматах. При обратном поиске потребовалось бы создать компактные описания "всех состояний, которые позволяют поставить мат с помощью хода ж,", и т.дл и эти описания нужно было бы сверять с состояниями, формируемыми при прямом поиске.
Общего способа эффективного решения такой проблемы не существует. Сравнение стратегий неинформнрованного поиска В табл. 3.2 приведено сравнение стратегий поиска в терминах четырех критериев оценки, сформулированных в разделе 3.4. 3.5. ПРЕДОТВРАЩЕНИЕ ФОРМИРОВАНИЯ ПОВТОРЯЮЩИХСЯ СОСТОЯНИЙ Вплоть до этого момента мы рассматривали все аспекты поиска, но игнорировали одно из наиболее важных усложнений в процессе поиска — вероятность появления непроизводительных затрат времени при развертывании состояний, которые уже встречались и были развернуты перед этим.
При решении некоторых задач такая ситуация никогда не возникает; в них пространство состояний представляет собой дерево и поэтому имеется только один путь к каждому состоянию. В частности, эф- 137 Глава 3. Решение проблем посредством поиска фективной является формулировка задачи с восемью ферзями (в которой каждый новый ферзь помещается на самый левый пустой вертикальный ряд), и ее эффективность в значительной степени обусловлена именно этим — каждое состояние может быть достигнуто только по одному пути. А если бы задача с восемью ферзями была сформулирована таким образом, что любого ферзя разрешалось бы ставить на любую вертикаль, то каждого состояния с и ферзями можно было бы достичь с помощью гы различных путей.
Табанил 3.2. Опенка стратегий поиска, где Ь вЂ” коэффиниент ветвления; сг — глубина самого поверхностного решения; и — максимальная глубина дерева поиска; à — предел глубины. Предостережения, обозначенные строчными буквами, означают следующее: ' — полный, если коэффнниент ветвления Ь конечен; ' — полный, если стоимость каждого этапа >е при некотором положительном значении е; ' — оптимальный, если стоамости всех этапов являются одинаковыми; — применимый, если в обоих направлениях осуществляется поиск в ширину Характерис- тика Поиск с ог- раннчепнем глубины Двунаправ- ленный по- иск (если он применим) Поиск в ширину Поиск оо критерию стоимости Поиск в глубину Поиск с итератив- ным углуб- лением Полнота Даь о О)ьгх г)) Да' о)Ь ') Да' о)ь ) Да*' О)Ьюс) Нет Нет о)ь ) Временная сложность о)Ь') о)ьгх' ') о)ь ) О)Ьыэ) о)ь" ) Пространс- твеннаяя сложность о)ЬП) о)ьг) Оптималь- ность Да' Да" Да" Да Нет Нет В некоторых задачах повторяющиеся состояния являются неизбежными.
К ним относятся все задачи, в которых действия являются обратимыми, такие как задачи поиска маршрута и игры со скользящими фишками. Деревья поиска для этих проблем бесконечны, но если мы отсечем некоторые из повторяющихся состояний, то сможем уменьшить дерево поиска до конечного размера, формируя только ту часть дерева, которая охватывает весь граф пространства состояний. Рассматривая только часть дерева поиска вплоть до некоторой постоянной глубины, можно легко обнаружить ситуации, в которых удаление повторяющихся состояний гюзволяет достичь экспоненциального уменьшения стоимости поиска. В крайнем случае пространство состояний размером сгг1 (рис.
3.11, а) становится деревом с 2е листьями (рис. 3.11. б). Более реалистичным примером может служить Ъ. прямоугольная решетка, как показано на рис. 3.11, ы. В решетке каждое состояние имеет четырех преемников, поэтому дерево поиска, включающее повторяющиеся состояния, имеет 4о листьев, но существует приблизительно только 2с)' различных состояний с с) этапами достижения любого конкретного состояния. Для с1=20 это означает, что существует около триллиона узлов, но лишь примерно 800 различных состояний. Таким образом, неспособность алгоритма обнаруживать повторяю)циеся состояния может послужить причиной того, что разрешимая задача станет неразрешимой.
Такое обнаружение обычно сводится к тому, что узел, подлежагций развертыванию, сравнивается с теми узлами, которые уже были развернуты; если обнаружено совпадение, то алгоритм распознал наличие двух путей в одно и то же состояние и может отбросить один из них. [39 Глава 3. Решение проблем посредством поиска можно показать (упр. 3.! 2), что этого не может случиться, если используется либо поиск по критерию стоимости, либо поиск в ширину с постоянными стоимостями этапов; таким образом, эти две оптимальные стратегии поиска в дереве являются также оптимальными стратегиями поиска в графе. При поиске с итеративным углублением, с другой стороны, используется развертывание в глубину, поэтому этот алгоритм вполне может проследовать к некоторому узлу по неоптимальному пути, прежде чем найти оптимальный.
Это означает, что при поиске в графе с итеративным углублением необходимо проверять, не является ли вновь обнаруженный путь к узлу лучшим, чем первоначальный, и в случае положительного ответа в нем может потребоваться пересматривать значения глубины н стоимости путей для потомков этого узла. Листинг 3.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
