洪水填充游戏算法

Question

游戏链接在这里：http://floodit.appspot.com/ 规则很简单，你必须从相邻的颜色中选择一种，起点是左上角，然后颜色会改变，你就可以淹没更多的区域。目标是淹没整个网格。

有一些关于这个游戏的主题在stackoverflow上，但我找不到答案。我的目标是获得淹没整个网格的最佳方法。现在我处于这个位置：

我正在尝试通过A*解决这个问题。我的启发式是选择颜色，使距离最远组件（在这种情况下，红色的2、4、1、3是最远的）最小化，并且如果几种颜色最小化到达其中一个最远的组件的距离，则选择具有最多点数的颜色（在这种情况下，我的算法选择“0”，因为它最小化了到所有最远节点的距离，并且在其中有更多的点数，比如“2”）。

我的老师给了我们最优解，而在这种情况下他的最佳方式是：2, 0, 1, 4 ,3, 2, 5；需要多7个单位。但根据我的启发式，我选择“0”，最佳方式是：0, 2, 4, 5, 3, 1, 0, 2, 4；需要多9个单位。有人能回答我，在这种情况下我必须选择“2”而不是“0”的启发式吗？

谢谢您提前的帮助。

- Giorgi Margiani

---

为什么不直接使用蛮力法呢？只有六种颜色，所以如果最优解的长度是八，那只需尝试1.6百万次，还是很可行的。不过，我猜如果你碰到超过十一次或十二次的解决方案，你可能就没那么幸运了。 - kevmo314

你的问题公式中最佳路径是什么？是选择次数最少的路径吗？ - rano

Answer 1

我想你可能将A*算法与简单的贪婪最佳优先搜索混淆了，其中只需计算启发式函数h(n)，该函数以某种方式估计当前状态到目标状态的成本（或距离）。

在A*中，您正在扩展最小化函数f(n) = g(n) + h(n)的节点，其中g(n)提供从起点到当前状态的（路径）成本（请记住，A*可以在找到最佳解之前探索多个方向的状态图）。

在您的情况下，我可以想象g(n)可以等于从根状态开始的路径长度，因为您对最短路径感兴趣（每个新状态的成本都是1）。为了找到最优路径，A*的h(n)不能高估最优解。出于这个原因，一个想法是使用表格中剩余颜色的数量来计算它（实际上，您始终需要至少这么多步才能达到完全着色的最终状态）。

请注意，这种启发式方法并不是非常信息丰富的，也就是说，在收敛到解决方案之前，您需要扩展许多状态。

- rano

Answer 2

我已经为这个游戏实现了一个AI，它根据前面提到的贪心算法工作。特别地，它试图最大化从(0,0)开始形成簇的单元格数。

首先，我们定义一种方法来计算一组相邻且颜色相同的点，我们称之为簇。

def cluster(self, x, y):

    # setup return value
    retval = sets.Set([])

    # stack
    col = self._grid[x][y]
    stk = []
    stk.append((x,y))

    while len(stk) > 0:
        curr = stk.pop()
        retval.add(curr)
        c_x = curr[0]
        c_y = curr[1]

        nbs = [(c_x,c_y+1),(c_x,c_y-1),(c_x+1,c_y),(c_x-1,c_y)]
        for n in nbs:
            if n[0] < self._width and n[0] >=0 and n[1] < self._height and n[1] >= 0:
                if self._grid[n[0]][n[1]] == col and not (n in retval):
                    stk.append(n)   
    # return
    return retval

然后我们可以将泛洪网格定义为简单地取（0,0）的群集并使用新颜色标记这些单元。

    def flood(self, x, y, c):
    pts = self.cluster(x,y)
    for p in pts:
        self._grid[p[0]][p[1]] = c

可以使用简单 (贪婪) 策略来实现:

    def easy_strategy(self):

    retval = []
    g = copy.deepcopy(self)
    c = g.cluster(0,0)
    S = g._width * g._height

    # continue until all cells have the same color
    while len(c) != S :

        # attempt all flood options
        cps = []
        for i in xrange(0, self._num_colors+1):
            cps.append(copy.deepcopy(g))
        csz = [0 for i in xrange(0, self._num_colors+1)]
        for i in xrange(0,self._num_colors+1):
            cps[i].flood(0,0,i)
            csz[i] = len(cps[i].cluster(0,0))

        # best move     
        max_index = csz.index(np.max(csz))                                  
        g = cps[max_index]
        c = g.cluster(0,0)

        # append to array
        retval.append(max_index)

    # return
    return retval

这实际上是做以下事情: 1. 将当前网格复制k次 (其中k是颜色的数量) 2. 对每个副本（索引为i）使用颜色i进行泛洪 3. 计算在(0,0)处的簇的大小 4. 选择具有最大簇的副本(和相应的颜色)

虽然这是一个天真的实现，但它表现良好。

此致 敬礼， Joris

- Joris Schellekens