tem*_*def 25 puzzle algorithm tiling
在此早期的问题中,OP询问了以下问题:
给定一个矩形网格,其中一些正方形是空的,有些正方形被填充,可以放入世界的最大数量的2x1多米诺骨牌是这样的,没有两个多米诺骨牌重叠,没有多米诺骨牌在填充的正方形上面？
(相当漂亮!)这个问题的答案认识到这相当于在特殊构造的图中找到最大的二分匹配.在此图中,每个空方块都有一个节点,该节点通过边链接到每个邻居.然后,每个多米诺骨牌对应于图中的边缘,使得其端点不被任何其他边缘覆盖.因此,不共享顶点(匹配)的任何边缘集合对应于多米诺骨牌的排列,反之亦然.
我的问题是对前一个问题的概括:
给定一个矩形网格,其中一些正方形是空的而一些是填充的,那么可以放入世界的M x N多米诺骨牌(对于给定的M和N)的最大数量是这样的,没有两个多米诺骨牌重叠并且没有多米诺骨牌在顶上一个满满的广场？
我无法看到如何将其转换为匹配问题,如前一种情况所做的那样.但是,我也没有看到为什么这个问题会立即成为NP难的特殊原因,因此可能存在一个多项式时间解决问题的方法.
有没有一种有效的算法来解决这个问题？或者是否有人有减少表明这个问题是NP难？
非常感谢!
Kei*_*win 18
这个问题肯定是NP难的,我可以证明这一点.从3-SAT到这个问题有所减少.具体来说,它是从3-SAT减少到这个问题的子问题,其中多米诺骨牌是1x3.对于其他特定尺寸可能还有其他减少,但这个肯定有效.
从本质上讲,在这种减少中,我们将使用多米诺位置来编码真或假.具体来说,我将采用与其他解决方案相同的符号,也就是说我将使用星号来指示网格上的开放空间.我还将使用三个大写字母组来表示多米诺骨牌和小写字母来表示"信号",这些信号是根据系统状态可能填充或不填充的空格.
为了将3-SAT问题嵌入到这个空间中,我们需要一套我称之为小工具的东西,这些小工具只允许某些状态.这些小工具中的大部分将具有固定数量的多米诺骨牌.例外情况是代表子句的小工具,如果子句为真(满足),则会有一个额外的多米诺骨牌,但是当它是假的(不满足)时则不会.我们可以使用路径互连这些小工具.这将使我们能够构建一个3-SAT电路.我们将有一个多米诺骨牌的基数,因为每个路径和小工具将采用标准数量的多米诺骨牌,我们可以添加这些以获得基数k然后每个子句小工具可以有一个额外的多米诺骨牌如果它是真的,所以如果所有条款可以成为真(因此满足表达式)并且有n个子句,那么多米诺骨牌的最大数量将是n + k.如果不是,则最大数量将小于n + k.这是减少的基本形式.接下来,我将介绍这些小工具并举例说明.
与其他答案类似,我们将有两个位置,对给定变量编码true和false.所以,我将从一个瓷砖开始,可以在两个可能的位置.
****
这可以用一个多米诺骨牌覆盖
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).显然,这是可以满足的,使用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个多米诺骨牌,所以我们可以知道原始表达是可以满足的.在这种情况下,平铺对应于make 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)交叉.因此,存在一种简单的多项式时间算法,用于完全解决这个问题,并且转换问题的最大大小是输入问题大小的多项式.QED.
编辑说明:在Tom Sirgedas在拆分器小工具中发现错误的出色工作后,我对答案进行了一些修改.基本上,我的旧拆分器看起来像这样,当x没有突出时(而不是我想要的5个)可以用6包装:
y*** ***z AAAC DBBB
* * C D
*** C*D
*** EEE
*x* FFF
所以我通过删除x两侧的两个空格来修改它.这消除了六个多米诺骨牌填充,同时仍允许5-dinoino填充,其中当x未被覆盖时y和z未被覆盖.