寻找解决彩色水分类游戏的最短路径

Question

于是我阿姨就玩这款现在很流行的手机游戏，如下图所示。她卡在某个关卡上，问我是否可以解决。知道我不够聪明，无法找到解决问题的模式或策略，并且只了解 Python 的基础知识，我认为我应该尝试通过编写脚本来解决它，这是学习新东西的绝佳机会，我开始了为期两周的旅程。

游戏由多个瓶子组成，里面装满了层层不同颜色的瓶子，一般还有一到两个空瓶子，目标是让所有瓶子颜色统一。一个动作包括将一个瓶子至少装满一层并将其倒入另一个瓶子中。主要规则是您可以在空瓶子中倒入任何颜色，并且只有在颜色相同的情况下才可以将一层倒入另一层上。

我解决这个问题的第一个方法是创建一个新的class bottle，实现其中的所有规则，这意味着因为我只知道基础知识，所以花了我很多时间而且它确实没有优化（我不了解堆栈）并且必须写下这么多if.. elif.. else语句来指定一个瓶子何时可以倒入另一个瓶子中）。完成后，我尝试编写一些可以解决该问题的代码。对于代码如何知道选择哪个瓶子以及将其倒到哪里，我没有太多想法，所以我采用了简单的解决方案：随机选择它们。对于少量瓶子，它立即（有点）解决了这个问题，我上次尝试的是 10 瓶，但对于 15 瓶或更多，它不能。

所以我的第二个想法是计算每一个可能性和移动，即制作游戏树，然后使用搜索算法来找到最短路径，我读了一些关于游戏树和图的搜索算法并决定使用广度 -第一次搜索（后来我了解到我使用的图是有向无环图，所以最好使用拓扑排序，我不确定）。游戏树中的节点是瓶子相互倒入后所处的不同状态，边缘是从一种状态到另一种状态的移动。以下是我如何用伪代码生成游戏树：

take the first bottle A
create a list of bottles, list A, that bottle A can pour in
for each bottle B in list A, we pour bottle A in bottle B, and get a new state of bottles C
check if state C is already a node in the graph, or a permutation of a node(see explanation after the code) and add it to the graph if not
do what we did to bottle A, to all other bottles in the current node
then move to the children nodes and do the same

我所说的检查节点排列的意思是，例如， (bottle(1,2,1), Bottle(0,0,0), Bottle(2,1,2)) 与 (bottle(1) ,2,1), Bottle(2,1,2), Bottle(0,0,0))，因此当我保留排列时，只有 3000 个节点的图会变得像 200000 个节点一样大。

我写的代码的问题是生成游戏树需要太多时间，上次我尝试时，生成16瓶关卡的游戏树花了5个小时，我认为这个时间很多，而且可以做得更快。我的一个朋友建议使用 Numpy，因此图中的每个状态或节点都将是一个矩阵，并且因为 Numpy 可以更快地完成任务，这可能是这样做的方法，但我对 Numpy 并不精通，我我想我可以在这里询问可以帮助我解决问题的一般良好实践，例如如何检查节点是否已经在图上，或者它的排列，在这种情况下，它将检查两个矩阵是否是相当于列的排列或类似的东西。

所以我的问题是：如果你处于我的处境，你会如何解决这个问题，你认为我如何才能更好地优化我的代码？任何建议将不胜感激。

Answer 1

非常有趣的问题！我确实有一些建议

• 首先，我认为在没有明确目标的情况下搜索这样一个巨大的配置树充其量是低效的。为什么不选择导致更多瓶子被填充或以相同颜色填充得更高的“方向”呢？看我__iter__下面的。

• 我认为，如果瓶子只是顺序不同，那么认识到拼图的两种状态是相同的可能是值得的。您可以通过用整数元组表示瓶子中的颜色并保存一组这些颜色来做到这一点（因为该组不保证顺序）。见set_rep下文。

我无法抗拒将其编码。作为基础，我使用了 Raymond Hettinger 的通用解谜器。 尤其是我的solve方法深受他的影响。

实际代码

