Меня интересует естественное обобщение знаменитой 15-головоломки , где вам нужно сдвигать блоки, пока вы не отсортируете все заданные числа (обычно есть разрыв в 1 блок).
Теперь обобщение должно было бы увеличить размер головоломки с 15 до , где одно поле свободно. Я создал небольшую иллюстрацию (пунктирные стрелки показывают разрешенные ходы, а нижняя конфигурация показывает решенную головоломку):
Учитывая начальную конфигурацию головоломки, я задаю себе следующий вопрос:
Решение вопроса : Учитывая загадку размера , и число K ∈ N . Есть последовательность из k или менее разрешенных ходов, которые превращают головоломку в решенную конфигурацию?
Я уже сделал некоторые исследования и нашел статью « ( п 2 - 1 ) -puzzle и связанные с ними проблемы переселения » с 1990 года, который показывает , что решение на мой вопрос для р = д является NP-полным и , следовательно, решить мой вопрос является NP- Завершить (так как общий алгоритм может также решить вопрос для симметричных полей).
Вопрос, который остается открытым, состоит в том, является ли проблема решения также NP-полной для фиксированного . Меня особенно интересуют частные случаи q = 2 , 3 . Он также остается открытым, если выделение большего количества свободного пространства, чем одного поля, затрудняет или облегчает решение проблемы.
Все статьи, которые я мог найти, к сожалению, пропускают асимметричный случай, таким образом, я думаю, что не может быть никаких известных результатов по этому поводу. Поскольку доказательства в статье довольно сложны и совсем не переводятся для фиксированной высоты, я скорее надеюсь, что кто-то может придумать другое сокращение / статью, которая ответит на некоторые вопросы.
Другие связанные статьи (будет расширен):
источник
Ответы:
Я думаю, что нашел частичный (хотя и довольно разочаровывающий) ответ на мою проблему:
Я наткнулся на эту статью (2007):
" Сложность трехмерной маршрутизации канала » Сатоши Таю и Шуичи Уэно
Они показывают (теорема 4), что «проблема маршрутизации 3d-каналов» с «2-сетями» и размерностьюр , д может быть решена, если и только если соответствующая (см. статью для более подробной информации) р × q- 1 головоломка может быть решена.
Ниже теоремы 1 они предлагают некоторую проблему, которую они называют «2.5-D CHANNEL ROUTING», которая в основном является «маршрутизацией по 3-м каналам» с фиксированной глубинойК , Они также говорят, что «сложность следующей задачи [2.5-D Channel Routing] открыта для любого фиксированного целого числаk≥2 ".
If we knew that the decision version of thep×q−1 puzzle is NP-Complete for some fixed k≥2 we would also know that 2.5-D Channel Routing is difficult for that k , therefore it seems the question can be reduced to some open problem.
It could of course be that the answer to my question would be thatp×q−1 puzzle is in P for all fixed k , which would still leave their question open (as the general routing doesn't only handle 2 -Nets). Therefore this is no complete answer, it is also rather disappointing that they include no references when claiming that the problem is still open.
источник