遞歸錯誤 - 分離度

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自己（希望輸入文件永遠不會包含該情況）的情況，但它可能會帶來一些小改變。