ПОИСК В ГЛУБИНУ И В ШИРИНУОпределив направление поиска (от данных или от цели), алгоритм поиска должен определить порядок исследования состояний дерева или графа. В этом разделе рассматриваются два возможных варианта последовательности обхода узлов графа:
поиск в глубину {depth-fist) и
поиск в ширину (breadth-first).
Рассмотрим граф, представленный на рисунке. Состояния в нем обозначены буквами (А, В, С, ...), чтобы на них можно было сослаться в следующих рассуждениях.
При поиске в глубину после исследования состояния сначала необходимо оценить все его потомки и их потомки, а затем исследовать любую из вершин братьев.
Поиск в глубину по возможности углубляется в область поиска. Если дальнейшие потомки состояния не найдены, рассматриваются вершины-братья.
Поиск в глубину исследует состояния графа на рисунке в таком порядке: А, В, Е, К, S, L, T, F, М, С, G, N, H, О, Р, U, D, I, Q, J, R.
Поиск в ширину, напротив, исследует пространство состояний по уровням, один за другим. И только если состояний на данном уровне больше нет, алгоритм переходит к следующему уровню. При поиске в ширину на графе из рисунка состояния рассматриваются в таком порядке: А, В, С, D, Е, F, G, H, I, J, К, L, M, N, О, Р, Q, R, S, T, U.
Смеюсь последний ... тормоз однако!