递归错误 - 分离度

Question

我试图找到电影数据库中任何两个actor之间的分离度。 我成功了，当我达到我的基本情况，为1的分离度（即演员在同一部电影中的另一位演员），但我用递归查找所有其他程度的分离，我也得到：

runtime error: maximum recursion depth exceeded in cmp. 

我用

##gets file with movie information 
f = open("filename.txt") 
actedWith = {} 
ActorList = [] 
movies = {} 
actedIn = [] 
dos = 1 

def getDegrees(target, base, dos): 
    for actor in actedWith[base]: 
     if target == actor: 
      print base, "has ", dos, " degree(s) of separation from ", target 
      return 
    dos = dos+1 
    for actor in actedWith[base]: 
     getDegrees(target, actor, dos) 


for l in f: 
    ##strip of whitespace 
    l = l.strip() 
    ##split by where forward-slashes are 
    l = l.split("/") 
    ##add the first "word" on the line to the database of movie names 
    movies = {l[0] : l[1:]} 
    for e in l[1:]: 
     if e in actedWith: 
      actedWith[e] = actedWith[e]+movies[l[0]] 
     else: 
      actedWith[e] = movies[l[0]] 

base = raw_input("Enter Actor Name (Last, First): ") 
target = raw_input("Enter Second Actor Name (Last, First): ") 
getDegrees(target, base, dos) 

文本文件可以在http://www.mediafire.com/?qtryvkzmuv5jey3

中找到为了测试基地的情况下，我使用：Bacon, Kevin和Pitt, Brad。

要测试其他人，我使用Bacon, Kevin和Gamble, Nathan。

Answer 1

两点建议（我没有看过上的文本文件，只是去上第一的原则在这里和你的代码快速阅读）：

1. 当您从getDegrees回，你仍然可以通过持续返回后的功能的其余部分。你需要返回一个True（或者某个）来表示搜索结束，整个函数调用栈应该被回滚。第一个返回将变为“返回True”，最后一行将变为“如果getDegrees（target，actor，dos）：return True”。
2. 跟踪哪些演员已被搜索。如果两个演员互相行动，或者关系中有一个循环，你会来回循环。

此代码尝试修复返回和图形循环问题。但是，某处仍然存在逻辑错误;凯文培根和詹姆斯贝鲁西（2分离度）得到下列：

Siravo，约瑟夫具有从贝鲁西分离的179度（S），詹姆斯

编辑：通过将固定在“原始“参数。

但递归问题是固定的。

##gets file with movie information 
f = open("filename.txt") 
actedWith = {} 
ActorList = [] 
movies = {} 
actedIn = [] 
dos = 1 

def getDegrees(original, target, base, dos=0, seen=[]): 
    dos = dos+1 
    print "----> checking %s against %s" % (target, base) 
    for actor in actedWith[base]: 
     #print "\t" + actor 
     if target == actor: 
      print original, "has ", dos, " degree(s) of separation from ", target 
      return True 
    for actor in actedWith[base]: 
     if actor in seen: continue 
     seen = seen + [actor] 
     if getDegrees(original, target, actor, dos, seen): 
      return True 
    return False 


for l in f: 
    ##strip of whitespace 
    l = l.strip() 
    ##split by where forward-slashes are 
    l = l.split("/") 
    ##add the first "word" on the line to the database of movie names 
    movies = {l[0] : l[1:]} 
    for e in l[1:]: 
     if e in actedWith: 
      actedWith[e] = actedWith[e]+movies[l[0]] 
     else: 
      actedWith[e] = movies[l[0]] 

original = raw_input("Enter Actor Name (Last, First): ") 
target = raw_input("Enter Second Actor Name (Last, First): ") 
getDegrees(original, target, original) 

例子：

Bacon, Kevin has 65 degree(s) of separation from Kosaka, Masami 

Answer 2

除非有一些actedWith的财产我没有看到，你没有任何东西可以防止无限循环。例如，您的递归调用中的一个将是getDegrees("Gamble, Nathan", "Pitt, Brad", 2)，然后由于Kevin Bacon已与布拉德皮特一起工作，当您再深入一级时，您将拨打getDegrees("Gamble, Nathan", "Bacon, Kevin", 3)。看到问题了吗？

Answer 3

它可能是无限递归。你正在寻找一棵植根于目标的树;并且该树上的一些路径到达了它们上游的点。您需要一种方法来识别这种情况，并在发生这种情况时停止向下看。

一种方法是保留路径上的祖先列表。喜欢的东西：

def getDegrees(target, base, dos, ancestors): # Also carry a list of "ancestors" 
    for actor in actedWith[base]: 
     if target == actor: 
      print base, "has ", dos, " degree(s) of separation from ", target 
      return 
    dos = dos+1 
    ancestors = ancestors + [base] # Must be separate variable binding to avoid mutating the caller's copy 
    for actor in actedWith[base]: 
     if actor in ancestors: continue # Check if on path, skip if so 
     getDegrees(target, actor, dos, ancestors) 

... 

getDegrees(target, base, dos, [target]) 

注意，“祖先”是指道路，不是一个演员可能与一个人上的一个点。

这并不能避免演员拥有actedWith自己（希望输入文件永远不会包含该情况）的情况，但它可能会带来一些小改变。