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

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

Типы проблем

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

Всегда ли пространство состояний связно для данного класса задач? То есть можно ли превратить любую пару состояний друг в друга с помощью последовательности ходов? Если нет, то какова вычислительная сложность определения связности пространства состояний для конкретной задачи?
Каков диаметр пространства состояний, наименьшее число $D,$ при котором каждые два состояния могут быть преобразованы друг в друга не более чем за $D$ ходов?
Если дано два состояния, какова сложность определения возможности их преобразования друг в друга или нахождения кратчайшей последовательности ходов для превращения одного в другое?
Если ходы выбираются случайным образом с тщательно выбранным распределением вероятностей, так что результирующая цепь Маркова сходится к дискретному равномерному распределению , сколько ходов потребуется в случайном блуждании , чтобы гарантировать, что состояние в конце пути будет почти равномерно распределено? ? То есть, каково время смешивания цепи Маркова ?

Примеры

Примеры проблем, изучаемых при реконфигурации, включают:

Игры или головоломки, такие как головоломка «15» или кубик Рубика . Этот тип головоломки часто можно смоделировать математически с использованием теории групп перестановок , что приводит к быстрым алгоритмам определения того, связаны ли состояния; однако найти диаметр пространства состояний или кратчайший путь между двумя состояниями может быть сложнее. Например, для $n\times n\times n$ версии кубика Рубика, диаметр пространства состояний равен $\Theta (n^{2}/\log n)$ , и сложность нахождения кратчайшего решения неизвестна, но для обобщенной версии головоломки (в которой некоторые грани куба не помечены) она NP-трудна . ^[1] Другие головоломки реконфигурации, такие как Сокобан, могут быть смоделированы как реконфигурация токенов, но им не хватает теоретико-групповой структуры. Для таких задач сложность может быть выше; в частности, тестирование доступности для Сокобана является PSPACE-полным . ^[2]
Расстояние вращения в бинарных деревьях и связанные с ним проблемы расстояния переворота в флип-графах . Вращение — это операция, которая изменяет структуру двоичного дерева, не затрагивая порядок его узлов слева направо, часто используется для изменения баланса двоичных деревьев поиска . Расстояние вращения — это минимальное количество поворотов, необходимое для преобразования одного дерева в другое. То же самое пространство состояний также моделирует триангуляции выпуклого многоугольника и перемещает, что «переворачивает» одну триангуляцию в другую, удаляя одну диагональ многоугольника и заменяя ее другой; аналогичные проблемы изучались и для других видов триангуляции. Известно максимально возможное расстояние поворота между двумя деревьями с заданным числом узлов: ^[3] но остается открытой проблема, можно ли найти расстояние вращения между двумя произвольными деревьями за полиномиальное время . ^[4] Аналогичные задачи для переворота расстояния между триангуляциями множеств точек или невыпуклыми многоугольниками являются NP-трудными. ^[5]^[6]
Реконфигурация раскрасок графов . Ходы, которые рассматривались для реконфигурации окраски, включают изменение цвета одной вершины или замену цветов цепочки Кемпе . Когда количество цветов не менее двух плюс вырожденность графа, тогда пространство состояний одновершинных перекрасок связно, и гипотеза Сереседа предполагает, что оно имеет полиномиальный диаметр. Из-за меньшего количества цветов некоторые графы имеют несвязные пространства состояний. Для 3-раскрасок тестирование глобальной связности пространства состояний перекраски с одной вершиной является ко-NP-полным , ^[7] но когда две раскраски можно переконфигурировать друг с другом, кратчайшую последовательность реконфигурации можно найти за полиномиальное время. ^[8] Для более чем трех цветов реконфигурация одной вершины является PSPACE-полной. ^[9]
Недетерминированная логика ограничений — это комбинаторная задача об ориентации кубических графов , ребра которых окрашены в красный и синий цвета. В корректном состоянии системы каждая вершина должна иметь хотя бы одно синее ребро или хотя бы два входящих в нее ребра. Перемещение в этом пространстве состояний меняет ориентацию одного края на противоположную, сохраняя при этом эти ограничения. -полный тест PSPACE позволяет проверить, связно ли результирующее пространство состояний или достижимы ли два состояния друг из друга, даже если базовый граф имеет ограниченную полосу пропускания . ^[10] Эти результаты твердости часто используются в качестве основы для редукций, доказывающих, что другие проблемы реконфигурации, например, возникающие в играх и головоломках, также сложны. ^[11]

