Проблемы с движением гальки - Pebble motion problems

В проблемы с движением гальки, или же движение гальки на графиках, представляют собой набор связанных проблем в теория графов имеет дело с движением нескольких объектов («камешков») от вершины к вершине в график с ограничением на количество камешков, которые могут занимать вершину в любой момент. Проблемы с движением гальки возникают в таких областях, какробот планирование движения (в котором камешки - роботы) и сетевая маршрутизация (в котором галька пакеты данных). Самый известный пример задачи о движении гальки - знаменитый 15 головоломка где неупорядоченная группа из пятнадцати плиток должна быть переставлена в сетке 4x4, сдвигая одну плитку за раз.

Теоретическая формулировка

Общая форма задачи движения гальки - это движение гальки на графах.^[1] сформулированы следующим образом:

Позволять ${ Displaystyle G = (V, E)}$ быть графом с ${ displaystyle n}$ вершины. Позволять ${ Displaystyle P = {1, ldots, k }}$ быть набором гальки с ${ Displaystyle к <п}$ . Расположение гальки - это отображение ${ displaystyle S: P rightarrow V}$ такой, что ${ Displaystyle S (я) neq S (j)}$ за ${ displaystyle i neq j}$ . Движение ${ Displaystyle м = (п, и, v)}$ состоит из передачи гальки ${ displaystyle p}$ из вершины ${ displaystyle u}$ в соседнюю незанятую вершину ${ displaystyle v}$ . Задачу Pebble Motion on Graphs необходимо решить, учитывая две схемы: ${ displaystyle S_ {0}}$ и ${ displaystyle S _ {+}}$ , существует ли последовательность ходов, преобразующая ${ displaystyle S_ {0}}$ в ${ displaystyle S _ {+}}$ .

Вариации

Общие вариации задачи ограничивают структуру графа следующим образом:

Другой набор вариантов рассматривает случай, когда некоторые^[5] или все^[3] гальки не имеют маркировки и взаимозаменяемы.

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

Сложность

Как известно, задача поиска кратчайшего пути в движении гальки на графах (с помеченными камешками) NP-жесткий^[6] и APX-жесткий.^[3] Непомеченная проблема может быть решена за полиномиальное время при использовании упомянутой выше метрики стоимости (минимизация общего количества переходов в соседние вершины), но она NP-жесткий для других показателей естественной стоимости.^[3]

Рекомендации

^ Корнхаузер, Даниэль; Миллер, Гэри; Спиракис, Пол (1984), «Координация движения камешков на графах, диаметр групп перестановок и приложения», Материалы 25-го ежегодного симпозиума по основам информатики (FOCS 1984), IEEE Computer Society Press, стр. 241–250, CiteSeerX 10.1.1.17.3556, Дои:10.1109 / sfcs.1984.715921, ISBN 978-0-8186-0591-8
^ Auletta, V .; Monti, A .; Parente, M .; Персиано, П. (1999), "Алгоритм линейного времени для возможности движения гальки по деревьям", Алгоритмика, 23 (3): 223–245, Дои:10.1007 / PL00009259, МИСТЕР 1664708
^ ^а ^б ^c ^d Кэлинеску, Груя; Думитреску, Адриан; Пах, Янош (2008), «Реконфигурации в графах и сетках», Журнал SIAM по дискретной математике, 22 (1): 124–138, CiteSeerX 10.1.1.75.1525, Дои:10.1137/060652063, МИСТЕР 2383232
^ Сурынек, Павел (2009), «Новый подход к планированию пути для нескольких роботов в двусвязных графах», Материалы Международной конференции IEEE по робототехнике и автоматизации (ICRA 2009), IEEE, стр. 3613–3619, Дои:10.1109 / robot.2009.5152326, ISBN 978-1-4244-2788-8
^ Пападимитриу, Христос Х.; Рагхаван, Прабхакар; Судан, Мадху; Тамаки, Хисао (1994), «Планирование движения на графе», Материалы 35-го ежегодного симпозиума по основам компьютерных наук (FOCS 1994), IEEE Computer Society Press, стр. 511–520, Дои:10.1109 / sfcs.1994.365740, ISBN 978-0-8186-6580-6
^ Ратнер, Дэниел; Вармут, Манфред (1990), "The ${ Displaystyle (п ^ {2} -1)}$ -заголовки и связанные с ними проблемы переезда », Журнал символических вычислений, 10 (2): 111–137, Дои:10.1016 / S0747-7171 (08) 80001-6, МИСТЕР 1080669

[Kornhauser-1] Корнхаузер, Даниэль; Миллер, Гэри; Спиракис, Пол (1984), «Координация движения камешков на графах, диаметр групп перестановок и приложения», Материалы 25-го ежегодного симпозиума по основам информатики (FOCS 1984), IEEE Computer Society Press, стр. 241–250, CiteSeerX 10.1.1.17.3556, Дои:10.1109 / sfcs.1984.715921, ISBN 978-0-8186-0591-8

[Auletta-2] Auletta, V .; Monti, A .; Parente, M .; Персиано, П. (1999), "Алгоритм линейного времени для возможности движения гальки по деревьям", Алгоритмика, 23 (3): 223–245, Дои:10.1007 / PL00009259, МИСТЕР 1664708

[Calinescu-3] а ^б ^c ^d Кэлинеску, Груя; Думитреску, Адриан; Пах, Янош (2008), «Реконфигурации в графах и сетках», Журнал SIAM по дискретной математике, 22 (1): 124–138, CiteSeerX 10.1.1.75.1525, Дои:10.1137/060652063, МИСТЕР 2383232

[Surynek-4] Сурынек, Павел (2009), «Новый подход к планированию пути для нескольких роботов в двусвязных графах», Материалы Международной конференции IEEE по робототехнике и автоматизации (ICRA 2009), IEEE, стр. 3613–3619, Дои:10.1109 / robot.2009.5152326, ISBN 978-1-4244-2788-8

[Papadimitriou-5] Пападимитриу, Христос Х.; Рагхаван, Прабхакар; Судан, Мадху; Тамаки, Хисао (1994), «Планирование движения на графе», Материалы 35-го ежегодного симпозиума по основам компьютерных наук (FOCS 1994), IEEE Computer Society Press, стр. 511–520, Дои:10.1109 / sfcs.1994.365740, ISBN 978-0-8186-6580-6

[Ratner-6] Ратнер, Дэниел; Вармут, Манфред (1990), "The ${ Displaystyle (п ^ {2} -1)}$ -заголовки и связанные с ними проблемы переезда », Журнал символических вычислений, 10 (2): 111–137, Дои:10.1016 / S0747-7171 (08) 80001-6, МИСТЕР 1080669

[1]

[2]

[3]

[4]

[5]

[6]