Простое пространство
Рисунок 11. 9. Простое пространство состояний: а - стартовая вершина,
f и j - целевые вершины. Применение стратегии поиска в ширину
дает следующий порядок прохода по вершинам: а, b, c, d, e, f. Более
короткое решение [a, c, f] найдено раньше, чем более длинное
[а, b, e, j]
нам приходится сохранять все множество альтернативных вершин-кандидатов, а не только одну вершину, как при поиске в глубину. Более того, если мы желаем получить при помощи процесса поиска решающий путь, то одного множества вершин недостаточно. Поэтому мы будем хранить не множество вершин-кандидатов, а множество путей-кандидатов. Таким образом, цель
вширину( Пути, Решения)
истинна только тогда, когда существует путь из множества кандидатов Пути, который может быть продолжен вплоть до целевой вершины. Этот продолженный путь и есть Решение.
Содержание раздела