python - 创建没有重复的树

Question

我正在尝试用著名的滑动拼图的不同可能状态创建一棵树

如果你不知道，它是这样的:

[3 5 2]
[4   1]
[8 6 7]

你必须这样做的地方:

[1 2 3]
[4 5 6]
[7 8  ]

基本上，每个状态都会生成新的状态，具体取决于空白区域的移动方式(向上、向下、向左或向右)

我想要的是创建一个树，所有状态都给定根作为拼图的初始状态，但是当向树中添加子项(新状态)时，它应该检查该状态是否已经添加到树

你介意帮我实现吗？提前致谢:)

这是我当前的代码，它抛出 RecursionError: maximum recursion depth exceeded while calling a Python object

节点类:

class Node(object):
    def __init__(self, value, parent=None):
        self.parent = parent
        self.value = value
        self.children = []

    def append(self, obj):
        if obj is not self.parent and obj not in self.children and obj is not None:
            self.children.append(obj)

    def has_children(self):
        return len(self.children) > 0

    def __iter__(self):
        yield self.value
        for v in chain(*map(iter, self.children)):
            yield v

    def find_root(self):
        p = self
        while p.parent is not None:
            p = p.parent
        return p

树生成方法(将self视为拼图状态):

def to_tree(self, parent=None):
        values = []
        if parent is not None:
            for child in parent.find_root():
                values.append(child)

        value = nd.Node(self, parent)

        if value not in values:
            children = [move[1].to_tree(value) for move in self.get_possible_movements()]
            for child in children:
                if child is not None:
                    value.append(child)
            return value
        else:
            return None

Answer 1

我会尝试回答阻碍您进步的直接障碍:

RecursionError: maximum recursion depth exceeded while calling a Python object

这意味着“事件”函数调用(及其本地状态)的数量超过了限制。您可以尝试提高该限制(我半信半疑这可以在某处配置)，但还有另一种更通用的技术来解决这个问题。

在伪代码中，通过树的搜索(这似乎是您正在做的)看起来像这样:

find(predicate, node):
    if predicate(node):
        return node # found it
    for child in node.children:
        res = find(predicate, child):
        if res:
            return res # found it
    return false # not found

predicate 是一个函数，它返回一个 bool 值，指示是否找到搜索到的节点，它泛化了这个搜索。

这里的问题是，由于树的绝对高度，这可能会超过递归限制，如您所见。避免此限制的另一种方法是不使用递归。不要将临时状态存储在堆栈上，而是为它们构建一个专用容器:

find(predicate, node):
    temp = [node]
    while not temp.empty():
        node = temp.pop()
        if predicate(node):
            return node # found it
        for child in temp.children:
            temp.push(child)
    return false # not found

现在，重要的一点是调用深度被移动到 temp 容器。但是，让我们看一下细节，push 和 pop 调用，因为还不完全清楚它们的作用。如果你想模仿上面的递归版本，你将不得不使用堆栈(后进先出)。此外，您必须以相反的顺序将 child 压入堆栈，但 child 的顺序可能无关紧要。这意味着在第一次迭代之后，您在容器中拥有给定节点的所有直接子节点。在第二次迭代中，移除并处理一个直接子节点，这会添加该节点的子节点。换句话说，搜索首先进入树的深度，因此称为“深度优先搜索”(DFS)。

它的一个变体称为“广度优先搜索”(BFS)。在那里，您使用队列 (FIFO) 而不是堆栈 (LIFO) 作为容器。第一次迭代后的状态是相同的，都是给定节点的直接子节点。然而，它随后会检查这些 child 并将他们的 child 添加到容器中，但它只会在检查完所有 child 后才开始检查孙子。

关于这种非递归方法的一句话:同时，如果您将其作为进一步开发的基础，它会更加灵活。例如，如果您有多种方式到达同一个节点(即如果它不是树)，则可以将您已经到达的所有子节点存储在第二个容器中以避免循环。另一种方法是根据 child 与解决方案的距离对他们进行排序，以免遵循没有好处的路径。

一般来说，递归是一种很少使用的工具。理解它确实很重要，尤其是数学中的递归定义，但在编码中使用它通常是不切实际的。尽管我可以用一些经验和成功来支持它，但您会发现有不同想法的人，这更像是一种观点，而不是可靠的主张。