Ссылки

^ Демейн, Эрик Д .; Демейн, Мартин Л .; Эйзенштат, Сара; Любив, Анна ; Уинслоу, Эндрю (2011), «Алгоритмы решения кубиков Рубика», Алгоритмы - ESA 2011: 19-й ежегодный европейский симпозиум, Саарбрюккен, Германия, 5–9 сентября 2011 г., Труды , конспекты лекций по информатике, том. 6942, Springer, Гейдельберг, стр. 689–700, arXiv : 1106.5736 , doi : 10.1007/978-3-642-23719-5_58 , ISBN 978-3-642-23718-8 , МР 2893242 , S2CID 664306
^ Калберсон, Джозеф (1997), Сокобан является PSPACE-полным , Технический отчет TR97-02, Университет Альберты, факультет компьютерных наук, doi : 10.7939/R3JM23K33 , hdl : 10048/27119
^ Пурнен, Лайонел (2014), «Диаметр ассоциэдров», Успехи в математике , 259 : 13–42, arXiv : 1207.6296 , doi : 10.1016/j.aim.2014.02.035 , MR 3197650
^ Кандж, Ияд; Седжвик, Эрик; Ся, Ге (2017), «Вычисление переворотного расстояния между триангуляциями», Дискретная и вычислительная геометрия , 58 (2): 313–344, arXiv : 1407.1525 , doi : 10.1007/s00454-017-9867-x , MR 3679938 , S2CID 254033552
^ Любив, Анна ; Патак, Винаяк (2015), «Расстояние между двумя триангуляциями набора точек является NP-полным», Computational Geometry , 49 : 17–23, arXiv : 1205.2425 , doi : 10.1016/j.comgeo.2014.11.001 , MR 3399985
^ Айххольцер, Освин; Мюльцер, Вольфганг; Пильц, Александр (2015), «Расстояние переворота между триангуляциями простого многоугольника является NP-полным», Discrete & Computational Geometry , 54 (2): 368–389, arXiv : 1209.0579 , doi : 10.1007/s00454-015-9709- 7 , МР 3372115 , С2КИД 254037222
^ Сереседа, Луис (2007), Смешивание раскрасок графа , докторская диссертация, Лондонская школа экономики . См. особенно страницу 109.
^ Джонсон, Мэтью; Крач, Дитер; Крач, Стефан; Патель, Виреш; Паулусма, Даниэль (2016), «Нахождение кратчайших путей между раскрасками графов» (PDF) , Algorithmica , 75 (2): 295–321, doi : 10.1007/s00453-015-0009-7 , MR 3506195 , S2CID 253974066
^ Бонсма, Пол; Сереседа, Луис (2009), «Нахождение путей между раскрасками графов: PSPACE-полнота и суперполиномиальные расстояния», Theoretical Computer Science , 410 (50): 5215–5226, doi : 10.1016/j.tcs.2009.08.023 , MR 2573973
^ ван дер Занден, Том К. (2015), «Параметризованная сложность логики ограничений графа», 10-й Международный симпозиум по параметризованным и точным вычислениям , LIPIcs. Лейбниц Междунар. Учеб. Информ., вып. 43, замок Дагштуль. Лейбниц-Зент. Информ., Wadern, стр. 282–293, arXiv : 1509.02683 , doi : 10.4230/LIPIcs.IPEC.2015.282 , MR 3452428 , S2CID 15959029
^ Хирн, Роберт А.; Демейн, Эрик Д. (2005), «PSPACE-полнота головоломок со скользящими блоками и других проблем с помощью модели вычислений с недетерминированной логикой ограничений», Theoretical Computer Science , 343 (1–2): 72–96, arXiv : cs/ 0205005 , doi : 10.1016/j.tcs.2005.05.008 , MR 2168845 , S2CID 656067

