使 BFS 适应多个值

Question

我有以下函数 program.the 函数 BFS 显示从节点到 target/goal 的路径。我如何修改函数 BFS，而不是将单个字符作为目标，它应该接受字符列表。

# tree stored as a dictionary (parent: [children])
simpletree = {'a':  ['b', 'c'],
              'b':  ['d','e', 'f'],
              'c':  ['g', 'h', 'i','j'],
              'd':  ['k', 'l'],
              'e':  ['m'],
              'g':  ['n'],
              'i':  ['o'],
              'j':  ['p'],
              'o':  ['z']}

def Successors(node,dictionarytree):

    children=dictionarytree[node]#extracting the children of a node

    for child in children:#i get the children using a for loop and  yield
             yield child




# Breadth-First search of a dictionary tree
def BFS(nodelist,target,dictionarytree):
    print "Nodelist:",nodelist
    childlist=[]
    # iterate over all the nodes in parentlist
    for parent in nodelist:

        # if the node is the target
        if parent[-1]==target:
            return parent
        # check if the node has children    
        if dictionarytree.has_key(parent[-1]):#check if the key exists in the  dictionary

            # loop through children and return children
             for child in Successors(parent[-1],dictionarytree): 
                    print child
                    childpath=parent+(child,)#add the targert to the childpath


                    childlist.append(childpath)
                    print "childpath",childpath
    # if there are children, progress to the next level of the tree
    if len(childlist) != 0:
        return BFS(childlist,target,dictionarytree)
    else:
        return None

node='a'
goal='z'
print simpletree
print BFS([(node,)],goal,simpletree)

Answer 1

嗯，BFS 并不是真的设计成有多个目标结局。在胡闹之后，你不能真正称它为 BFS。如果你真的对此很感兴趣，你总是可以把它画出来，看看如果你在头脑中遵循算法会发生什么。但是您需要跟踪哪个目标的路径。我认为这不会有太大帮助。

就我个人而言，因为这看起来像是在学校，所以我只是在另一个函数中遍历字符列表并存储值。您需要将 BFS 函数编辑为 return 路径而不是打印它。

def multipleBFSRuns(listOfChars):
  values=[]
  for x in listOfChars:
     values.append(BFS([(node,)],x,simpletree))
  return values

使 BFS 适应多个值

Adapting BFS to target multiple values

python

tree

artificial-intelligence

breadth-first-search