2

我正在尝试在 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 ...

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

谢谢阅读。

4

3 回答 3

1

我不能对大部分内容发表评论，因为我不完全理解你想要做什么——正如你所说，通常 BFS 已经有图表了，所以我不确定你是如何提议的随手建造。但我必须回复这一点：

我是如何将对象存储在数组中的，它们每个都需要一个唯一的名称

这绝对是错误的。如果您只想将其存储在列表中，则绝对无需命名 - 您只需附加它即可。如果您担心以后能够找到它，那么与图表有关的正常操作就是给每个节点一个数字，通过一个计数器，每次定义一个时您都会增加该数字。同样，如果您只是将节点存储在列表中，那么它们会自动获得一个唯一编号：它们在列表中的位置。

于 2012-04-14T14:41:20.997 回答
0

你的方法对我来说很好。

为了获得发现路径，您可以跟踪每个父节点，例如给它一个属性，该属性设置为发现它的节点。这样，您就有了一个可追溯发现路径的链表。一旦你达到了你可以做的目标就往回走

def get_parents(node):
    if node.parent is None:
        return []

    yield node.parent
    get_parents(node)

为了跟踪生成的节点（变量 n），只需将您发现的节点放入列表中，而不仅仅是状态。

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

    for state in states:
        m = node()
        m.state = state
        m.parent = n
        if state == goal:
            pass #placeholder
        q.append(m)
        visited.append(m)
于 2012-04-14T14:48:11.690 回答
0

一般来说，你所拥有的一切都很好。

有几个困惑，我将尝试解释。首先，您可以将节点存储在队列中，而不是状态，并且由于节点有父节点，您可以访问之前的节点，因此您不会丢失它们。其次，追溯父母不是为了提高效率而需要担心的事情——你只有在成功时才这样做（另外，不需要名字——听起来你把列表和地图混淆了？）。

因此，您的代码中唯一缺少的是您没有创建节点。当你得到一个状态时，创建一个节点，然后保存节点，而不是保存状态。然后一切都会奏效。

于 2012-04-14T14:52:01.363 回答