ВУЗ:
Составители:
Рубрика:
68
Поиск в ширину программируется не так легко, как поиск в глубину.
Причина состоит в том, что приходится сохранять все множество
альтернативных вершин-кандидатов, а не только одну вершину как при
поиске в глубину. Более того, если при помощи процесса поиска необходимо
получит решающий путь
, то следует хранить не множество вершин-
кандидатов, а множество путей-кандидатов. Для представления множества
путей-кандидатов обычно используют списки, однако при таком способе
одинаковые участки путей хранятся в нескольких экземплярах. Избежать
подобной ситуации можно, если представить множество путей-кандидатов в
виде дерева, в котором общие участки путей хранятся в его
верхней части без
дублирования. При реализации стратегии поиска в ширину решающие пути
порождаются один за другим в порядке увеличения их длин, следовательно,
стратегия поиска в ширину гарантирует получение кратчайшего решения
первым.
Представленные выше стратегии поиска в глубину и поиска в ширину
не учитывают стоимости, приписанной дугам в пространстве состояний.
Если критерием
оптимальности является минимальная стоимость пути, а не
его длина, то в данном случае поиск в ширину не решает поставленную
задачу.
Еще одна проблема, возникающая при решении задачи поиска – это
проблема комбинаторной сложности. Для сложных предметных областей
число альтернатив столь велико, что проблема сложности часто принимает
критический характер, так как длина
решающего пути (тем более, если их
множество, как при реализации поиска в ширину) может привести к
экспоненциальному росту длины в зависимости от размерности задачи, что
приводит к ситуации, называемой комбинаторным взрывом. Стратегии
a
b
c
d
e f
g
h i
j
k
Страницы
- « первая
- ‹ предыдущая
- …
- 66
- 67
- 68
- 69
- 70
- …
- следующая ›
- последняя »
