Уменьшите сумму подмножества до полимино-упаковки

Это домашнее задание, поэтому любая помощь приветствуется.

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

Имея набор фигур, как показано ниже, и доску размером m на n, решите, возможно ли полностью покрыть доску всеми фигурами. Обратите внимание, что фигуры не могут вращаться.

Например, для доски 3 на 5 и следующих фигур доска может быть покрыта следующим образом:

фигуры

крытая доска

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

Приветствуются любые идеи по использованию другой NP-полной задачи.


algorithm subset-sum np-complete
person Ashkan Kazemi    schedule 01.06.2015    source источник
comment
Не могли бы вы указать, в чем заключается исходная проблема? В чем вопрос — доказать, что ответ на вопрос, можете ли вы покрыть доску, является NP-полным? что ты не можешь?   -  person shapiro yaacov    schedule 01.06.2015
comment
@shapiro.yaacov вам нужны дополнительные разъяснения? Потому что я думаю, что вопрос достаточно ясен. есть ли какой-то особый момент, который вы хотите знать?   -  person Ashkan Kazemi    schedule 01.06.2015
comment
1. Хотелось бы узнать исходный вопрос. 2. Попробуйте посмотреть задачу Wang Tile (не полный ответ, согласен). 3. Мне, по крайней мере, кажется, что вы формулируете проблему так, будто можно полностью покрыть доску всеми фигурами. Итак, это вопрос о том, как показать или заявить, что это возможно/не возможно?   -  person shapiro yaacov    schedule 01.06.2015
comment
Это не очень хороший вопрос для Stack Overflow.   -  person Nick    schedule 01.06.2015
comment
@shapiro.yaacov во-первых, да, это описывается как проблема решения, и для доказательства полноты np любой проблемы мы должны сначала описать ее как проблему решения. исходный вопрос точно указан в вопросе, и он на другом языке, поэтому я не могу опубликовать исходный вопрос здесь. Я видел эту проблему, но она требует доработки, но это был хороший указатель, спасибо!   -  person Ashkan Kazemi    schedule 01.06.2015
comment
@Nick, прежде чем публиковать вопрос, я проверил тег np-complete и тег суммы подмножества и увидел похожие вопросы, поэтому я разместил это здесь.   -  person Ashkan Kazemi    schedule 01.06.2015
comment
Подсказка: чтобы сделать сокращение, вам нужно каким-то образом превратить экземпляр Subset Sum в экземпляр этой задачи. Итак, есть ли очевидный способ превратить отдельный номер из задачи СС во что-то в этой задаче? Что произойдет, если вы будете следовать этому ходу мысли?   -  person j_random_hacker    schedule 01.06.2015
comment
@j_random_hacker я на самом деле именно этим и занимаюсь. Простой способ - иметь доску размером 1 * s (число суммы) для суммы, и каждое число получает i блоков, а затем попытаться покрыть доску блоками. проблема в том, что это не полиномиальная редукция!   -  person Ashkan Kazemi    schedule 01.06.2015
comment
en.wikipedia.org/wiki/ (не то же самое, но актуально)   -  person Veedrac    schedule 02.06.2015
comment
Чего-то не хватает... То, что вы мне говорите, подразумевает, что набор кусочков (и, в частности, их отдельные формы) не является частью проблемы. Я вижу две возможности: либо набор элементов является фиксированным (т. е. фиксированным для всех экземпляров проблемы, например, для набора из 4 блоков в вашем примере), или набор элементов является частью экземпляр проблемы, и в этом случае идея сокращения, которую я предложил, должна быть хорошей.   -  person j_random_hacker    schedule 02.06.2015
comment
@j_random_hacker, как я понял, что набор кусочков исправлен !? конечно, они являются частью проблемы.   -  person Ashkan Kazemi    schedule 03.06.2015
comment
@Veedrac на самом деле проблема, которую вы предложили, неразрешима, что означает, что она не является np-полной, это сложнее!   -  person Ashkan Kazemi    schedule 03.06.2015
comment
Мой комментарий, содержащий правильный ответ, был удален, предположительно, потому, что кто-то был оскорблен тем, что я сказал ОП, чтобы выразить некоторую признательность за предложенную помощь. Замечательный.   -  person j_random_hacker    schedule 04.06.2015
comment
@j_random_hacker ваш комментарий не содержал ответа и не был почти уместным.   -  person Ashkan Kazemi    schedule 04.06.2015
comment
В моем комментарии изложен ответ, и я выбрал тон, соответствующий тону вашего предыдущего комментария ко мне.   -  person j_random_hacker    schedule 04.06.2015
comment
У меня есть ответ, написание которого потребует больше усилий, чем я готов потратить. В случае, если это поможет, ключом является использование китайской теоремы об остатках для уменьшения суммы подмножества размера N до O (N) модульных сумм подмножества размера O (log N). Вы должны использовать различные трюки с замком и ключом, чтобы гарантировать, что одно и то же подмножество выбрано для всех модулей и т. д. Это кажется слишком сложным для домашней работы, поэтому, вероятно, есть более простой способ.   -  person Matt Timmermans    schedule 23.12.2020

Ответы (1)


arrow_upward
1
arrow_downward

Самое простое сокращение из проблемы раздела.

Предположим, что у нас есть набор положительных чисел, сумма которых равна 2n, и мы хотим знать, что подмножество этих чисел дает n.

Мы создаем набор блоков длины числа и ширины 1, затем пытаемся уместить их в прямоугольник шириной 2 и длиной n. Мы можем добиться успеха тогда и только тогда, когда проблема разбиения была решаема для этих чисел, а строки — это разбиение. Таким образом, любая проблема разбиения может быть сведена к задаче упаковки полимино за линейное время. Поскольку задача о разбиении является NP-полной, мы закончили.

Но они сказали подмножество суммы. Если они означают сумму подмножества положительных чисел, то мы можем просто использовать другой трюк. Предположим, что сумма наших чисел равна n, и мы хотим знать, составляет ли сумма подмножества k. Затем мы просто добавляем 2 числа к задаче размера k+1 и размера n-k+1 и стремимся решить проблему разделения. Если нам это удастся, наши дополнительные 2 номера не могли находиться в одном разделе, и поэтому остальные являются решением проблемы разделения. Поскольку мы уже свели проблему разбиения к проблеме упаковки полимино, мы закончили.

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

person btilly    schedule 23.12.2020