Python中的无限循环与递归

Question

我正致力于实现一个迭代的深化深度优先搜索，以找到8 puzzle problem的解决方案。我对寻找实际的搜索路径本身并不感兴趣，而是想知道程序运行所需的时间。（我还没有实现计时功能）。在

但是，我在实现实际搜索功能时遇到了一些问题（向下滚动查看）。我粘贴了目前为止所有的代码，所以如果你复制粘贴这个，你也可以运行它。这可能是描述我遇到的问题的最好方法…我只是不明白为什么在递归过程中会出现无限循环，例如在谜题2（p2）的测试中，第一次扩展应该会产生一个解决方案。我想这可能与没有在一行代码前面添加“Return”有关（下面对其进行了注释）。当我添加返回值时，我可以通过谜题2的测试，但是像谜题3这样更复杂的东西失败了，因为现在的代码似乎只扩展了最左边的分支。。。在

在这里干了好几个小时，放弃了希望。如果你能指出我的错误，我将非常感激你能再多看一眼。谢谢您！在

#Classic 8 puzzle game
#Data Structure: [0,1,2,3,4,5,6,7,8], which is the goal state. 0 represents the blank
#We also want to ignore "backward" moves (reversing the previous action)

p1 = [0,1,2,3,4,5,6,7,8]
p2 = [3,1,2,0,4,5,6,7,8]
p3 = [3,1,2,4,5,8,6,0,7]

def z(p):   #returns the location of the blank cell, which is represented by 0
    return p.index(0)

def left(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc-1]
    p[zeroLoc-1] = 0
    return p

def up(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc-3]
    p[zeroLoc-3] = 0
    return p

def right(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc+1]
    p[zeroLoc+1] = 0
    return p

def down(p):
    zeroLoc = z(p)
    p[zeroLoc] = p[zeroLoc+3]
    p[zeroLoc+3] = 0
    return p

def expand1(p):   #version 1, which generates all successors at once by copying parent
    x = z(p)
    #p[:] will make a copy of parent puzzle
    s = []  #set s of successors

    if x == 0:
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 1:
        s.append(left(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 2:
        s.append(left(p[:]))
        s.append(down(p[:]))
    elif x == 3:
        s.append(up(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 4:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(right(p[:]))
        s.append(down(p[:]))
    elif x == 5:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(down(p[:]))   
    elif x == 6:
        s.append(up(p[:]))
        s.append(right(p[:]))
    elif x == 7:
        s.append(left(p[:]))
        s.append(up(p[:]))
        s.append(right(p[:]))
    else:   #x == 8
        s.append(left(p[:]))
        s.append(up(p[:]))

    #returns set of all possible successors
    return s

goal = [0,1,2,3,4,5,6,7,8]

def DFS(root, goal):    #iterative deepening DFS
    limit = 0
    while True:
        result = DLS(root, goal, limit)
        if result == goal:
            return result
        limit = limit + 1

visited = []

def DLS(node, goal, limit):    #limited DFS
    if limit == 0 and node == goal:
        print "hi"
        return node
    elif limit > 0:
        visited.append(node)
        children = [x for x in expand1(node) if x not in visited]
        print "\n limit =", limit, "---",children   #for testing purposes only
        for child in children:
            DLS(child, goal, limit - 1)     #if I add "return" in front of this line, p2 passes the test below, but p3 will fail (only the leftmost branch of the tree is getting expanded...)
    else:
        return "No Solution"

#Below are tests

print "\ninput: ",p1
print "output: ",DFS(p1, goal)

print "\ninput: ",p2
print "output: ",DLS(p2, goal, 1)
#print "output: ",DFS(p2, goal)

print "\ninput: ",p3
print "output: ",DLS(p3, goal, 2)
#print "output: ",DFS(p2, goal)

Answer 1

为你的州使用类！这会让事情变得容易得多。让你开始。现在不想发布整个解决方案，但这会使事情变得容易得多。在

#example usage
cur = initialPuzzle
for k in range(0,5): # for 5 iterations. this will cycle through, so there is some coding to do
    allsucc = cur.succ() # get all successors as puzzle instances
    cur = allsucc[0] # expand first                                                                                           
    print 'expand ',cur 

---

^{pr2}$

Answer 2

递归的直接问题是，在执行递归步骤时不会返回任何内容。但是，无条件地从第一个递归调用返回值也不起作用，因为不能保证第一个子级是找到解决方案的那个。相反，您需要测试您在子状态上执行的递归搜索（如果有的话）是否成功。下面是我如何更改DLS函数的结尾：

    for child in children:
        child_result = DLS(child, goal, limit - 1)
        if child_result != "No Solution":
            return child_result

# note, "else" removed here, so you can fall through to the return from above
return "No Solution"

一种稍微“pythonic”（而且更快）的方法是使用None作为哨兵值，而不是“No Solution”字符串。那么您的测试将是if child_result: return child_result，您可以选择为失败的搜索省略return语句（因为None是函数的默认返回值）。在

一旦这个递归问题被修复，代码中还存在一些其他问题。例如，使用全局visited变量是有问题的，除非每次重新启动另一个递归搜索时都重置它。但我会把这些留给你！在