logo
ЛОИИ методичка 2015

Слепые методы поиска

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

Поиск в глубину. Процесс расширения происходит слева направо, то есть движение идет вглубь по дереву.

Алгоритм поиска в глубину:

  1. создать одноэлементную очередь, включающую путь нулевой длины, соответствующий корневому узлу дерева.

  2. пока головной путь в очереди не оканчивается целью или пока очередь не пуста повторять:

  • если полный путь найден, показать его, иначе сообщить о неудаче.

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

    Выбор метода поиска зависит от свойств поискового дерева, поиск в ширину эффективнее, когда пути имеют небольшую глубину. Кроме того, поиск в ширину работает в дереве с ветвями бесконечной длины (лабиринт). Поиск в глубину лучше для деревьев с большим фактором ветвления.

    Yandex.RTB R-A-252273-3
    Yandex.RTB R-A-252273-4