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

我试图在Python中实现BFS，我理解算法是如何工作的，但我没有太多的编程经验。我花了好几个小时的时间思考最好的方式来表现一切，以及如何尽可能高效。我一直无法弄清楚如何获得从我的开始节点到目标节点的路径。在Python中的广度优先搜索实现

我花了年龄周围的Googling和寻找其他人民实现算法的，但我的应用程序略有不同，这让我困惑。当人们实施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循环会将每个新节点追加到队列中，并且访问队列，并且它会在其中一个生成的节点下重复出现一个与我的目标状态匹配的状态。

现在，我已经发现目标节点，则我曾参观过的节点列表，但如果我跟踪路径向后从目标节点的路径，不是我放慢算法？一旦找到目标，我会查看它的父项，在访问列表中找到它的父项，然后查看父项的父项等...直到我有一个路径= [节点对象，节点对象，... ]从初始节点到目标节点。

这使我想起了另一个问题，当我创建一个节点对象只持续了while循环的一个迭代。我如何将对象存储在数组中，它们每个都需要一个唯一的名称，而且对我来说没有明显的方法来执行此操作。这是我之前提到的我不确定的问题。所以它看起来像我创建的节点，但只有在队列中存储node.state，这是毫无意义的，因为我需要节点对象访问node.parent ...

为什么我觉得这很难，我错过了一些明显的东西，或者使这个过于复杂？

感谢您的阅读。

来源

2012-04-14 user1291204

我不能在这个最发表评论，因为我不完全理解你正在试图做的 - 就像你说的，通常是BFS将有图形已经出现，所以我不知道如何你打算在你走的时候建造它。但我必须回复此位：

我怎么打算的对象存储在数组中，他们将每个人都需要一个唯一的名称

这肯定是假的。如果你只是想把它存储在一个列表中，那么绝对没有必要给出一个名字 - 你可以追加它。如果你担心能够在以后找到它，那么对于图形来说，正常的事情就是给每个节点一个数字，通过一个你每次定义一个时就增加的计数器。同样，如果您只是将节点存储在列表中，那么它们会自动获取唯一编号：它们在列表中的位置。

来源

2012-04-14 14:41:20

有一个初始状态和一个目标状态以及有限数量的操作符。正如你所说，我没有给出一个图，我必须构建它，这是通过应用一套操作完成的，我使用函数generate_states（n），其中n是一个节点。最后，我将遍历每个状态并最终得到一棵树，该树终止于目标节点。我试图了解如何做到这一点，然后从目标节点向后追踪以在树中查找路径。对不起，如果这更令人困惑。 – user1291204 2012-04-14 15:16:51

你的方法对我来说很好。

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

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-14 14:48:11 j13r

一般来说，你有什么好。

但有一些混淆，我会试着解释。首先，将节点存储在队列中，而不是状态。并且由于节点有一个父节点，所以你可以到达前面的节点，所以你没有丢失它们。第二，通过父母追溯并不是你需要为提高效率而担心的事 - 你只有在成功的时候才能做到这一点（同样，不需要名字 - 听起来像是让地图混淆名单？）。

所以你的代码中唯一缺少的东西就是你没有创建节点。当你得到一个状态时，创建一个节点并保存节点，而不是状态。那么一切都会奏效。

来源

2012-04-14 14:52:01

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

回答

相关问题