Python的遞歸我缺少什麼

Question

我有2個水罐的問題。 初始狀態是[0,0]，各個水罐的容量爲[4,9]，目標狀態是[0,6] 合法移動：填充水壺1或壺2直到結束，空壺1或壺2和可憐的一個罐子進入另一個。

import search #get the interface 
import sys 
sys.setrecursionlimit(5000) 
class two_jugs(search.Nodes): 

    #return the starting state vessel 1: 0, vessel 2: 0 
    def start(self): 
      return [0,0] 

    #returns true if node is equal to goal node 
    def goal(self,node): 
      return node ==(0,6) 
    #yields the successors of the configuration indicated by node 
    def succ(self,node):    
      # set capacities for vessel 1: 4, vessel 2 : 9 
      c = [4,9]; 
      #stop at second last 
      for i in range(len(node)-1): 
        #create a safety copy 
        new_node = node[:] 

        #fill vessel 1 
        if new_node[i]<=0: 
          new_node[i]=c[i] 
          print new_node 

        #fill vessel 2 
        if new_node[i+1]<=0: 
          new_node[i+1]=c[i+1] 
          print new_node 

        #dump vessel i+1 
        if (new_node[i+1]>0): 
          new_node[i+1]=0 
          print new_node 

        #poor vessel i to vessel i+1     
        if (new_node[i+1]<c[i+1] and new_node[i]>0): 
          #calculate the difference 
          d = min(new_node[i],c[i+1]-new_node[i+1]) 
          new_node[i]= new_node[i]-d 
          new_node[i+1]= new_node[i+1]+d 
          print new_node 

        #dump vessel i 
        if (new_node[i]>0): 
          new_node[i]=0 
          print new_node 


       #poor vessel i+1 to vessel 1 
        if (new_node[i]<c[i] and new_node[i+1]>0): 
          #calculate the difference 
          d = min(new_node[i+1],c[i]-new_node[i]) 
          #set new node 
          new_node[i+1]= new_node[i+1]-d 
          new_node[i]= new_node[i]+d 
          yield new_node 
          print new_node 

現在的問題是，因爲我已經宣佈所有的法律動作，爲什麼我的程序只返回一個合法的舉動，結果呢？例如，從運行程序的起始狀態[0,0]開始，它返回[4,0]，[0,4]，[0,9]和其他可能的結果，直到遞歸停止，但不是我的目標狀態。 我錯過了什麼？

class Nodes: 
    def succ(self,n): 
     raise Exception, "Successor undefined" 
    def start (self): 
     raise Exception, "Start undefined" 
    def goal (self,n): 
     raise Exception, "Goal undefined" 

運行該程序的類：

import decant 
from breadth_first_search import * 

dec = decant.Decant() 
print breadth_first_search(dec,[[dec.start()]]) 

Answer 1

您的第一個錯誤是標籤類2jugs

breadth_first_search類：

def breadth_first_search(problem, candidates): 
    if not candidates: return 
    # make sure there is something in the candidate list 
    # I am modifying ’candidates’ list here. 
    # Why don’t I need to copy? 
    c = candidates.pop(0) # pop from front 
    node = c[-1] # must exist 
    if problem.goal(node): return c 
    # base case 
    succ = [s for s in problem.succ(node)] 
    for s in problem.succ(node): 
     candidates.append(c + [s]) 
     # 1-step extension 
    return breadth_first_search(problem, candidates) 

搜索類別。在Python變量名（包括類和函數的名稱）以及許多其他的編程語言不能以數字開頭。因此，重命名2jugs到two_jugs。

precise rule for identifiers in python是標識符必須以大寫字母（A-Z），小寫字母（a-z）或下劃線（_）開頭。標識符的以下字符也可以包含數字（0-9）。 （該規則在Backus-Naur form中指定）。