Задача реконфигурации «Змея»

13

Пока пишу небольшой пост о сложности видеоигр Nibbler и Snake ; Я обнаружил, что они оба могут быть смоделированы как задачи реконфигурации на плоских графах; и кажется маловероятным, что такие проблемы не были хорошо изучены в области планирования движения (представьте, например, цепочку связанных вагонов или роботов). Игры хорошо известны, однако это краткое описание соответствующей модели реконфигурации:

ЗМЕЯ ПРОБЛЕМА

Входные данные : дан плоский граф , л галька р 1 , . , , , Р л размещаются на узлах U 1 , . , , , У л , которые образуют простой путь. Галька представляет собой змею , а первый p 1 - его голова. Голова может быть перемещена из ее текущего положения в соседний свободный узел, а тело следует за ней. Некоторые узлы отмечены точкой; когда голова достигает узла с точкой, тело увеличится награммзнак равно(В,Е)Lп1,,,,,пLU1,,,,,ULп1 камешки в следующих электронных движениях головы. Точка на узле удаляется после обхода змеи.ее

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

Легко доказать, что задача SNAKE NP-трудна на плоских графах максимальной степени 3, даже если точки не используются, а также на графах решетки SOLID, если мы можем использовать произвольное количество точек. Вещи усложняются на сплошных графах без точек (это связано с другой открытой проблемой).

Я хотел бы знать, была ли проблема изучена под другим именем.
и, в частности, если есть доказательство того, что оно есть в НП ...

Изменить: проблема оказалась PSPACE-полной, даже на плоских графах, и результат кажется очень интересным, так что остается выяснить, является ли это новой проблемой и есть ли известные результаты о ней.

введите описание изображения здесь
Простой пример (галька показана зеленым цветом, голова змеи - P1).

Марцио де Биаси
источник
1
NпNпеNп
Можете ли вы дать лучшее и четкое определение для целевой конфигурации? Например, что вы подразумеваете под полным описанием положения змеи?
Саид
@Saeed: целевая конфигурация - это просто конечные позиции гальки (то есть змеи). Я добавлю рисунок, чтобы прояснить проблему.
Марцио Де Биаси
Ваш вопрос был достаточно ясен, но в моем комментарии я перепутал терминологию. Он должен читать «точки» везде, а не «галька».
Том ван дер Занден
@ TomvanderZanden: хорошо, спасибо, я согласен с вами (см. Также мой комментарий к ответу Zimmux). Я написал «... с или без точек ...», чтобы сказать, что они не имеют значения; но это было недостаточно ясно; поэтому я отредактировал вопрос и сделал его более четким.
Марцио Де Биаси

Ответы:

8

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

Недетерминированная логика ограничений

12223132Гаджеты NCL

змея

В нашей конструкции голова змеи будет гоняться за своим хвостом на небольшом расстоянии и будет вынуждена повторить тот же цикл с небольшими изменениями. Мы встраиваем каждое ребро графа ограничений, как на рисунке (ребра показаны красным), где мы указываем положение змеи толстыми линиями. Ребро имеет две стороны (вершины), и змея выбирает центральный маршрут в вершине, к которой направлено ребро. Обратный край

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

2

Снейк А Змея или

Наконец, черные линии всех устройств края соединены, чтобы сформировать единый цикл, таким образом, голова змеи преследует свой хвост. Если между двумя краевыми гаджетами мы сделаем черный путь достаточно длинным, змея всегда должна пересекать черные пути в одном и том же циклическом порядке.

Чтобы показать, что черные пути всегда могут быть построены плоско, рассмотрим охватывающее поддерево (толстые ребра на рисунке ниже) графа ограничений. Затем мы можем заставить черные ребра следовать этому дереву, как показано ниже, в результате чего получается плоский график.

Связующее поддерево Планарный цикл

Целевая позиция змеи может быть получена тем же преобразованием. Следовательно, реконфигурирование змеи завершено PSPACE даже на планарных графах.

Тим
источник
Большой! :-) :-) :-)
Марцио Де Биаси