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

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

Типы проблем

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

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

Примеры

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

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

Ссылки

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, MR  2893242, S2CID  664306
2. Culberson, Joseph (1997), Sokoban is PSPACE-complete , Технический отчет TR97-02, Университет Альберты, Кафедра вычислительной техники, doi : 10.7939/R3JM23K33, hdl : 10048/27119
3. Pournin, Lionel (2014), «Диаметр ассоциэдров», Advances in Mathematics , 259 : 13–42, arXiv : 1207.6296 , doi : 10.1016/j.aim.2014.02.035 , MR  3197650
4. Кандж, Ияд; Седжвик, Эрик; Ся, Ге (2017), «Вычисление расстояния переворота между триангуляциями», Дискретная и вычислительная геометрия , 58 (2): 313–344, arXiv : 1407.1525 , doi : 10.1007/s00454-017-9867-x, MR  3679938, S2CID  254033552
5. Lubiw, Anna ; Pathak, Vinayak (2015), «Расстояние переворота между двумя триангуляциями множества точек является NP-полным», Computational Geometry , 49 : 17–23, arXiv : 1205.2425 , doi : 10.1016/j.comgeo.2014.11.001 , MR  3399985
6. Айххольцер, Освин; Мульцер, Вольфганг; Пильц, Александр (2015), «Расстояние переворота между триангуляциями простого многоугольника является NP-полным», Дискретная и вычислительная геометрия , 54 (2): 368–389, arXiv : 1209.0579 , doi : 10.1007/s00454-015-9709-7, MR  3372115, S2CID  254037222
7. Сереседа, Луис (2007), Смешивание раскрасок графов, докторская диссертация, Лондонская школа экономики. См. особенно страницу 109.
8. Джонсон, Мэтью; Крач, Дитер; Крач, Стефан; Патель, Виреш; Паулусма, Даниэль (2016), «Поиск кратчайших путей между раскрасками графа» (PDF) , Algorithmica , 75 (2): 295–321, doi : 10.1007/s00453-015-0009-7, MR  3506195, S2CID  253974066
9. Бонсма, Пол; Сереседа, Луис (2009), «Поиск путей между раскрасками графов: полнота PSPACE и суперполиномиальные расстояния», Теоретическая информатика , 410 (50): 5215–5226, doi :10.1016/j.tcs.2009.08.023, MR  2573973
10. ван дер Занден, Том К. (2015), «Параметризованная сложность логики ограничений графов», 10-й Международный симпозиум по параметризованным и точным вычислениям , LIPIcs. Leibniz Int. Proc. Inform., т. 43, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, стр. 282–293, arXiv : 1509.02683 , doi : 10.4230/LIPIcs.IPEC.2015.282 , MR  3452428, S2CID  15959029
11. Хирн, Роберт А .; Демейн, Эрик Д. (2005), «PSPACE-полнота головоломок со скользящими блоками и других задач с помощью недетерминированной модели логики ограничений вычислений», Теоретическая информатика , 343 (1–2): 72–96, arXiv : cs/0205005 , doi : 10.1016/j.tcs.2005.05.008, MR  2168845, S2CID  656067

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

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