NP-полнота решения задачи для обобщенной 15-головоломки

35

Меня интересует естественное обобщение знаменитой 15-головоломки , где вам нужно сдвигать блоки, пока вы не отсортируете все заданные числа (обычно есть разрыв в 1 блок).

Теперь обобщение должно было бы увеличить размер головоломки с 15 до , где одно поле свободно. Я создал небольшую иллюстрацию (пунктирные стрелки показывают разрешенные ходы, а нижняя конфигурация показывает решенную головоломку):p×q

введите описание изображения здесь

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

Решение вопроса : Учитывая загадку размера , и число K N . Есть последовательность из k или менее разрешенных ходов, которые превращают головоломку в решенную конфигурацию?p×qkNk

Я уже сделал некоторые исследования и нашел статью « ( п 2 - 1 ) -puzzle и связанные с ними проблемы переселения » с 1990 года, который показывает , что решение на мой вопрос для р = д является NP-полным и , следовательно, решить мой вопрос является NP- Завершить (так как общий алгоритм может также решить вопрос для симметричных полей).(n21)p=q

Вопрос, который остается открытым, состоит в том, является ли проблема решения также NP-полной для фиксированного . Меня особенно интересуют частные случаи q = 2 , 3 . Он также остается открытым, если выделение большего количества свободного пространства, чем одного поля, затрудняет или облегчает решение проблемы.q>1q=2,3

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

Другие связанные статьи (будет расширен):

Листинг
источник
2
@Listing: нет, вы не можете сделать это сами, модераторы могут переместить это (возможно, они заметят эти комментарии, и если они согласятся, они переместят это).
Марцио де Биаси
2
Я написал неопубликованную реализацию алгоритма Парберри (saml.pdf), адаптированную к асимметричному случаю. Это работает :-) Кроме того, я цитировал обзорную статью Эрика Демейна в моих публикациях, связанных с этой темой. Получите это на erikdemaine.org/papers/AlgGameTheory_GONC3 ; это немного новее, чем в газете 2008 года, FWIW. О(N3)
Йонас Кёлкер
4
@Vor Я предлагаю $ 50 денежного приза за доказательство NP-полноты :)
Мохаммад Аль-Туркистани
2
Связанные ?: cstheory.stackexchange.com/questions/783/…
Джошуа
2
@vzn Извините, если я не был достаточно конкретен здесь - я хочу попросить только фиксированное q, которое является особой формой асимметричного случая.
Объявление

Ответы:

4

Я думаю, что нашел частичный (хотя и довольно разочаровывающий) ответ на мою проблему:

Я наткнулся на эту статью (2007):

" Сложность трехмерной маршрутизации канала » Сатоши Таю и Шуичи Уэно

Они показывают (теорема 4), что «проблема маршрутизации 3d-каналов» с «2-сетями» и размерностью п,Q может быть решена, если и только если соответствующая (см. статью для более подробной информации) п×Q-1 головоломка может быть решена.

Ниже теоремы 1 они предлагают некоторую проблему, которую они называют «2.5-D CHANNEL ROUTING», которая в основном является «маршрутизацией по 3-м каналам» с фиксированной глубиной К, Они также говорят, что «сложность следующей задачи [2.5-D Channel Routing] открыта для любого фиксированного целого числаk2".

If we knew that the decision version of the p×q1 puzzle is NP-Complete for some fixed k2 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 that p×q1 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.

Listing
источник