python - 一种尝试无反馈分组的算法

Question

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

我将以图形方式进行解释，答案也可以是图形/理论的(也许是发错网站了？)

假设我想制作一个算法来解决一个简单的婴儿数字游戏(这不是实际情况，它要复杂得多)

规则如下:

• 从上面看有一个方形网格，中间有一个彩色乐高积木每个点

• 您可以拖动碎片来尝试堆叠在一起。

• 如果他们的颜色匹配，他们将堆叠，留下第一个的位置你拖空的一 block 。

• 如果你把一个棋子移到一个空位，它也会移动到那个位

• 如果它们的颜色不匹配并且您将一个拖到另一个的顶部，它们会换位置。

• 相同颜色的棋子数量在新的格子开始时随机生成。

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

现在问题来了，我想制作一个解决游戏的脚本，但它将是“盲目的”，这意味着它无法看到颜色，也无法跟踪匹配发生的时间。它必须以一种确保尝试所有可能的“阻力”的方式遍历

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

还有这个复杂度是可以计算的吗？是不是太疯狂了？

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 列保证为空。

行缩减

现在我们对列重复相同的过程，即对于所有 j >= n-p，将 (1, j) 拖到 (m, j)，然后将 (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，列和行的减少将大大降低实际的复杂性。