Cтратегии неинформированного поиска

Неинформированный поиск также называется «слепым», поскольку он ни на что не способен, кроме вырабатывания преемников и проверки целевого состояния. Существует несколько стратегий неинформированного поиска. В лабораторной работе рассмотрены две основных стратегии — поиск в ширину и поиск в глубину.

Поиск в ширину — это простая стратегия, в которой вначале развертывается корневой узел, затем — все преемники корневого узла, после этого развертываются преемники этих преемников и т.д. При этом проверяется совпадение разворачиваемой вершиной с целью. Если целевая вершина достигнута, то поиск останавливается. На рис.7 приведен пример развертывания дерева поиска с использованием этой стратегии.

Рис.7. Стратегия поиска в ширину

Примечание. На первом шаге происходит развертывание корневой вершины А. На втором шаге разворачиваются все потомки А — вершины В и С. На третьем этапе разворачиваются потомки этих вершин. Алгоритм завершается после разворачивания вершины Е — достигнуто целевое состояние. В результате получен путь AàCàEàF. И наш агент достигает своего назначения.

Одним из недостатков такого поиска является многократное развертывание одних и тех же состояний. Например, вершина С и вершина А разворачивались дважды. Такие напрасные действия увеличивают время работы алгоритма, если он выполняется в виде программы на компьютере.

Средством устранения этой проблемы является ведение истории развернутых вершин, или списка развернутых вершин. Алгоритмы, которые забывают свою историю, обречены на то, что бы ее повторять J. Если текущая вершина находится в этом списке, то нет смысла ее разворачивать, и она больше не рассматривается. По мере разворачивания вершин этот список пополняется. Пример работы поиска в ширину с ведением списка развернутых вершин представлен на рис.8.

Рис.8. Улучшенный вариант поиска в ширину

Примечание. На первом шаге разворачивается вершина А и заносится в список развернутых узлов. На втором шаге разворачиваются вершины В и С, которые также заносятся в список. На третьем шаге разворачиваются только узлы, отсутствующие в списке развернутых. Таким образом, нет необходимости разворачивать узлы А и С, их можно отбросить и сразу переходить к узлу Е.

Поиск в глубину — это такая стратегия, при которой всегда развертывается самый глубокий узел в дереве поиска. Поиск переходит на самый глубокий уровень дерева поиска, на котором узлы не имеют приемников. При этом проверяется совпадение разворачиваемой вершиной с целью. Если целевая вершина достигнута, то поиск останавливается.

На рис.9 приведен пример поиска в глубину в произвольном бинарном дереве. В этом примере всегда разворачивается самый левый потомок.

Рис.9. Поиск в глубину бинарном дереве.
Цель — найти вершину М

На рис.10 приведен пример развертывания дерева поиска с использованием стратегии поиска в глубину с ведением списка развернутых вершин. Данная стратегия возвратила нам более длинный путь, чем стратегия поиска в ширину, а сам поиск занял четыре этапа.

Существуют и другие стратегии неинформированного поиска: поиск с ограничением глубины, поиск в глубину с итеративным углублением, двунаправленный поиск — когда путь строится одновременно с двух сторон пространства состояний и др. Изучение этих стратегий выходит за рамки лабораторной работы.

Рис.10. Стратегия поиска в глубину

Примечание. На первом шаге разворачиваем корневую вершину А. На втором шаге разворачиваем левый потомок вершины А — вершину В. На третьем шаге необходимо развернуть опять же самую левую вершину — вершину А, однако она есть в списке, и мы ее пропускаем и разворачиваем вершину С. На четвертом шаге пропускаем вершину В, разворачиваем D, пропускаем А, разворачиваем Е и приходим к цели — вершине F. Таким образом, получаем путь AàBàCàEàF.

Дата добавления: 2015-07-26; просмотров: 168; Нарушение авторских прав

Мы поможем в написании ваших работ!