解决拼图难题的高效算法是什么？

Question

12

昨天我只是在玩拼图游戏，突然想到了解决这个问题的算法。

作为人类，我遵循以下步骤：

我在想，哪种高效的算法可以更有效地解决这个拼图难题，以及使用什么数据结构会提供最优的高效解决方案。

谢谢。

- Rachel

我想到的是创建一个大小与谜题相等的零矩阵。然后将第一个元素放在零矩阵上的任何一个位置。接着取下一个元素，并检查它是否适合放在矩阵中现有块的任一侧。 - Jdeep

三角插值使用FFT经常被考古学家用于重新组装碎片化的文物。此外，使用卷积处理图像可能会降低问题的复杂性。（还要注意算法的设计高度依赖于您拼图的数字副本的质量。） - Lucas Aschenbach

5个回答

4

请确保扫描每个部分的男/女性--这将减少搜索量一半。

- nedblorf

但如果拼图块只是普通的正方形呢？ - Jdeep

3

假设您不会涉及到任何计算机视觉内容，那么解决整个问题空间的方法是对每个拼图块进行尝试，直到找到符合要求的为止，并不断重复这个过程。主要的优化在于，如果您知道某个拼图块不适合某个位置，则不要在同一位置再次尝试该拼图块。边/角拼图块占据了相对较少的拼图块数量，可能无法被视为任何主要优化的考虑因素。

数据结构可能类似于哈希矩阵，您可以快速检查是否已经在某个位置尝试过某个拼图块。

一个简单的包含计算机视觉的优化方法是，通过按照平均颜色与相邻位置匹配程度的接近程度对拼图块进行排序后，在每个位置尝试拼图块。

当然，这只是我脑海中的一些想法。

- Kenan Banks

3

我不认为以人类的方式去实现会很有帮助-计算机可以每秒查看所有块多次，而将块分成角落、边缘和内部块并没有（大）优势，特别是因为它们只有三个类别且大小差异很大。

给定一组所有块的图像，我会尝试为每个块或边推导出一个简单的描述符。描述符必须包含关于块的粗略形状和颜色的信息，或者四条边各自的信息。给定一个由1000个块组成的拼图，共有4000个边，且总有两个相等（忽略拼图的边框）。因此，描述符必须能够区分2000个边，需要至少11位。

将一个块分成3 x 3的棋盘格模式，并赋予每个边三种颜色-每通道8位，我们已经有72位。我最初倾向于建议减少颜色分辨率，但这似乎不是一个好主意-例如，蓝天可能真正受益于高颜色分辨率。请注意，计算颜色可能需要将块从背景中分离出来，并尝试将边与水平和垂直轴对齐。

在非常均匀的区域，比如蓝天，颜色信息可能不足以找到良好的匹配，需要额外的几何信息。我会尝试通过其曲率或导出的度量来描述边缘的形状。也许每个边缘采样十到二十个点。这可能又依赖于背景分离和边缘对齐。

最后，计算机可以做简单的部分-比较所有边缘描述符并找到最佳匹配。这个过程应该控制得更加本地化，而不是简单的最佳匹配，因为每当你找到一个角落（正确的英语词汇？我的意思是L形状的三个部分），你就有两个边缘约束要查找，并且如果找不到好的匹配，就可以提前回溯（表示之前的错误或难题）。

- Daniel Brückner

1

在这个问题上，我想到了一个有趣的解决方案，可以通过一系列步骤逐渐增加成本来解决它。

将所有拼图分成两组。测试它们是否能够拼合在一起。如果不能，尝试另一块之前未见过的拼图。如果可以，将该组放入正确的堆中。重复此步骤，直到所有的拼图都被匹配成一对。
从正确的堆中组合成两组拼图的集合，即{{1,2},{5,6}}。看看其中至少一块拼图是否与另一组中的至少一块拼图相匹配。如果不是，请尝试之前未见过的其他组合。如果是，则将两组合并为一组四个拼图，以正确的方向放置，并将其放入正确的堆中。重复此步骤，直到所有的四个拼图都被找到。
重复以上步骤，直到最后一个问题，即第n/2组与第n/2组相结合。

不确定这个计算时间会是多少。

- Masa Hu

我认为步骤1并不能保证所有的拼图都能成对。我们来看一个简单的1*4拼图，比如A-B-C-D。如果你用{B,C}和{A,D}创建集合，第一个集合会匹配，但第二个集合不会。 - thanos.a

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- LBushkin · Accepted Answer

解决这类问题可能会具有欺骗性的复杂性，特别是如果没有对谜题的大小和复杂度施加任何限制时。

以下是我对编写解决此类谜题的程序方法的思考。

有四个关键信息可以单独或结合使用作为拼图谜题的线索：

1. 每个拼图块的形状信息（它们的边缘如何出现） 2. 每个拼图块的颜色信息（相邻的块通常具有平滑的过渡） 3. 每个块的方向信息（平坦和角边缘可能位于哪里） 4. 整体尺寸和碎片数量提供了谜题的一般尺寸

那么程序将提供什么样的信息-假设每个拼图块都是带有透明度信息的小矩形图像，用于识别表示非矩形边缘的拼图块部分。

从这里开始，相对容易地识别出四个角落的拼图块（在典型的拼图中）。这些块将具有恰好两个具有平坦轮廓的边缘（请参见下面的轮廓图）。

接下来，我将建立关于每个拼图块四边形状的信息。这些信息可以用来构建一个相邻矩阵，表明哪些拼图块能够拼接在一起。

现在，我们可以修剪此相邻矩阵，以仅识别在相邻配置中具有平滑颜色过渡的拼图块。这有点棘手，因为它需要一定程度的模糊匹配 - 因为不是每个像素到像素的边界都必然具有平滑的颜色过渡。

使用最初识别出的四个角落拼图块，我们现在应该能够重构拼图块的所有尺寸和位置。

表示边缘形状的方便数据结构可能是等高线图 - 基本上是一组整数，表示从拼图块四边中的最后一个非透明像素到图像对面的距离的增量。匹配的拼图块应具有镜像等高线图。