Реконфигурация токена

В теории сложности вычислений и комбинаторике проблема реконфигурации токена — это проблема реконфигурации графа с начальным и желаемым состоянием токенов.

Учитывая график $G$ , начальное состояние токенов определяется подмножеством $V\subset V(G)$ вершин графа; позволять $n=|V|$ . Перемещение токена из вершины $v_{1}$ в вершину $v_{2}$ действителен , если $v_{1}$ и $v_{2}$ соединены путем в $G$ не содержащий других токенов; Обратите внимание, что расстояние, пройденное внутри графа, несущественно, и последовательное перемещение токена по нескольким ребрам считается одним перемещением. Желаемое конечное состояние определяется как другое подмножество $V'\subset V(G)$ . Цель состоит в том, чтобы минимизировать количество допустимых ходов для достижения конечного состояния из начального состояния. ^[1]

Мотивация

Проблема мотивирована так называемыми скользящими головоломками , которые на самом деле являются вариантом этой задачи, часто ограничиваясь прямоугольными сетками без отверстий. Самая известная такая головоломка, головоломка «15», представляет собой вариант этой задачи на сетке 4 на 4, такой что $n=|V(G)|-1$ . Одно из ключевых отличий между головоломками со скользящими блоками и проблемой реконфигурации жетонов заключается в том, что в исходной задаче реконфигурации жетонов жетоны неразличимы. В результате, если граф связен, проблема реконфигурации токена всегда разрешима; это не обязательно относится к головоломкам с раздвижными блоками.

Сложность

Калинеску, Думитреску и Пах показали несколько результатов, касающихся как оптимизации, так и аппроксимации этой проблемы на различных типах графов. ^[2]

Оптимизация

Во-первых, если перейти к случаю деревьев, всегда существует решение не более чем $n$ ходы, не более одного хода на каждый жетон. Более того, оптимальное решение может быть найдено за время, линейное по размеру дерева. Очевидно, что первый результат распространяется на произвольные графы; последний этого не делает.

Схема оптимального алгоритма для деревьев выглядит следующим образом. Во-первых, мы получаем алгоритм, который перемещает каждый узел ровно один раз, что может быть неоптимальным. Сделайте это рекурсивно: рассмотрим любой лист наименьшего дерева в графе, содержащий как исходное, так и желаемое множества. Если лист этого дерева есть в обоих, удалите его и вернитесь вниз. Если лист есть только в исходном множестве, найти путь от него до вершины искомого множества, не проходящий через другие вершины искомого множества. Удалите этот путь (это будет последний ход) и вернитесь вниз. Другой случай, когда лист находится только в нужном множестве, является симметричным. Чтобы расширить алгоритм, достигающий оптимума, рассмотрим любой токен как в исходном, так и в желаемом наборах. Если его удаление приведет к разбиению графа на поддеревья, все из которых имеют одинаковое количество элементов из исходного и желаемого наборов, сделайте это и выполните рекурсию. Если такой фишки нет, то каждая фишка должна переместиться ровно один раз, и поэтому решение, которое перемещает все фишки ровно один раз, должно быть оптимальным.

В то время как алгоритм поиска оптимума на деревьях является линейным по времени, поиск оптимума для общих графов является NP-полным, что представляет собой скачок в сложности. Это в НП; сертификат представляет собой последовательность ходов, размер которой не превышает линейного размера, поэтому остается доказать, что задача также является NP-сложной. Это осуществляется за счет уменьшения комплекта крышки .

Рассмотрим пример покрытия множества, где мы хотим охватить все элементы. $v_{1},v_{2},\ldots ,v_{n}$ во вселенной $U$ использование подмножеств $S_{1},S_{2},\ldots ,S_{m}$ из $U$ используя минимальное количество подмножеств. Постройте график следующим образом:

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

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

Приближение

Задача реконфигурации токена является APX-полной , что означает, что в некотором смысле ее так же сложно аппроксимировать, как и любую задачу, имеющую алгоритм аппроксимации с постоянным коэффициентом . Уменьшение такое же, как указано выше, из комплекта обложки. Однако проблема покрытия множеств ограничивается подмножествами размером не более 3, что является APX-сложной проблемой. ^[3]

Используя точно ту же структуру, что и выше, мы получаем L-редукцию , поскольку расстояние любого решения от оптимального одинаково между экземпляром набора покрытия и преобразованной проблемой реконфигурации токена. Единственное изменение — это увеличение количества элементов во Вселенной. Более того, оптимум покрытия множества составляет не менее 1/3 числа элементов из-за ограниченного размера подмножества. Таким образом, константы L-редукции равны $\alpha =1/4,\beta =1$ .

Фактически, можно изменить сокращение, чтобы оно работало и для реконфигурации помеченных токенов. Для этого к каждой из вершин подмножества прикрепите новую вершину, которая не является ни начальной, ни желаемой вершиной. Обозначьте вершины на длинном пути от 1 до $n$ и сделайте то же самое для вершин элементов. Теперь решение состоит в том, чтобы «отодвинуть» каждый выбранный токен вершины подмножества, правильно разместить помеченные вершины на пути и вернуть токены вершин подмножества в исходные местоположения. Это L-редукция с $\alpha =1/5,\beta =2$ .

Калинеску, Думитреску и Пах также показали, что существует 3-приближение для реконфигурации немаркированных токенов, поэтому проблема также заключается в APX и, следовательно, в APX-полноте. Доказательство гораздо сложнее и здесь опускается.

Ссылки

^ Демейн, Эрик (осень 2014 г.). «Алгоритмические нижние границы: забава с доказательствами твердости, лекция 11, примечания» (PDF) .
^ Калинеску, Груя; Думитреску, Адриан; Пах, Янош (2006). «Реконфигурации в графиках и сетках». ЛАТИНЬ 2006: Теоретическая информатика . Конспекты лекций по информатике. Том 3887. стр. 262–273. дои : 10.1007/11682462_27 . ISBN 978-3-540-32755-4 . {{cite book}}: |journal= игнорируется ( помогите )
^ Пападимитриу, Христос Х.; Яннакакис, Михайлис (1991). «Классы оптимизации, аппроксимации и сложности». Журнал компьютерных и системных наук . 43 (3): 425–440. дои : 10.1016/0022-0000(91)90023-X .

[d-1] Демейн, Эрик (осень 2014 г.). «Алгоритмические нижние границы: забава с доказательствами твердости, лекция 11, примечания» (PDF) .

[calinescu-2] Калинеску, Груя; Думитреску, Адриан; Пах, Янош (2006). «Реконфигурации в графиках и сетках». ЛАТИНЬ 2006: Теоретическая информатика . Конспекты лекций по информатике. Том 3887. стр. 262–273. дои : 10.1007/11682462_27 . ISBN 978-3-540-32755-4 . {{cite book}}: |journal= игнорируется ( помогите )

[3] Пападимитриу, Христос Х.; Яннакакис, Михайлис (1991). «Классы оптимизации, аппроксимации и сложности». Журнал компьютерных и системных наук . 43 (3): 425–440. дои : 10.1016/0022-0000(91)90023-X .

[1]

[2]

[3]