Поиск в глубину | MetodPro.ru

Реклама на сайте

Поиск в глубину


Для того, чтобы найти минимальный путь, который будет храниться в переменной Реш, из некоторой заданной вершины B в некоторую целевую веришу, необходимо:

1.Если B-целевая вершина, то реш=[B];

2.Если для исходной вершины B существует приемник B1, такая что можно провести путь РЕШ1 из вершины B1 в целевую вершину, то решение Реш=[B/РЕШ1]

При реализации поиска в глубину имеется ввиду порядок, в котором рассмотрены альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину следует выбрать из нескольких вершин,  в которых нужно перейти для продолжения поиска нужно перейти для продолжения поиска он предпочитает самую “глубокую” из них. Самая глубокая вершина расположена дальше других от стартовой вершины.
Вершина – это состояние, из которого необходимо найти путь до цели. Путь-это список вершин между стартовой вершиной и вершиной ВЕРШ.

Решение – это путь, продолженный до целевой вершины.

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



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем