Сетевой коммутатор (название придумано) выполнен с тремя типами узлов:
- один начальный узел
- один конечный узел
- один или несколько узлов коммутатора
Узел коммутатора имеет 3 выхода: влево, вверх, вправо; имеет два состояния L и R и целевое состояние TL или TR . Каждый переключатель может быть пройден по следующим правилам:
- всегда слева вверх; состояние переключателя меняется на L
- всегда справа вверх; состояние переключателя меняется на R
- сверху вниз, только если переключатель находится в состоянии L; государство не меняется
- сверху вниз, если переключатель находится в состоянии R; государство не меняется
- никогда слева направо или справа налево
Рисунок 1. Переключение узла в состояние L с целевым состоянием TR
Эти свойства также содержат:
- 0, 1 или 2 выхода переключателя могут быть изолированы (не подключены к другому переключателю);
- путь может «коснуться» переключателя, чтобы изменить его состояние: войти слева и выйти слева или войти справа и выйти справа;
- нет никаких ограничений на количество перемещений / касаний переключателя.
Проблема решения такова: «Существует ли путь от начального узла к конечному узлу так, что все конечные состояния коммутаторов соответствуют соответствующему целевому состоянию?»
Очевидно, что все переключатели, которые изначально не находятся в своем целевом состоянии, должны быть пройдены (или затронуты) хотя бы один раз;
Это быстрая отрисовка тривиальной сети (сделанной в Excel ... Я сделаю лучше):
Тривиальное решение это:
S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E
РЕДАКТИРОВАТЬ 2:
- Известна ли эта проблема? ---> вы дали мне хорошую ссылку на тезис Хирна (графы ограничений);
источник
Ответы:
Проблема, по крайней мере, NP-сложная, по сравнению с 3-SAT.
Сначала рассмотрим проблему поиска пути от начала до выхода следующего ориентированного графа с ограничением на то, что ни один путь не может посещать все три (квадратные) узла предложения:
Мы преобразуем эти графики в сеть коммутаторов. Для этого мы используем три гаджета:
На следующих рисунках переключатели изображены в виде двух входящих стрелок, одна из которых пунктирная (отключена). Направление цели обозначается черным кружком (таким образом, сплошная стрелка должна в конце концов находиться на стороне круга).
Примечание. Мы будем использовать жирный шрифт, чтобы отличить выход графика от выходов гаджетов.
Напомним, что для исходного графа поиск пути, который вел к выходу и не посещал все три квадратных узла любого предложения, был NP-завершен. Теперь рассмотрим проблему достижения выхода преобразованного графа, не беспокоясь о целевых положениях переключателей.
Заметьте, что любой путь, который является решением исходной задачи о графе, также является решением для преобразованного графа. Итак, предположим, что путь для преобразованного графа не является решением для исходного графа. Это может произойти в двух случаях:
В первом случае односторонний гаджет должен быть сначала пройден в намеченном направлении, и в этом случае путь мог бы также избежать его прохождения в первую очередь.
Итак, рассмотрим второй случай, когда путь пересекает все три переключателя некоторого гаджета Clause . Тогда у этого гаджета будут переключены все три переключателя (см. Ниже). Здесь мы используем целевые позиции. Обратите внимание , что серый магистральная часть Пункта гаджета больше не может быть достигнуто, не означает , что коммутаторы больше не могут быть направлены на их целевых позиций. В этом случае мы говорим, что этот гаджет Clause не подлежит восстановлению.
Осталось показать, что для любого решения исходной задачи графа переключатели преобразованного графа могут быть помещены в их целевое положение. Для этого мы используем тот факт, что выходной провод может быть достигнут только тогда, когда есть решение, или какой-то гаджет Clause становится неисправимым.
Чтобы поместить переключатели в их целевое положение, теперь мы можем добавить дополнительные односторонние гаджеты из провода выхода к входу каждого существующего одностороннего гаджета, а также к трем выходным проводам всех гаджетов Clause . Затем, как только токен достигнет выхода , все дополнительные односторонние гаджеты могут быть пройдены (и, таким образом, помещены в их целевую позицию), а также поместить оставшиеся переключатели в их целевые позиции (если нет невыполнимого предложения). Наконец, жетон может вернуться к выходу, и головоломка решена.
Следует отметить, что гаджеты Clause могут быть восстановлены только при входе с неисследованного выхода; и в связи с односторонним движением гаджетов, которые размещены между Clause устройствами и следующим переменным, это не может произойти до тех пор , выход проволока не будет достигнута.
Следовательно, проблема сети коммутатора является NP-трудной.
До сих пор неясно, является ли проблема в NP или PSPACE-сложной. Снижение NP-твердости при построении плоской сети коммутаторов будет иметь большое значение для ограниченных вариантов Sokoban, а именно потому, что все коммутаторы эквивалентны гаджету Sokoban ниже.
источник