Поиск в ширину

Согласно этой стратегии все узлы графа уровня (К+1) раскрываются после того, как построены все узлы уровня К. При К =0 имеем узел с начальным состоянием:

При поиске в ширину рассматриваются вначале все пути, длина которых равна 1, затем все пути, дина которых равна 2.

В итоге просматриваются все пути длиной К, ведущие из начального узла во все остальные.

В общем случае при глубине поиска К и числе ветвей L порядок всех узлов – О(L^к). Это число называется экспоненциальной оценкой сложности. При L = K =10 время просмотра всех узлов со скоростью 1000 узлов в секунду — 128 дней.

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

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

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