Python中的無限循環和遞歸

Question

我正在實施迭代加深深度優先搜索以找到8 puzzle problem的解決方案。我對找到自己的實際搜索路徑並不感興趣，而只是爲了計算程序運行需要多長時間。 （我還沒有實現定時功能）。

但是，我有一些問題試圖實現實際的搜索功能（向下滾動查看）。我粘貼了迄今爲止所有的代碼，因此如果您複製並粘貼此代碼，則也可以運行它。這可能是描述我遇到的問題的最好方法......我只是不理解爲什麼在遞歸期間我會遇到無限循環，例如，在拼圖2（p2）的測試中，第一次擴展應該產生一個解決方案。我認爲這可能與在代碼行之前不添加「返回」有關（它在下面進行了評論）。當我添加回報時，我可以通過拼圖2的測試，但像拼圖3這樣更復雜的測試失敗，因爲看起來現在的代碼只是展開最左邊的分支......

在此處for幾小時，並放棄希望。如果你能指出我的錯誤，我會非常感激這一點。謝謝！

#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

您在遞歸時遇到的直接問題是，當您執行遞歸步驟時，不會返回任何內容。但是，無條件地從第一次遞歸調用返回值也不起作用，因爲第一個孩子不能保證找到解決方案。相反，您需要測試以查看您在子狀態中執行的遞歸搜索的哪些（如果有）成功。以下是我會改變你的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" 

一個這樣做是使用None作爲標記值而不是「無解」的略微更「Python化」（快）的方式串。然後，您的測試將簡單地爲if child_result: return child_result，您可以選擇退出失敗搜索的返回語句（因爲None是函數的默認返回值）。

一旦這個遞歸問題得到解決，您的代碼還會遇到一些其他問題。例如，使用全局變量visited是有問題的，除非每次重新啓動另一個遞歸搜索時重置該變量。但我會把這些留給你的！

Answer 2

爲你的狀態使用類！這應該讓事情變得更容易。爲了讓你開始。現在不想發佈整個解決方案，但這使事情變得更容易。

#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 

---

import copy 


class puzzle: 

    ''' 
    orientation 
    [0, 1, 2 
    3, 4, 5 
    6, 7, 8] 
    ''' 

    def __init__(self,p): 
     self.p = p 

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

    def swap(self,a,b): 
     self.p[a] = self.p[b] 
     self.p[b] = 0 

    def left(self): 
     self.swap(self.z(),self.z()+1) #FIXME: raise exception if not allowed 

    def up(self): 
     self.swap(self.z(),self.z()+3) 

    def right(self): 
     self.swap(self.z(),self.z()-1) 

    def down(self): 
     self.swap(self.z(),self.z()-3) 

    def __str__(self): 
     return str(self.p) 

    def copyApply(self,func): 
     cpy = self.copy() 
     func(cpy) 
     return cpy 

    def makeCopies(self,s): 
     ''' some bookkeeping ''' 
     flist = list() 
     if 'U' in s: 
      flist.append(self.copyApply(puzzle.up)) 
     if 'L' in s: 
      flist.append(self.copyApply(puzzle.left)) 
     if 'R' in s: 
      flist.append(self.copyApply(puzzle.right)) 
     if 'D' in s: 
      flist.append(self.copyApply(puzzle.down)) 

     return flist 

    def succ(self): 
     # return all successor states for this puzzle state 
     # short hand of allowed success states 
     m = ['UL','ULR','UR','UDR','ULRD','UDL','DL','LRD','DR'] 
     ss= self.makeCopies(m[self.z()]) # map them to copies of puzzles 
     return ss 


    def copy(self): 
     return copy.deepcopy(self) 



# some initial state 
p1 = [0,1,2,3,4,5,6,7,8] 

print '*'*20 
pz = puzzle(p1) 
print pz 

a,b = pz.succ() 
print a,b