使用python中的递归在dfs中超出了最大递归深度

1 回答

• 0

  有两个问题：

  1：您的“已访问”列表没有正确跟踪所有状态 . 这可以通过访问一个全局变量（通过将其置于def main（）之前，如最终解决方案中所做的那样）轻松修复

  2：该程序正在寻找不会有任何帮助的可能性（例如：来回带来同一个人），这个

  if root in visited:
      return
  if root is None:
      return
  

  没有解决这个问题，因为它永远不是同一个根对象（即使root.state.mission，canibals和boat是相同的值），所以我使用字典对象更改了它：

  if root is None:
      return
  state = str(root.state.missionaries) + ',' + str(root.state.cannibals) + ',' + str(root.state.boat)
  if state in routes:
      if routes[state] < root.depth:
          return
      else:
          routes[state] = root.depth
  else:
      routes[state] = root.depth
  visited.append(root)
  

  这导致以下代码（它返回一个答案，我不确定它是否正确，因为我不知道传教士和食人族的问题）

  class State(object):
  #left = 1
  #right = 0 for boat
      def __init__(self, missionaries, cannibals, boat):
          self.missionaries = missionaries
          self.cannibals = cannibals
          self.boat = boat
  
      #def __str__(self):
      #    return "%s, %s %s %s" % (self.by_move, self.missionaries, self.cannibals, self.boat)
  
      def is_valid(self):
          if self.missionaries < 0 or self.missionaries > 3:
              return False
          if self.cannibals < 0 or self.cannibals > 3:
              return False
          if self.boat > 1 or self.boat < 0:
              return False
          if self.missionaries < self.cannibals and self.missionaries > 0:
              return False
          # Check for the other side
          if self.missionaries > self.cannibals and self.missionaries < 3:
              return False
  
          return True
  
      def is_goal(self):
          return self.missionaries == 0 and self.cannibals == 0 and self.boat == 0
  
      def new_states(self):
          op = -1  # Subtract
          boat_move = "from left shore to right"
          if self.boat == 0:
              op = 1  # Add
              boat_move = "from right shore to left"
  
          for x in range(3):
              for y in range(3):
                  by_move = "Move %s missionaries and %s cannibals %s" % (x, y, boat_move)
                  new_state = State(self.missionaries + op * x, self.cannibals + op * y, self.boat + op * 1)
                  if x + y >= 1 and x + y <= 2 and new_state.is_valid():
                      yield new_state
  
  class Node(object):
      def __init__(self, parent, state, depth):
          self.parent = parent
          self.state = state
          self.depth = depth
  
      def children(self):
          for state in self.state.new_states():
              yield Node(parent=self, state=state, depth=self.depth + 1)
  
      def extract_solution(self):
          print "Extracting soln"
          solution = []
          node = self
          solution.append(node)
          while node.parent is not None:
              solution.append(node.parent)
              node = node.parent
          solution.reverse()
          return solution
  
  def dfs(root,sol = None):
      if root is None:
          return
      state = str(root.state.missionaries) + ',' + str(root.state.cannibals) + ',' + str(root.state.boat)
      if state in routes:
          if routes[state] < root.depth:
              return
          else:
              routes[state] = root.depth
      else:
          routes[state] = root.depth
      visited.append(root)
  
      if root.state.is_goal():
          sol = root
          return
  
      for child in root.children():
          if child not in visited:
              dfs(child,sol)
  
  visited = []
  routes = {}
  
  def main():
      initial_state = State(3,3,1)
      root = Node(parent = None, state = initial_state,depth = 0)
      sol = Node(parent = None, state = initial_state,depth = 0)
      dfs(root,sol)
      ans = sol.extract_solution()
      print(ans)
  
  
  if __name__ == '__main__':
      main()
  

  PS . 正如@PM 2Ring所说，下次：请在提问时修改你的缩进，这使得阅读代码更容易理解 . 您可以通过选择所有代码，向所有选定行添加选项卡然后复制它来完成此操作 . 在粘贴之前，请确保空行 . :)

  回复于 2024-04-29T05:28:09+08:00