Обобщение алгоритма домино-черепицы?

Ответ 1

Эта проблема, безусловно, NP-hard, и я могу это доказать. С этой проблемой происходит сокращение от 3-SAT. В частности, это сокращение от 3-SAT к подзадаче этой проблемы, в которой домино 1x3. Могут также быть другие сокращения для других конкретных размеров, но это определенно работает.

По сути, в этом сокращении мы будем использовать позиции домино, чтобы кодировать либо true, либо false. В частности, я собираюсь принять то же обозначение, что и другое решение, то есть сказать, что я буду использовать звездочки, чтобы указать открытые пространства в сетке. Я также буду использовать наборы из трех заглавных букв для представления домино и строчных букв для представления "сигналов", которые являются пробелами, которые могут заполняться или не заполняться в зависимости от состояния системы.

Чтобы внедрить проблему 3-SAT в это пространство, нам понадобится набор того, что я буду называть гаджетами, которые позволяют использовать только определенные состояния. Большинство этих гаджетов будут иметь фиксированное количество домино в них. Исключением будут гаджеты, которые представляют предложения, которые будут иметь один дополнительный домино, если предложение истинно (выполнено), но не тогда, когда оно ложно (неудовлетворено). Мы можем связать эти гаджеты с помощью путей. Вместе это позволит нам построить схему 3-SAT. У нас будет базовое число домино, так как каждый путь и гаджет будут принимать стандартное количество домино, мы можем добавить их, чтобы получить базовое число k, а затем каждый гаджет предложения может иметь один дополнительный домино, если он истинен, поэтому, если все (и, следовательно, выражение удовлетворено), и есть n предложений, тогда максимальное число домино будет n + k. Если нет, то максимальное число будет меньше n + k. Это основная форма сокращения. Далее я опишу гаджеты и приведу примеры.

Как и в другом ответе, мы будем иметь две позиции, которые кодируют true и false для данной переменной. Итак, я начну с одной плитки, которая может быть в двух возможных местах.

****

Это может быть покрыто одним домино, например

AAA* or *AAA

Очевидно, что это не может быть покрыто двумя домино и покрыть его 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 домино. Если х торчит, чем упаковка, 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

Я займу минутку, чтобы отметить, что можно будет упаковать это с пятью домино, когда х не будет выступать таким образом, чтобы либо 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). Очевидно, что это выполнимо, используя любое присваивание, где y истинно или несколько других назначений. Таким образом мы построим нашу проблему с домино:

    *******
    *     *
    *     *
 ****   ***
 *       *
***      ****
  *         *
  *         *        
  * ******* *
  * *     * *
  * *     * *
 *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 true и z false. Обратите внимание, что это не единственное мозаичное (а не единственное удовлетворительное назначение булевых значений), но нет другого тайлирования, которое увеличит количество фрагментов за пределами 24, поэтому это максимальная разбивка. (Если вы не хотите считать все домино, вы можете заметить, что я использовал каждую букву, кроме Y и Z.)

Если максимальная черепица содержала 22 или 23 домино, то мы знали бы, что одно из предложений не было выполнено (GGG и/или LLL-домино не могли быть размещены), и, следовательно, мы знали бы, что оригинал выражение не было выполнено.

Чтобы быть уверенным, что мы можем это сделать, даже если плоский 3-SAT не является NP-жестким, мы можем создать гаджет, который позволяет пересекать пути. Этот гаджет, к сожалению, очень большой и сложный, но это самый маленький, который я смог выяснить. Сначала я опишу фрагменты, а затем весь гаджет.

Часть 1: точка кроссовера. x и y - входы. a, b и c - выходы. Они должны быть объединены с использованием других гаджетов, чтобы фактически передавать x и y на противоположную сторону друг от друга.

   ***c
   *
  ***
  * *
  * *
  * *
  ***
  ***
 ax*yb

