19

建议解决游戏 Globs 的算法和数据结构 ( http://www.deadwhale.com/play.php?game=131 )。它以一种极客的方式非常有趣。

用 N 表示您的方法的时空复杂度 (big-O)，即网格的大小 (N>=14)。具有低复杂性的足够好的有效算法是首选。

（MatrixFrog 正确地指出这个游戏也被称为 FloodIt，并且 Smashery 在 3 个月前在他引用的链接中给出了一个解决方案。你们所有的家伙都建议修剪/贪婪只有 1 个前瞻，这给出了次优的解决方案。）

游戏生成一个由 nxn 个节点组成的随机方形网格，其中每个节点的颜色为六种颜色之一（Grn=1、Ylw=2、Red=3、Blu=4、Pur=5、Orn=6）。级别 1 有 9x9 网格，然后每个级别增加 n，最多 14 个。每个级别您最多可以进行 25 回合，否则您将失败。在每一回合中，您选择将左上角节点更改为例如 Grn->Red 的颜色，这样新颜色的任何连接的相邻（水平/垂直）节点都被同化为一个形状，并且每个同化节点增加 1 pt你的分数。计分目标是在尽可能少的回合内完成每个网格，例如，如果您在 16 回合内完成，那么您的 9 个未使用的动作 => 2*9 乘以您的总得分。

显然有很多方法可以分解它，默认选择 14x14 网格的递归回溯是一个可行的竞争者；这适用于哪些其他类型的数据结构？一种* ？不要挂在最优性上，我想知道是否有一个“足够好”的算法。

（我认为编写一个机器人并获得愚蠢的高分可能是一个有趣的项目。虽然我的肉件自己获得了 3.5E+12。）

4

7 回答 7

5

这个游戏真的引起了我的兴趣，所以我花了几天的时间来研究它。

我注意到的第一件事是，很容易证明在第一局（在某些情况下可能是 2 局）之后，提高分数的最快方法是使用乘数。正因为如此，我建立了一个系统，目标是用最少的步骤解决每个板。我开始想使用 A*，因为它通常是为这些类型的搜索问题而构建的……但是，这个问题仍然是一个问题。

在谈论 A* 时，它的有效性确实归结为您对启发式估计的选择。您越接近猜测实际距离，为达到目标而必须扩展的节点就越少。对于这个问题，我经历了很多估计的想法，但大多数都违反了 A* 规则，即不能高估实际距离，否则会破坏 A* 的最优性。

然而，有一些工作。该线程中的其他人发布了关于仅将剩余颜色的数量作为估计值的帖子，这是可以接受的，因为它不能高估（对于不属于主要“洪水”区域的每种剩余颜色，您必须至少更改一次颜色。这种启发式的问题是它对实际距离的估计很差。以第一步为例，它通常对颜色数量进行估计，为 6。它通常会扩展为 2 步，每个步通常估计为 7 ，依此类推。以这 5 个级别为深度，对于 10x10 的棋盘大小，大多数叶子的估计值为 11。这种启发式方法基本上是广度优先搜索的一种实现，直到您在 4 或 5 步内到达目标。这不是很有效，在我自己的测试中，指数在棋盘大小 9 附近运行，这通常需要在解决方案中进行大约 14 次移动。应该注意的是，我的解决方案是非常高级的，但是并没有很注意加快速度。

问题是 A* 只有在每一步都对整体解决方案的实际距离进行显着改进时才真正有效。直接看问题，你可能不会找到一个很好的启发式方法，它可以做得比这更好，而不会高估成本。但是，如果您将问题转化为另一个问题，则更好的启发式方法会突然出现。启发式“剩余颜色数”正在回答这个问题，剩余的最小可能移动数是多少。为了回答这个问题，我问自己“黑板上的哪个位置需要最多的步数才能到达”？对于我的启发式方法，我最终确定了“到右下角有多少步”的答案。这很容易通过运行另一个 A* 搜索来实现，该搜索更像是查找地图方向，然后计算解决方案中的步数。我意识到这是板上的任意点可供选择，但是它在测试中运行良好，并且在每个剩余点上运行 A* 在我的单处理器测试机器上花费了相当多的时间。

然而，在右下角成为泛滥区域的一部分后，仅此启发式就有崩溃的趋势，因此最终结果是 MAX（右下角最小步长，剩余的颜色数量不属于主泛滥的一部分）。通过我的高级实现，这终于能够在一秒钟内实现一些非常大的电路板尺寸。

我将把记录设置留给你。

于 2010-01-12T18:53:59.107 回答
1

鉴于固定的起始状态和有限的移动次数，我认为您可以充分探索决策树。对于每一轮，只有 5 种可能的移动和浪费的移动（选择一种不会“覆盖”任何邻居的颜色）可以在构建树时消除。一旦构建了决策树，我认为您可以探索每条路径的点值，但如果您需要更多优化，A* 肯定会让您接近。

对于每一轮，我将基本状态作为未全局位置状态的位数组矩阵（因为颜色在全局位置中不再重要，您可以通过省略颜色位来节省状态数据结构的内存）以及每个可能的决定的分值。然后您的 A* 或广度优先算法可以正常最大化路径值。保存路径，分析完成后，进行所有确定的移动。

于 2009-12-31T19:18:24.947 回答
1

另一种方法是使用遗传算法。由于任何（部分）解决方案都包含一系列颜色，因此它可以很好地转化为基因。适应度函数可以是连接分量的 4 倍减去使用的颜色总数（基因长度）。

我在 Mathematica 的 10x10 板上尝试了这个，使用了一个非常未优化的算法，并很快得到了一个简短的解决方案。我并不声称它是最优的，但只要有足够的时间，基因突变过程中的随机性将确保你最终得到最优解。

于 2011-09-26T20:04:00.413 回答
0
  1. 如果可以，消除一种颜色。
  2. 选择为您生成更多新邻居的颜色！
  3. 转到步骤 1。
于 2009-12-29T05:55:58.110 回答
0

蛮力递归搜索将找到最高分。您最多需要考虑 5^25 个结束状态。许多中间状态将是等价的；识别这些并修剪重复的搜索空间可能会更快。跟踪搜索时找到的最高分数，以及到达那里的路径（移动序列）。

于 2009-12-30T14:13:48.083 回答
0

一个好的启发式方法是生成颜色连接的距离图。例如，当前洪水的距离为零。一组颜色连接到距离为“i”的正方形，距离为“i+1”。

接下来，观察最大距离处有多少种颜色。我们需要最大距离移动来消除最大距离处的一种颜色，并且我们需要额外移动来消除最大距离处的每种额外颜色。如果所有颜色都不在最大距离处，则考虑之前距离处尚未消除的颜色。我们可能会在进行“最大距离”移动时消除这些颜色中的一种，但我们需要移动来消除每种额外的颜色。

这提供了一个相当好的估计。在最初的 14x14 棋盘位置上，我倾向于估计 17 到 18 步，而需要 20 到 22 步才能获得最佳解决方案。一个 14x14 的棋盘通常可以通过这个下限求解，同时查看大约 10,000 个棋盘位置。（如果这样的移动可用，则使用消除颜色的移动的优化。）

于 2013-09-16T10:01:02.227 回答
0

另一个优化是有一些颜色斑点不需要马上被取走。网络距离图中可能有叶子，其中一个颜色 blob 没有进一步的邻居。直到最远的相同颜色的 blob 才需要获取此颜色 blob。使用这种方法，我们可以调整距离图以获得必须采用颜色斑点的最短时间。

对于某些棋盘位置，我们将能够表明在下一回合不需要采用符合条件的颜色。我们可以避免这种颜色并减少分支因子。

于 2015-05-01T09:25:10.157 回答