Алгоритм «кратчайшего пути» с шагающим агентом

Question

Я ищу алгоритм кратчайшего пути, где агент (вещь, которая должна двигаться от начала до конца sh) имеет только ограниченное представление о поле, которое можно пройти. Допустим, у нас есть лабиринт со стартом и целью на основе тайлов. Примерно так: Тогда агент сможет видеть только одно в каждом направлении (вверх, вниз, влево, вправо) , но имеет неограниченную память . В качестве измерения я хочу как можно меньше шагов , чтобы достичь цели. Есть ли алгоритм для этого?

И если да, то есть ли алгоритм для более общей проблемы. Скажем так: график, несколько целей и запусков, а также функция, которая возвращает видимые узлы, и ограниченная память?

Решение, использующее звезду с полным зрением:

Answer 1

С ограниченной видимостью вы не сможете найти кратчайший путь, потому что вы можете видеть путь к цели или нет, если вам не повезло увидеть несколько путей.

Тем не менее, вы можете использовать heuristi c для улучшения вашего поиска. Например, вы захотите исследовать неизведанные плитки, расставляя приоритеты вокруг ваших целей, начиная с ближайших. С видимостью всего 1, вы в основном слепы, но если у вас была немного более высокая видимость, вы могли бы расставить приоритеты для исследования вокруг цели, пока не найдете путь, который соединяется с чем-то, что вы уже исследовали.

Это напоминает меня двунаправленная трассировка пути, техника рендеринга, где вы отслеживаете пути от камеры и источника света, пока они не соединятся. http://www.pbr-book.org/3ed-2018/Light_Transport_III_Bidirectional_Methods/Bidirectional_Path_Tracing.html

Answer 2

Простой подход, который я придумал, был:

walk to an undiscovered tile using a star
if it is the goal stop
if not repeat
if there aren't any undiscovered tiles stop and fail

Но это, безусловно, можно победить.

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