Внешние ссылки

Ресурсы по комбинаторной реконфигурации (включая неисчерпывающую библиографию )

[rubik-1] Демейн, Эрик Д .; Демейн, Мартин Л .; Эйзенштат, Сара; Любив, Анна ; Уинслоу, Эндрю (2011), «Алгоритмы решения кубиков Рубика», Алгоритмы - ESA 2011: 19-й ежегодный европейский симпозиум, Саарбрюккен, Германия, 5–9 сентября 2011 г., Труды , конспекты лекций по информатике, том. 6942, Springer, Гейдельберг, стр. 689–700, arXiv : 1106.5736 , doi : 10.1007/978-3-642-23719-5_58 , ISBN 978-3-642-23718-8 , МР 2893242 , S2CID 664306

[sokoban-2] Калберсон, Джозеф (1997), Сокобан является PSPACE-полным , Технический отчет TR97-02, Университет Альберты, факультет компьютерных наук, doi : 10.7939/R3JM23K33 , hdl : 10048/27119

[pournin-3] Пурнен, Лайонел (2014), «Диаметр ассоциэдров», Успехи в математике , 259 : 13–42, arXiv : 1207.6296 , doi : 10.1016/j.aim.2014.02.035 , MR 3197650

[ksx-4] Кандж, Ияд; Седжвик, Эрик; Ся, Ге (2017), «Вычисление переворотного расстояния между триангуляциями», Дискретная и вычислительная геометрия , 58 (2): 313–344, arXiv : 1407.1525 , doi : 10.1007/s00454-017-9867-x , MR 3679938 , S2CID 254033552

[pointflip-5] Любив, Анна ; Патак, Винаяк (2015), «Расстояние между двумя триангуляциями набора точек является NP-полным», Computational Geometry , 49 : 17–23, arXiv : 1205.2425 , doi : 10.1016/j.comgeo.2014.11.001 , MR 3399985

[polyflip-6] Айххольцер, Освин; Мюльцер, Вольфганг; Пильц, Александр (2015), «Расстояние переворота между триангуляциями простого многоугольника является NP-полным», Discrete & Computational Geometry , 54 (2): 368–389, arXiv : 1209.0579 , doi : 10.1007/s00454-015-9709- 7 , МР 3372115 , С2КИД 254037222

[cereceda-7] Сереседа, Луис (2007), Смешивание раскрасок графа , докторская диссертация, Лондонская школа экономики . См. особенно страницу 109.

[jkkpp-8] Джонсон, Мэтью; Крач, Дитер; Крач, Стефан; Патель, Виреш; Паулусма, Даниэль (2016), «Нахождение кратчайших путей между раскрасками графов» (PDF) , Algorithmica , 75 (2): 295–321, doi : 10.1007/s00453-015-0009-7 , MR 3506195 , S2CID 253974066

[boncer-9] Бонсма, Пол; Сереседа, Луис (2009), «Нахождение путей между раскрасками графов: PSPACE-полнота и суперполиномиальные расстояния», Theoretical Computer Science , 410 (50): 5215–5226, doi : 10.1016/j.tcs.2009.08.023 , MR 2573973

[nclband-10] ван дер Занден, Том К. (2015), «Параметризованная сложность логики ограничений графа», 10-й Международный симпозиум по параметризованным и точным вычислениям , LIPIcs. Лейбниц Междунар. Учеб. Информ., вып. 43, замок Дагштуль. Лейбниц-Зент. Информ., Wadern, стр. 282–293, arXiv : 1509.02683 , doi : 10.4230/LIPIcs.IPEC.2015.282 , MR 3452428 , S2CID 15959029

[nclpuzzle-11] Хирн, Роберт А.; Демейн, Эрик Д. (2005), «PSPACE-полнота головоломок со скользящими блоками и других проблем с помощью модели вычислений с недетерминированной логикой ограничений», Theoretical Computer Science , 343 (1–2): 72–96, arXiv : cs/ 0205005 , doi : 10.1016/j.tcs.2005.05.008 , MR 2168845 , S2CID 656067

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]