Я должен реализовать следующие алгоритмы:
- Отделение & Связанное
- Филиал и связка с расширенным списком
- Branch & Bound w / Допустимая эвристика
- A * Алгоритм (также упоминается как алгоритм Дейкстры в более позднем руководстве MIT)
Следуя этому руководству MIT, я смог сформировать следующее понимание четырех реализаций.
Предполагается, что вы пытаетесь найти кратчайший (оптимальный) путь между узлом S и узлом E .
Simple Branch & Bound :
- Должен найти кратчайший путь к каждому узлу, прежде чем быть уверенным, что он нашел кратчайший путь к E .
- Использует обычную очередь для отслеживания узлов, которые она должна сканировать.
Отделение и связка с расширенным списком
- Расширенный список отслеживает уже посещенные нами узлы, поэтому мы не можем повторно посещать узлы, которые уже имеют оптимальные пути.
- Чтобы этот метод гарантировал оптимальный путь, необходимо использовать очередь с приоритетами, чтобы при посещении узла мы могли быть уверены, что путь к этому узлу является оптимальным (это явно не указано в руководстве )
- Этот алгоритм может быть остановлен, как только мы достигнем конечного узла
- Это лучше, чем обычный B & B, но у него нет смещения в сторону конечного узла E , и, следовательно, может быть быстрее
A * алгоритм
A* = B&B + dynamic programming + admissible heuristic (из руководства)
- Допустимая эвристика h (N) , в данном случае это длина наиболее известного в настоящее время пути до N + евклидова расстояния от N до E.
- Это позволяет алгоритму смещать конечный узел вместо сканирования всего.
- Очередь приоритетов используется для выбора следующего лучшего узла (динамическое программирование) (аналогично реализации расширенного списка)
Branch & Bound с допустимой эвристикой
Теперь вот с чем у меня проблемы, так как кажется, что добавление эвристики без очереди приоритетов не даст никакого преимущества перед простым алгоритмом B & B, потому что мы не назначаем приоритеты узлам с очередью приоритетов (потому что, если мы это сделали , это был бы просто алгоритм A *.
Если только возможно , эвристика позволяет нам проверять меньшее количество узлов даже без очереди приоритетов с помощью процесса, который я не совсем понимаю.
Было бы здорово увидеть объяснение того, почему мы бы хотели добавить эвристику в алгоритм B & B без добавления очереди с приоритетами.