在为基于平铺的游戏编程随机级别生成器时，我遇到了一个有趣的问题。我已经为它实现了一个强力解算器，但它的速度是指数级的，绝对不适合我的用例。我不一定要寻找一个完美的解决方案，我会满足于一个“足够好”的解决方案，表现良好。
问题陈述：
假设您有以下全部或一个子集可用（这是映射到右、上、左和下方向的所有可能4位模式的组合）：
alt text http://img189.imageshack.us/img189/3713/basetileset.png
提供了一个网格，其中一些单元格被标记为（true），而其他单元格则不被标记为（false）。例如，这可以由perlin噪声算法生成。我们的目标是用瓷砖填充这个空间，这样就有尽可能多的复杂瓷砖。理想情况下，应连接所有瓷砖。对于某些输入值（可用的tiles+pattern），可能没有解决方案。如果左上角的未连接图块可用（即，可以用该图块填充所有图案单元格），则始终至少有一个解决方案。
例子：
从左到右的图像：磁贴可用性（可以使用绿色磁贴，不能使用红色磁贴）、要填充的图案和解决方案
alt text http://img806.imageshack.us/img806/2391/sampletileset.png+alt text http://img841.imageshack.us/img841/7/samplepattern.png=alt text http://img690.imageshack.us/img690/2585/samplesolution.png
我试过的：
我的蛮力实现在任何地方尝试所有可能的平铺，并跟踪找到的解决方案。最后，它选择最大化从每个瓦片输出的连接总数的解决方案。所需时间与模式中的瓷砖数量成指数关系。12块瓷砖的图案需要几秒钟才能解决。
笔记：
正如我所说，表现比完美更重要。但是，最终解决方案必须正确连接（没有指向不指向原始平铺的平铺的平铺）。为了说明范围，我想在2秒钟内处理100个瓷砖的图案。
最佳答案
对于100个瓷砖实例，我相信基于输入图的雕刻分解的动态程序可以满足需求。
雕刻分解
在图论中，图的雕刻分解是其顶点的递归二元划分。例如，这里有一个图表
1--2--3
| |
| |
4--5
它的一个雕刻分解
{1,2,3,4,5}
/ \
{1,4} {2,3,5}
/ \ / \
{1} {4} {2,5} {3}
/ \
{2} {5}.
雕刻分解的宽度是离开它的一个分区的最大数量的边缘。在这种情况下，
{2,5}具有传出边2--1、2--3和5--4，因此宽度为3。10 x 10网格的kd树型分区的宽度为13。图的雕刻宽度是雕刻分解的最小宽度。已知n个顶点的平面图（特别是网格图的子图）具有刻划宽度o（√n），且大o常数相对较小。
动态程序
给定一个n-顶点输入图和一个宽度w的雕刻分解，有一个o（2wn）-时间算法来计算最优瓷砖选择。这个运行时间在w中快速增长，因此您应该尝试手动分解一些示例输入，以了解期望的性能类型。
该算法自下而上对分解树进行处理。设x是一个分区，设f是离开x的边的集合。我们做一个表，在指定的约束条件下，把f中存在或不存在边的2 f可能性中的每一个映射到x上的最优和（如果没有解，则为无穷大）。例如，对于分区
{1,4}，我们有个条目{} -> ??
{1--2} -> ??
{4--5} -> ??
{1--2,4--5} -> ??
对于只有一个顶点的叶分区，f的子集完全决定平铺，因此很容易填充连接数（如果平铺有效）或-无穷大。对于其他分区，在计算表的一个条目时，尝试为两个子分区之间的边使用所有不同的连接模式。
例如，假设我们有碎片
|
. .- .- -. .
|
{1}的表是{} -> 0
{1--2} -> 1
{1--4} -> -Infinity
{1--2,1--4} -> 2
{4}的表是{} -> 0
{1--4} -> 1
{4--5} -> 1
{1--4,4--5} -> -Infinity
现在让我们计算
{1,4}的表。对于{}，如果没有边缘1--4，则{1}（entry{}）的得分为0，而{4}（entry{}）的得分为0。对于edge1--4我们有score-infinity+1=-infinity（entries{1--4}）。{} -> 0
对于
{1--2}，分数为1+0=1（无1--4）和2+1=3（有）。{1--2} -> 3
持续的。
{4--5} -> 0 + 1 = 1 (> -Infinity = -Infinity + (-Infinity))
{1--2,4--5} -> 1 + 1 = 2 (> -Infinity = 2 + (-Infinity))
最后我们可以用这些表来确定一个最优解。
找到雕刻分解
有复杂的算法可以找到好的雕刻分解，但您可能不需要它们。尝试一个简单的二进制空间分区方案。