递归错误 - 分离度

Question

我正在尝试找出电影数据库中任意两个演员之间的“关系度”。当我找到基础情况时，也就是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

除非我没看到actedWith有什么特别的属性，否则你没有任何措施来防止无限循环。举个例子，你的一个递归调用是getDegrees("Gamble, Nathan", "Pitt, Brad", 2)，然后因为凯文·贝肯和布拉德·皮特合作过，当你再深入一层时，你会调用getDegrees("Gamble, Nathan", "Bacon, Kevin", 3)。你明白这个问题了吗？

Answer 2

这可能是无限递归的问题。你在搜索一个以目标为根的树，而这棵树上的某些路径可能会到达比它们更高的点。你需要找到一种方法来识别这种情况，并在发生时停止沿着那条路径继续搜索。

一种方法是保持一份路径上祖先的列表。可以像这样：

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的情况（希望输入文件中永远不会出现这种情况），但通过小的修改是可以解决的。

Answer 3

这里有两个建议（我没有查看文本文件，只是根据基本原则和快速阅读你的代码得出的）：

1. 在你从getDegrees函数返回时，实际上你还在继续执行这个函数后面的代码。你需要返回一个True（或者其他什么）来表示搜索已经结束，整个函数调用的过程应该停止。第一个返回应该改成“return True”，最后一行应该改成“if getDegrees(target, actor, dos): return True”。
2. 要记录哪些演员已经被搜索过。如果两个演员互相合作过，或者关系中有循环的话，你就会来回循环。

这段代码试图解决返回值和图循环的问题。不过，还是有逻辑错误；凯文·贝肯和詹姆斯·贝鲁西（分离度为2）给出的结果是：

约瑟夫·西拉沃与詹姆斯·贝鲁西之间有179度的分离。

补充：通过添加“original”参数来修复。

不过递归问题已经解决了。

##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