python - 广度优先搜索在 Python 中的实现

Question

我正在尝试用 Python 实现 BFS，我了解该算法的工作原理，但我没有太多编程经验。我花了几个小时思考表示所有内容的最佳方式以及如何尽可能高效。我一直无法弄清楚如何获得从我的起始节点到目标节点的路径。

我花了很长时间谷歌搜索并查看其他人的算法实现，但我的应用程序略有不同，这让我感到困惑。当人们实现 BFS 时，他们假设他们有一张图表给他们(关于 BFS 的维基百科文章也是如此)。在我的问题中，我有一个初始状态和一个我想要达到的目标状态，但没有图或树，所以我会边走边生成节点。

例如:

def BFS(initial, goal):

    q = [initial]
    visited = []

    while q:
        n = q.pop()
        states = generate_states(n)

        for state in states:
            if state == goal:
                pass #placeholder
            q.append(state)
            visited.append(state)

它没有被适本地充实，因为我遇到了一些问题，我也不确定它具体是什么......如果初始和目标是节点，我在代码的其他地方写了一个结构类型类，例如:

class node:
    state = None
    parent = None

我认为这是表示节点的合适方式。因此，当我从队列中弹出一个节点对象时，它有关于它起源于何处的信息，这些信息将由 generate_states 函数初始化。然后 for 循环会将这些新节点中的每一个附加到队列中，并访问队列并在其中一个生成的节点具有与我的目标状态匹配的状态下重复。

现在我已经找到了目标节点，我有一个已访问节点的列表，但是如果我从目标节点向后跟踪路径，我不会减慢算法速度吗？一旦找到一个目标，我会查看它的父级，在访问列表中找到它的父级，然后查看父级的父级，等等......直到我有一个 path = [node object, node object, ... ] 从初始节点到目标节点。

这给我带来了另一个问题，当我创建一个节点对象时，它只持续 while 循环的一次迭代。我打算如何将对象存储在数组中，它们每个都需要一个唯一的名称，并且(对我而言)没有明显的方法来做到这一点。这是我之前提到的我不确定的问题。所以看起来我正在创建节点，但随后只将 node.state 存储在队列中，这是毫无意义的，因为我需要节点对象访问 node.parent...

为什么我觉得这很困难，是我遗漏了一些明显的东西还是把它弄得太复杂了？

感谢阅读。

Answer 1

我不能对其中的大部分内容发表评论，因为我不完全理解你想要做什么 - 正如你所说，通常 BFS 已经有了图表，所以我不确定你是怎么做的正在提议随手构建它。但是我必须回复这个位:

How am I meant to store the objects in an array, they will each need a unique name

这绝对是错误的。如果您只是想将某物存储在列表中，则完全没有必要为其命名 - 您只需附加它即可。如果您担心以后能否找到它，那么处理图的正常做法就是通过一个计数器给每个节点一个编号，每次定义一个计数器时您都会增加该计数器。同样，如果您只是将节点存储在列表中，那么它们会自动获得一个唯一编号:它们在列表中的位置。