一种无反馈尝试分组算法

Question

将其标记为Python是因为在我看来，Python是最伪y代码的语言

我会以图形化的方式解释，答案也可以是图形化的/理论化的（也许发布这个的网站不对？）你知道吗

假设我想做一个算法，为婴儿解决一个简单的数字游戏（这不是实际的上下文，它要复杂得多）

规则如下：

• 从上面可以看到一个正方形的网格，里面有一块彩色的乐高积木 每个点

• 你可以拖拽一块块试着叠在一起。

• 如果他们的颜色匹配，他们会堆叠，留下第一个斑点 你拖空的那块。

• 如果您将一个工件移动到一个空的位置，它将移动到该位置

• 如果他们的颜色不匹配，你把其中一个拖到另一个上面，他们 将切换点。

• 当一个新的网格启动时，相同颜色的块的数量是随机生成的。

游戏的目标显然是拖动相同颜色的棋子，直到每种颜色只有一堆为止。你知道吗

现在问题来了，我想做一个脚本来解决游戏，但它将是“盲的”，这意味着它将无法看到颜色，或跟踪何时发生匹配。它必须以一种方式穿越，以确保它尝试了所有可能的“拖拽”

我甚至开始思考这个问题的主要问题是，如果脚本猜不出颜色，他们会交换位置，而且没有反馈知道你失败了。你知道吗

这个问题的复杂性也是可以计算的吗？是不是太疯狂了？你知道吗

Answer 1

让我们尝试以下操作：

假设我们有一个m乘以n的网格，有p种不同的颜色。首先，我们使用以下算法逐行工作：

列缩减

1. 将工件从（1,1）拖到（1,2），然后从（1,2）拖到（1,3），依此类推，直到达到（1，n）
2. 以相同的方式将工件从（1，1）拖动到（1，n-1）。你知道吗
3. 继续，直到你达到（1，n-p）与块移动。你知道吗

第一步保证将原来位于（1，1）的颜色移动到（1，n），并在途中收集所有相同颜色的碎片。 接下来的步骤收集剩余的颜色。在这部分算法之后，我们保证只填充p到n列，每个列都有不同的颜色。你知道吗

我们对其余的m-1行重复这个步骤。之后，保证第1列到第n-p-1列为空。你知道吗

行缩减

现在我们对列重复相同的过程，即将（1，j）拖到（m，j）表示所有j>；=n-p，然后将（1，j）拖到（m-1，j）。你知道吗

在这部分之后，我们保证只填充一个p乘以p的子网格。你知道吗

全网格搜索

现在我们用暴力收集每种不同的颜色： 移动（p，p）到（p，p+1），（p，p+2）。。。（p，n）然后到（p+1，n），（p+1，n-1），…，（p+1，p）然后到（p+2，p），…，（p+2，n）等等，直到我们到达（m，p）或（m，n），这取决于p是偶数还是奇数。你知道吗

这一步我们重复p次，只不过每次在距离最后一步不远的地方停下来。你知道吗

因此，只有剩余的p字段被填充，并且每个字段都包含一个相同颜色的堆栈。问题解决了。你知道吗

要估计复杂性：

• 行移动部件需要n+n-1+n-2+。。。+n-p=n*（n+1）/2-（n-p）*（n-p+1）/2=np+（p^2+p）/2=O（n^2）每行移动，因此O（mn^2）。你知道吗
• 柱移动部分同样需要O（nm^2）移动。你知道吗
• 最后的移动需要对每种颜色进行p^2次移动，即O（p^3）。你知道吗

如果q=max（n，m，p），则复杂度为O（q^3）。你知道吗

注意：如果我们不知道p，我们可以立即开始全网格搜索。我们仍然处在复杂性O（q^3）中。但是，如果p<；<；n或p<；<；m，则列和行缩减将大大降低实际复杂性。你知道吗