Этот гаджет всегда будет соответствовать ровно 7 домино. Существует четыре возможных комбинаций ввода. Если ни один вход не выступает (оба являются истинными), ни один выход не будет выступать, и он будет заполнен, как показано ниже (tt1) или (tt2). Если выдается только вход x, тогда будет выступать только c, как в (ft) ниже. Если выдается только вход 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      

Я не включил возможность того, что в сценариях (ft) или (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. Объединение всего этого требует также добавления некоторых гаджетов скрипача и выглядит так:

             ******* ****
             *     * *  *
             *     ***  *
            ***    *** ***
              *     *  *
           ****     *  ****
           *        *     *
           *     ****     *
          ***    *       ***
            *   ***      *
         ****   * *      ****
    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 раскрываются при обнаружении x.

Ответ 2

К Кейту:

Отличная работа и отличные объяснения! Хотя, я написал программу, чтобы найти максимальные тилинги, и она обнаружила недостаток. Надеюсь, это можно исправить! [Обновление: Кейт исправил проблему!]

Пожалуйста, ознакомьтесь с этой ссылкой: http://pastebin.com/bABQmfyX (проанализированы ваши гаджеты, а также очень удобный исходный код С++)

Проблема в том, что гаджет ниже может быть разбит на 6 домино:

y*** ***z
   * *
   ***
   ***
   *x*

-Tom Sirgedas

Ответ 3

Действительно хороший вопрос. Эта проблема эквивалентна поиску максимального независимого множества размера (или максимального размера клики) на специальном графике - вершины будут всевозможными позициями прямоугольника MxN, и ребра будут соединять две позиции, если они сталкиваются. Тогда найти размер максимального независимого множества дает результат. Или наоборот, мы могли бы определить край как соединение двух позиций, которые не сталкиваются, тогда мы будем искать максимальный размер клики. Во всяком случае, ни один граф не является ни свободным, ни совершенным, поэтому мы не можем использовать полиномиальные решения для нахождения максимального независимого набора/клики.

Итак, мы могли бы попытаться преобразовать максимальную независимую задачу набора в эту проблему с разбивкой, но я не смог найти способ преобразования общего графика в это, потому что вы не можете преобразовать, например. индуцированный фрагмент K _1,5 для фрагментов.

Ответ 4

1x3 плитки трудны благодаря сокращению от кубического планарного монотона Один-три-три 3SAT. Мы должны построить некоторую "схему" для кодирования формулы.

"Gates":

X********Y

Направляет ровно один из X и Y, который должен быть закрыт извне. Используется для связывания переменной и ее отрицания.

Y***
   *
   *
  ooo  ****
  * *  *  *
  * *  *  *
  X ****  Z

Заставляет всех или всех X и Y и Z скрываться снаружи. Используется для копирования X или уничтожения трех копий одной и той же вещи. Провода могут иметь форму более или менее произвольно, используя длины длиной 3 л.

*******************
*        *        *
*        *        *
X        Y        Z

Направляет ровно один из X и Y и Z на внешнее. Один для каждого предложения.

Ответ 5

Первое, что я хотел бы сделать, это сделать третье состояние: "пустое, но недостижимое". Вы можете легко доказать, что каждая плитка недоступна в l * w * m * n времени (где l - длина мира, w - ширина мира, а m и n - размеры плитки). Это уменьшит ваше пространство таким образом, чтобы любая пустая плитка достижима. Обратите внимание, что у вас могут быть острова доступной плитки. Простейшим примером этого является то, что мир сокращается наполовину. Это поддается рекурсивному усилию, когда каждый остров достижимости воспринимается как мир сам по себе.

Теперь, когда мы имеем дело с островом (который может быть или не быть квадратным), у вас по существу есть специальный случай проблемы двускатного рюкзака, который, как известно, является NP-hard (цитата в разделе Предыдущая работа). Ваше усложняет проблему, добавляя фиксированные позиции в рюкзак, который всегда заполняется, но уменьшает сложность (слегка), делая все пакеты одинакового размера.