Понимание поиска *

Question

У меня возникли проблемы с пониманием того, как * поиск может быть применен к роботу, проходящему лабиринт в реальном времени . Я понимаю, как работает A *, но только в «предварительно вычисленном» смысле (т. Е. Если вы должны были проработать весь путь, прежде чем пытаться пройти лабиринт).

Как бы вы использовали его, чтобы дать ответ «куда идти дальше» на каждом шагу лабиринта? Или я что-то упустил? Большое спасибо!

Answer 1

Обычно робот отображает лабиринт как можно лучше, затем запускает алгоритм поиска пути и следует полученному лучшему пути. Если позднее изменения в лабиринте будут обнаружены, робот перезапустит A * из своего текущего положения.

Существует изменение в A *, называемое D * -lite , которое может повторно использовать прошлые поиски, чтобы ускорить будущие поиски, когда будут сделаны небольшие изменения в лабиринте. Это алгоритм, который используют марсоходы.