3

游戏链接在这里： 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”吗？先感谢您。

4

2 回答 2

0

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

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

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

请注意，这种启发式方法的信息量并不多，即它会让您在收敛到解决方案之前扩展许多状态。

于 2013-09-28T16:04:38.093 回答
0

我已经为这个游戏实现了一个人工智能，它根据上述贪心算法工作。特别是，它试图最大化从 (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.选择集群最大的副本（和相应的颜色）

尽管这是一个幼稚的实现，但它确实表现良好。

亲切的问候，乔里斯

于 2015-08-16T11:52:59.243 回答