在python中实现递归深度优先算法的错误

-1

我在udacity上做了一些实践问题，必须编写一些递归代码来查找节点中朋友的路径。我想出了这个。然而，递归定义缺少停止条件，我认为没有找到连接。我如何解决它？网络的在python中实现递归深度优先算法的错误

def path_to_friend(network, user_A, user_B,traversed = None): 
    if traversed is None: 
     traversed = [] 

    if (user_B in network and user_A in network): 
     if user_B in get_connections(network,user_A): 
      return [user_A] + [user_B] 
     else: 
      for conn in get_connections(network,user_A) : 
       if conn in traversed: 
        continue 
       else: 
        traversed.append(conn) 
        return [user_A] + path_to_friend(network,conn,user_B) 
    else: 
     return None

数据结构：{ '鲍勃'：[[ '卡罗尔']，[]]， '爱丽丝'：[[ '鲍勃']，[]]， '卡罗尔'：[[”鲍勃 ']，[]]}

为了找到：path_to_friend（网络，' 鲍勃”， '爱丽丝'）

结果：无限递归。我如何解决它？

来源

2015-10-18 Kartik Kapoor

你失踪，至少，因为当''LEN（网络）的条件== 0''。我认为它应该返回''None''或者什么 –

为什么你的值是列表的列表，什么是get_connections？ –

这行代码在这里可能会导致此问题：

return [user_A] + path_to_friend(network,conn,user_B)

基本上这个代码，只要任何连接发现尚未访问运行。因此，代码将在第一个未访问路径中搜索连接，否则将不再路径。

  c ---- e 
     /
a ---- b 
     \ 
     d

如果你开始在和目标节点是E，你的代码将只能达到E，如果c在get_connections(network , b) d前出现，否则代码将在d结束。这种行为甚至没有定义/执行路径不会以return -statement结尾。

最简单的解决办法是简单地返回None，如果路径没有找到节点结束：

for conn in get_connections(network,user_A) : 
    if conn in traversed: 
     continue 
    else: 
     traversed.append(conn) 
     tmp = path_to_friend(network , conn , user_B) 
     if (tmp is not None): 
      return [user_A] + tmp//a matching path was found 

//no matching path was found -> return none 
return None

下一页问题代码：你不是从一个调用保持走过列表接下来，每次调用该函数时，traversed is None都成立。使用每个呼叫的遍历列表作为参数，为后续的呼叫：

path_to_friend(network,conn,user_B, traversed)

来源

2015-10-18 09:33:22 Paul

我已经更新了代码。但仍然陷入无限循环。似乎遍历列表正在每个函数调用中创建。我该如何解决。 –

@KartikKapoor我已经更新了答案，应该修复这个问题。 – Paul

def path_to_friend(network, user_A, user_B,traversed = None): 
if traversed is None: 
    traversed = [] 

if (user_B in network and user_A in network): 
    if user_B in network[user_A][0] : 
     return [user_A] + [user_B] 
    else: 
     for conn in network[user_A][0] : 
      if conn in traversed: 
       continue 
      else: 
       traversed.append(conn) 
       temp = path_to_friend(network,conn,user_B,traversed) 
       if (temp is not None): 
        return [user_A] + temp 
     return None 
else: 
    return None 


network = {'Bob': [['Carol'], []], 'Alice': [['Bob'], []], 'Carol': [['Bob'], []]} 
path_to_friend(network,'Bob','Alice')

来源

2015-10-18 11:20:05

在python中实现递归深度优先算法的错误

回答

相关问题