import numpy as np
from collections import deque


class ColoredWater:
    def __init__(self, pos):
        self.pos = pos

    @staticmethod
    def get_first_non_zero(arr):
        try:
            return arr[arr != 0][0]
        except IndexError:
            return 0

    @staticmethod
    def get_first_non_zero_index(arr):
        try:
            return np.where(arr != 0)[0][0]
        except IndexError:
            return 3

    @staticmethod
    def get_last_zero_index(arr):
        try:
            return np.where(arr == 0)[0][-1]
        except IndexError:
            return 3

    def get_legal_moves_to(self, moveable_to):
        first_non_zero = self.first_non_zero
        n = first_non_zero.shape[0]
        if first_non_zero[moveable_to] == 0:
            return np.where((first_non_zero != 0) & (np.arange(n) != moveable_to))[0], moveable_to
        else:
            return np.where((first_non_zero == first_non_zero[moveable_to]) & (np.arange(n) != moveable_to))[0], moveable_to

    def swap(self, i, j):
        out = self.pos.copy()
        idx_from = (self.get_first_non_zero_index(self.pos[:, i]), i)
        idx_to = (self.get_last_zero_index(self.pos[:, j]), j)
        out[idx_from], out[idx_to] = out[idx_to], out[idx_from]
        return ColoredWater(out)

    def isgoal(self):
        return np.array_equiv(self.pos, self.pos[0])

    def __iter__(self):
        self.first_non_zero = np.apply_along_axis(self.get_first_non_zero, 0, self.pos)
        moveable_to = np.where(self.pos[0] == 0)[0]
        legal_moves = tuple(map(self.get_legal_moves_to, moveable_to))

        out = [self.swap(origin, target)
               for origins, target in legal_moves
               for origin in origins]   

        def number_of_full_stacks(pos):
            return np.sum(np.all((pos == [pos[0]]), axis=0))

        def fillings_of_stacks(game):
            pos = game.pos
            return number_of_full_stacks(pos), number_of_full_stacks(pos[1:]), number_of_full_stacks(pos[2:])

        return iter(sorted(out, key=fillings_of_stacks, reverse=True))

    def set_rep(self):
        return frozenset(map(tuple, self.pos.T))

    def __repr__(self):
        return repr(self.pos)

    def solve(pos, depthFirst=False):
        queue = deque([pos])
        trail = {pos.set_rep(): None}
        solution = deque()
        load = queue.append if depthFirst else queue.appendleft

        while not pos.isgoal():
            for m in pos:
                if m.set_rep() in trail:
                    continue
                trail[m.set_rep()] = pos
                load(m)
            pos = queue.pop()

        while pos:
            solution.appendleft(pos)
            pos = trail[pos.set_rep()]

        return list(solution)

如何运行它

首先我在你的例子上运行它。在运行中，depthFirst=True它在 376 毫秒内给出了 117 次移动的解决方案。当我运行它时，depthFirst=False它在 9.42 秒内通过 55 次移动给出了最佳解决方案。

from ColoredWater import ColoredWater
import numpy as np

ColoredWater(np.array([[ 0,  1,  0,  5,  8,  9,  7,  4,  2,  8,  2,  5,  5, 10, 12],
                       [ 0,  2,  0,  6,  3, 10,  9,  7, 11,  3, 11, 12,  3,  6, 13],
                       [ 0,  3,  0,  7,  4,  2, 11, 11,  6, 12, 12, 13,  1, 13,  1],
                       [ 0,  4,  0,  5,  9,  9,  7,  6,  8,  8, 13,  1,  4, 10, 10]]))\
.solve(depthFirst=True) 

我还在“随机”示例上测试了它：

def sort_zeros(x):
    return sorted(x, key=lambda x:x != 0)


n = 15

arr = np.broadcast_to(np.array([0,0,*range(n)]),(4,n+2)).copy()
np.random.shuffle(arr.reshape(-1))
arr = np.apply_along_axis(sort_zeros,0,arr)
print(ColoredWater(arr).solve(depthFirst=True))