Сложность проблемы сети коммутатора

17

Сетевой коммутатор (название придумано) выполнен с тремя типами узлов:

  • один начальный узел
  • один конечный узел
  • один или несколько узлов коммутатора

Узел коммутатора имеет 3 выхода: влево, вверх, вправо; имеет два состояния L и R и целевое состояние TL или TR . Каждый переключатель может быть пройден по следующим правилам:

  • всегда слева вверх; состояние переключателя меняется на L
  • всегда справа вверх; состояние переключателя меняется на R
  • сверху вниз, только если переключатель находится в состоянии L; государство не меняется
  • сверху вниз, если переключатель находится в состоянии R; государство не меняется
  • никогда слева направо или справа налево

узел переключения
Рисунок 1. Переключение узла в состояние L с целевым состоянием TR

Эти свойства также содержат:

  • 0, 1 или 2 выхода переключателя могут быть изолированы (не подключены к другому переключателю);
  • путь может «коснуться» переключателя, чтобы изменить его состояние: войти слева и выйти слева или войти справа и выйти справа;
  • нет никаких ограничений на количество перемещений / касаний переключателя.

Проблема решения такова: «Существует ли путь от начального узла к конечному узлу так, что все конечные состояния коммутаторов соответствуют соответствующему целевому состоянию?»

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

Это быстрая отрисовка тривиальной сети (сделанной в Excel ... Я сделаю лучше):

example2

Тривиальное решение это:

S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

РЕДАКТИРОВАТЬ 2:

  1. Известна ли эта проблема? ---> вы дали мне хорошую ссылку на тезис Хирна (графы ограничений);

NпSпAСЕзнак равнопSпAСЕ

Nп

Nп-сомпLеTе

Марцио де Биаси
источник
1
Я бросил быстрый взгляд на предложенную статью (сейчас я прочитаю ее более внимательно), но моя проблема, похоже, другая: переключатели меняют свое состояние в соответствии с направлением их прохождения. В статье коммутаторы «исправлены», и (более простые) проблемы имеют вид: «Существует ли конфигурация коммутатора, такая, что ...».
Марцио Де Биаси
4
@Vor: Кажется, это тесно связано с логическими играми с ограничениями Демейна и Хирна (я думаю, тезис Хирна groups.csail.mit.edu/mac/users/bob/hearn-thesis-final.pdf - очень хорошая рецензия на эту работу. ). Интересно, можно ли решить сложность вашей проблемы, используя их методы. Кажется, что это может быть завершено NEXP ...
Джошуа Грохов
3
Я только собирался указать на работу Hearn / Demaine - обратите внимание, что она также доступна в виде книги "Игры, головоломки и вычисления" (ISBN 978-1-56881-322-6), и это определенно кажется уместным для этого вопрос.
Стивен Стадницкий,
2
@Kaveh: для моего уровня знаний это тривиально в NPSPACE = PSPACE. Кажется, не в состоянии «рассчитывать»; но я не вижу простого доказательства того, что, если решение существует, то существует другое решение, в котором каждый переключатель перемещается / касается только постоянного числа раз.
Марцио Де Биаси
1
Примечание: более простая версия этой головоломки была рассмотрена также Дилленбургом и Нельсоном, и она представлена ​​в их Поиске по периметру
Карлос Линарес Лопес

Ответы:

2

Проблема, по крайней мере, NP-сложная, по сравнению с 3-SAT.

Сначала рассмотрим проблему поиска пути от начала до выхода следующего ориентированного графа с ограничением на то, что ни один путь не может посещать все три (квадратные) узла предложения:

3SAT

(Икс1Икс2Икс3)(Икс1¬Икс2Икс4)

Мы преобразуем эти графики в сеть коммутаторов. Для этого мы используем три гаджета:

  1. Каждый круговой узел и двунаправленный край становится проводом , образуя соединения между коммутаторами.
  2. Каждое направленное ребро становится односторонним гаджетом, состоящим из одного переключателя (см. Ниже).
  3. Каждый квадратный узел представляет собой один из трех переключателей, которые являются частью гаджета Clause (см. Ниже).

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

Примечание. Мы будем использовать жирный шрифт, чтобы отличить выход графика от выходов гаджетов.

AВВAИкс1Икс2Икс3Икс1'Икс2'Икс3'

Односторонний гаджет Гаджет

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

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

  1. ВA
  2. Путь пересекает все три пути гаджета Clause .

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

Итак, рассмотрим второй случай, когда путь пересекает все три переключателя некоторого гаджета Clause . Тогда у этого гаджета будут переключены все три переключателя (см. Ниже). Здесь мы используем целевые позиции. Обратите внимание , что серый магистральная часть Пункта гаджета больше не может быть достигнуто, не означает , что коммутаторы больше не могут быть направлены на их целевых позиций. В этом случае мы говорим, что этот гаджет Clause не подлежит восстановлению.

Застойная оговорка

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

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

Следует отметить, что гаджеты Clause могут быть восстановлены только при входе с неисследованного выхода; и в связи с односторонним движением гаджетов, которые размещены между Clause устройствами и следующим переменным, это не может произойти до тех пор , выход проволока не будет достигнута.

Следовательно, проблема сети коммутатора является NP-трудной.


До сих пор неясно, является ли проблема в NP или PSPACE-сложной. Снижение NP-твердости при построении плоской сети коммутаторов будет иметь большое значение для ограниченных вариантов Sokoban, а именно потому, что все коммутаторы эквивалентны гаджету Sokoban ниже.

Sokoban

Тим
источник