0

作为一个编程练习，我正在尝试用 Python 解决一个益智游戏。为此，我使用了一种递归算法，我认为这是一种深度优先搜索实现。我的问题是达到最大递归限制时出现运行时错误，我还没有弄清楚如何解决它。

我看过关于游戏和算法的不同帖子，但我没有在这个设置中重新编码，而是希望对我所写的内容有所帮助。所以这是我的代码的伪简化版本。

# Keep track of paths that I have found for given states. 
best_paths = dict()

def find_path(state, previous_states = set()):

  # The output is a tuple of the length of the path and the path.
  if state in previous_states:
    return (infty,None)
  previous_states = copy and update with state

  if state in target_states: 
    best_paths[state] = (0,[])

  if state in best_paths:
    return best_paths[state]

  possible_moves = set((piece,spaces) that can be moved)
  (shortest_moves,shortest_path) = (infty,None)
  for (piece,spaces) in possible_moves:
    move_piece(piece,spaces)
    try_state = the resulting state after moving the piece
    (try_moves,try_path) = find_path(try_state,previous_states)

    if try_moves < shortest_moves:
      shortest_moves = try_moves + 1
      shortest_path  = try_path + [(piece,spaces)]

    # Undo the move for the next call
    move_piece(piece,-spaces)

  if shortest_moves < infty:
    best_paths[state] = shortest_path

  return (best_moves, shortest_path)

所以我的问题是，如果在 for 循环之外返回是什么导致递归达到最大值？
感谢您的帮助。

    -
4

1 回答 1

0

如果您遇到递归深度超出异常，则您可能遇到代码问题或需要不同的算法。看起来你的算法是 O(N*N) 其中 N 是节点数。N 不需要很大就可以达到极限。

有更好的方法来解决这个问题。

于 2012-08-15T14:17:28.410 回答