Шаги, которые гарантируют выход из лабиринта

14

Имеется двухмерный лабиринт, где вы можете дать 4 команды «двигаться вверх / вниз / вправо / влево». Зная лабиринт, а не где находится человек, как найти минимальную последовательность команд, которая гарантирует выход из лабиринта? Я ищу единственную последовательность команд, которая будет работать независимо от того, где в лабиринте вы начинаете.

Предположим, что если нашему партнеру будет дана команда «двигаться вправо», когда справа будет стена, он просто останется там, где он есть.

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

Существует ли алгоритм полиномиального времени для построения такой последовательности с учетом описания лабиринта?

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

Одновременное решение лабиринта . Стефан Функе, Андре Нуссер, Сабина Сторандт. AAAI 2017.

К сожалению, для общих графиков это кажется нерешенной проблемой, но мне интересно, может ли быть хороший алгоритм для этого конкретного случая. Я придумал подход кандидата: пометьте каждую позицию с минимальным количеством шагов, необходимых для выхода, и отслеживайте каждого агента в лабиринте. Это может быть возможно сделать поиск A * таким образом.

algorithms graphs graph-traversal seilgu
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Дискретная ящерица
Стратегия Эппштейна для монотонных автоматов состоит в том, чтобы кластеризовать состояния таким образом, чтобы вместо поиска пути в полном наборе состояний он искал путь в графе с полиномиально большим количеством вершин. Самым естественным обобщением интервалов в 2D, о котором я могу думать, является выпуклая оболочка, но, к сожалению, не ясно, что их число растет полиномиально .
Питер Тейлор

Ответы:

-1

A*

vonbrand
источник
Вы не можете кодировать следование за стеной как фиксированную последовательность кардинальных указаний. Выбор зависит от стен вокруг вас, что конкретно запрещено вопросом.
Кертис Ф
Если вы знаете кратчайший путь, вы можете закодировать его как «двигаться влево, затем прямо, затем ...». Если вы не знаете кратчайший путь, вы не можете дать такие указания для кратчайшего пути. Если вы не знаете пути, вы не можете дать указания, как выбраться.
vonbrand