Эта проблема определенно NP-трудна, и я могу это доказать. Существует сокращение от 3-SAT до этой проблемы. В частности, это сокращение от 3-SAT до подзадачи этой проблемы, в которой домино 1x3. Могут также быть другие сокращения для других определенных размеров, но это определенно работает.
По сути, в этом сокращении мы будем использовать позиции домино для кодирования истинного или ложного. В частности, я собираюсь принять ту же нотацию, что и другое решение, то есть я буду использовать звездочки для обозначения открытых пространств в сетке. Я также буду использовать наборы из трех заглавных букв для обозначения домино и строчных букв для обозначения «сигналов», которые являются пробелами, которые могут заполняться или не заполняться в зависимости от состояния системы.
Чтобы внедрить проблему 3-SAT в это пространство, нам понадобится набор того, что я буду называть гаджетами, которые позволят сделать возможными только определенные состояния. Большинство из этих гаджетов будут иметь фиксированное количество домино в них. Исключением будут гаджеты, представляющие предложения, которые будут иметь одно дополнительное домино, если предложение истинно (выполнено), но не тогда, когда оно ложно (неудовлетворено). Мы можем соединить эти гаджеты, используя пути. Вместе это позволит нам построить схему 3-SAT. У нас будет базовое количество домино, поскольку каждый путь и гаджет будут брать стандартное количество домино, мы можем сложить их, чтобы получить базовое число k, и тогда у каждого гаджета-предложения может быть одно дополнительное домино, если оно истинно, поэтому, если все предложения могут быть выполнены (и, следовательно, выражение выполнено), и есть n предложений, тогда максимальное количество домино будет n + k. Если нет, то максимальное число будет меньше, чем n + k. Это основная форма сокращения. Далее я опишу гаджеты и приведу примеры.
Как и в другом ответе, у нас будет две позиции, которые кодируют истину и ложь для данной переменной. Итак, я начну с одной плитки, которая может быть в двух возможных местах.
****
Это может быть покрыто одним домино, как
AAA* or *AAA
Очевидно, что это не может быть покрыто 2 домино, и покрытие его 0 домино никогда не будет максимальным. Для моих целей мы собираемся рассмотреть выступ для представления значения «ложь» и отсутствие выступа для представления «истина». Таким образом, мы можем рассматривать эту часть как имеющую два сигнала:
x**y
И в этом случае будет охвачен только один из x или y, поэтому мы можем рассматривать сигналы как x, а логические не как x. Для наших целей все, что покрыто, является ложным, все, что не покрыто, является истинным. Далее, мы можем передавать сигналы просто по прямым изогнутым путям. Если у нас есть
x*****y
У нас снова будет ровно два домино, и в результате будут покрыты либо x, либо y, но не оба.
***y
*
*
x
Будет вести себя точно так же. Таким образом, мы можем использовать это для создания длинных и искривленных траекторий с длиной, равной 3. Однако не все длины, которые мы могли бы использовать, имеют шаг 3, поэтому нам нужен дополнительный гаджет для перемещения на другое расстояние. Я называю это гаджетом скрипача, и его единственная цель - переместить сигнал на несколько неровных дистанций, чтобы все прошло успешно. Его вход поступает от x, а выход идет к y, и он просто передает один и тот же сигнал. Это выглядит так:
***y
*
**x
Он всегда содержит ровно два домино и заполняется одним из следующих двух способов:
BBB* ABBB
* A
AAA *AX
Если мы собираемся моделировать 3-SAT, нам нужно больше, чем это. В частности, нам нужен какой-то способ моделирования предложений. Для этого у нас есть гаджет, в который можно упаковать еще одно домино, если условие верно. Предложение будет истинным, если один или несколько его входов верны. В этом случае это означает, что мы можем упаковать одно дополнительное домино, когда хотя бы один из входов не выступает. Это будет выглядеть так:
*x*y*
*
z
Если мы добавим дополнительный путь к каждому для ясности, то это будет выглядеть так:
* *
* *
* *
*****
*
****
Если x, y и z все ложные, то все они будут иметь выступы, и они будут заполнены так:
A B
C D
C D
*C*D*
*
EEEF
Где остальные домино A, B и F продолжаютсяна пути где-то вниз.Если хотя бы один из входных данных является истинным, то мы можем упаковать одно дополнительное домино (G) следующим образом:
C B A D A B
C D C D C D
C D or C D or C D
GGGD* *CGGG *CGD*
* * G
EEEF EEEF GEEE
Однако, даже если все входные данные верны, мы не можем упаковать более одного домино,Этот сценарий будет выглядеть следующим образом:
C D
C D
C D
*****
*
*EEE
И, как вы можете видеть, мы можем вставить только одно дополнительное домино в пустое пространство, а не два.
Теперь, если термины никогда не былиповторил, то мы бы сделали (или почти закончили).Тем не менее, они могут повторяться, поэтому далее нам нужен разделитель сигналов, чтобы одна переменная могла появляться в нескольких терминах.Для этого мы используем следующий гаджет:
y*** ***z
* *
***
***
x
В этом гаджете x - это вход, а y и z - это выходы.В этом гаджете мы всегда можем собрать 5 домино.Если x выступает, чем упаковка 5 домино всегда будет требовать покрытия y и z.Если x не выступает, то покрытие y и z не требуется.Упаковка, в которой x не выступает, выглядит следующим образом:
yAAA BBBz
C D
CED
CED
E
Когда x выступает, (мы используем X, чтобы указать конец выпадающего в пространство домино x), максимальная упаковка обязательно охватывает как y, так и z.:
AAAC DBBB
C D
C*D
EEE
X
Я возьму момент, чтобы отметить, что было бы возможно собрать это с пятью домино, когда x не выступает таким образом, что либо y, либо z выступают.Однако это может привести к тому, что термины, которые могут быть истинными (не выступающими), станут ложными (выступающими).Разрешение некоторым из терминов (не переменных, а фактических терминов в предложениях) различаться по значению только из-за ненужного ложного выражения никогда не приведет к возможности удовлетворить иным неудовлетворительным выражением.Если бы наше 3-SAT-выражение было (x | y | z) & (! X | y |! Z), то разрешение ложных значений x и! X только усложнило бы ситуацию.Если бы мы допустили, чтобы оба конца чего-то были верными, это привело бы к неверным решениям, но мы не делаем этого в этой схеме.Чтобы сформулировать ее с точки зрения нашей конкретной проблемы, высовывание излишне никогда не приведет к тому, что больше домино будет упаковано позже по линии.
С путями и этими тремя гаджетами мы теперь можем решить плоскую 3-SAT, что было бы подзадачей 3-SAT, где, если мы нарисуем граф, в котором термины и предложения являются вершинами, и между каждым членом и каждым предложением, содержащим этот термин, есть грань, то этот график является плоским.Я полагаю, что планарная 3-SAT, вероятно, NP-трудная, потому что планарная 1-в-3-SAT есть, но в противном случае мы можем использовать гаджеты для пересечения сигналов.Но это действительно довольно сложно (если кто-то видит более простой путь, пожалуйста, дайте мне знать), поэтому сначала я собираюсь сделать пример решения планарного 3-SAT с помощью этой системы.
Итак, простой планар 3-SAT проблема будет (x | y | z) & (! X | y |! Z).Очевидно, что это выполнимо, используя любое присвоение, где у истинно, или несколько других назначений.Мы построим нашу проблему с домино следующим образом:
*******
* *
* *
**** ***
* *
*** ****
* *
* *
* ******* *
* * * *
* * * *
*z*x* *****
* *
**** ****
* *
***
***
*
*
*
y
Обратите внимание, что нам пришлось использовать фиддлеры наверху, чтобы правильно расположить вещи в пространстве, иначе это было бы существенно менее сложно.
Суммируя общее количество домино из гаджетов и путей, мы получаем 1 сплиттер (5 домино), два фиддлера (по 2 домино в каждом) и в общей сложности 13 регулярных путей, что в сумме гарантирует 5 + 2 * 2 + 13 = 22 домино, даже если пункты не могут быть выполнены.Если это так, то у нас будет еще 2 домино, которые можно заполнить в общей сложности 24. Одна оптимальная упаковка с 24 домино выглядит следующим образом:
QRRRSSS
Q T
Q T
OPPP *UT
O U
*ON UVVV
N W
N W
M IIIJJJK W
M H K X
M H K X
*zGH* LLLX*
G *
GEEE FFF*
B D
BCD
BCD
C
A
A
A
Этот лист содержит 24 домино, поэтому мы можем знать, что исходное выражение выполнимо. В этом случае лист соответствует тому, чтобы сделать y и x истинными, а z ложными. Обратите внимание, что это не единственная мозаика (и не единственное удовлетворяющее присвоение логических значений), но что нет другой мозаики, которая увеличит количество плиток за пределами 24, поэтому это максимальная мозаика. (Если вы не хотите считать все домино, вы можете заметить, что я использовал каждую букву, кроме Y и Z.)
Если бы максимальный тайлинг содержал 22 или 23 домино, то мы бы знали, что одно из условий не было выполнено (домино GGG и / или LLL не могли быть размещены), и, следовательно, мы знали бы, что оригинал выражение не было удовлетворительным.
Чтобы быть уверенным в том, что мы можем сделать это, даже если планарная 3-SAT не является NP-трудной, мы можем создать гаджет, позволяющий пересекать пути. Этот гаджет, к сожалению, довольно большой и сложный, но он самый маленький, который мне удалось выяснить. Сначала я опишу кусочки, а затем весь гаджет.
Часть 1: Точка кроссовера. х и у - входные данные. a, b и c являются выходами. Их нужно будет объединить с помощью других гаджетов, чтобы фактически перевести x и y в противоположную сторону друг от друга.
***c
*
***
* *
* *
* *
***
***
ax*yb
Этот гаджет всегда будет соответствовать ровно 7 домино. Существует четыре возможных комбинации ввода. Если ни один из входных значений не выступает (оба значения верны), то ни один из выходных данных не будет выступать, и он будет заполнен, как в (tt1) или (tt2) ниже. Если только вход x выступает, то только c будет выступать, как в (футах) ниже. Если только вход y выступает, то либо выход a, либо c будет выступать, как в (tf) ниже. И если входные x и y выступают, выходной c выступает, как показано в (ff) ниже.
(tt) AAAc (ft) AAAc (tf) AAAc (ff) BAAA
* * * B
BBB BBB BBB CBD
C D C D C D C D
C D C D C D C D
C D C D C D E G
EEE EEE EEE EFG
FFF FFF FFF EFG
aGGGb aXGGG GGGYb aXFYb
Я не включил возможность того, что в (футах) или (tf) сценарии могут быть охвачены c вместо a или b. Это возможно в рамках этого гаджета, но, будучи объединенным с другими гаджетами для формирования полного кроссовера, в противном случае это никогда не приведет к удовлетворению большего количества предложений, поэтому мы можем исключить его. Имея это в виду, мы можем наблюдать, что в этом случае значение входа x равно значению b & c, а вход y равен значению a & c (обратите внимание, что это было бы логично или, скорее, чем логично, и если выступ считался верным, а не ложным). Так что нам просто нужно разделить c, а затем использовать логические и гаджет для соединения значений c с a и b соответственно, и тогда мы успешно завершим наш переход.
Логично, и это наш самый простой гаджет на сегодняшний день, и он выглядит так:
****
*
x*y
Вы можете заметить, что один из них встроен в верхнюю часть гаджета точки пересечения. Этот гаджет всегда будет содержать ровно 2 домино. Один будет наверху, чтобы служить выходом. Другой служит переключателем, который будет горизонтально ориентирован, только если оба x и y верны (не выступающие) и вертикально ориентированы в противном случае, как мы можем видеть на следующих диаграммах:
BBB* ABBB ABBB ABBB
* A A A
AAA XAy xAY XAY
Таким образом, мы можем завершить пересечение, разделив c, а затем добавив два из этих ворот, один для a & c и один для b & c. Для того, чтобы собрать все это вместе, нужно также добавить несколько гаджетов Fiddler и выглядеть так:
******* ****
* * * *
* *** *
*** *** ***
* * *
**** * ****
* * *
* **** *
*** * ***
* *** *
**** * * ****
y * * * * x
* * * * * *
* **** *** **** *
*** *** ***
**********x*y*************
Я не собираюсь заполнять примеры для этого. Вам придется сделать это самостоятельно, если вы хотите увидеть это в действии. Итак, ура! Теперь мы можем сделать произвольный 3-SAT. Я должен уделить минутку, чтобы отметить, что это будет полиномиальное преобразование времени, потому что даже в худшем случае мы можем просто создать большую сетку со всеми переменными и их противоположностями вдоль вершины и всеми терминами на стороне O (n ^ 2) кроссоверы. Таким образом, существует простой алгоритм с полиномиальным временем для выкладывания всего этого, и максимальный размер преобразованной задачи является полиномиальным по размеру входной задачи. Что и требовалось доказать.
Редактировать заметку:После превосходной работы Тома Сиргедаса по поиску ошибки в гаджете сплиттера я внес некоторые изменения в ответ. По сути, мой старый сплиттер выглядел следующим образом и мог быть упакован с 6, когда х не выступает (а не 5, как я задумал), вот так:
y*** ***z AAAC DBBB
* * C D
*** C*D
*** EEE
*x* FFF
Так что я пересмотрел его, удалив два пробела по обе стороны от x. Это исключает упаковку из шести домино, в то же время позволяя упаковку из 5 домино, в которой y и z раскрыты, когда х не обнаружен.