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

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

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

Общая форма задачи о движении гальки — «Движение гальки на графиках». ^[1] сформулировано следующим образом:

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

Вариации [ править ]

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

дерево ^[2]
квадратная сетка , ^[3]
двусвязный . граф ^[4]

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

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

Сложность [ править ]

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

Ссылки [ править ]

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

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

[Auletta-2] Аулетта, В.; Монти, А.; Паренте, М.; Персиано, П. (1999), «Алгоритм с линейным временем для возможности движения гальки на деревьях», Algorithmica , 23 (3): 223–245, doi : 10.1007/PL00009259 , MR 1664708 , S2CID 672515

[Calinescu-3] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Кэлинеску, Груя; Думитреску, Адриан; Пах, Янош (2008), «Реконфигурации в графиках и сетках», SIAM Journal on Discrete Mathematics , 22 (1): 124–138, CiteSeerX 10.1.1.75.1525 , doi : 10.1137/060652063 , MR 2383232

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

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

Вариации [ править ]

Сложность [ править ]

Ссылки [ править ]

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