递归误差分离度

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和{}。在

Answer 1

除非actedWith的某些属性我看不到，否则您没有任何地方可以防止无限循环。例如，您的一个递归调用将是getDegrees("Gamble, Nathan", "Pitt, Brad", 2)，那么由于Kevin Bacon与Brad Pitt合作过，当您深入到另一个层次时，您将调用getDegrees("Gamble, Nathan", "Bacon, Kevin", 3)。看到问题了吗？在

Answer 2

两个建议（我没有查看文本文件，只是在这里介绍一下基本原则，并快速阅读一下您的代码）：

1. 当您从getDegrees返回时，您仍然要在返回之后完成函数的其余部分。您需要返回True（或其他值）以指示搜索已结束，整个函数调用堆栈应该回滚。第一个返回将更改为“returntrue”，最后一行将更改为“if getDegrees（target，actor，dos）：return True”。在
2. 跟踪哪些演员已经被搜索过。如果两个演员互相表演，或者在关系中有一个循环，你会来回循环。

此代码尝试修复返回和图形循环问题。然而，仍然有一个逻辑错误，凯文·培根和詹姆斯·贝卢斯希（2度分离度）给出了以下结论：

Siravo, Joseph has 179 degree(s) of separation from Belushi, James

编辑：通过添加“原始”参数修复。在

但递归问题是固定的。在

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

示例：

^{pr2}$

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])

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

这并不能避免一个actor拥有actedWith他们自己的情况（希望输入文件永远不会包含这些内容），但是只要稍加修改就可以了。在