作为编程练习,我正在尝试用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 循环之外是什么导致递归达到最大值?
谢谢你的帮助。
- -
如果您遇到递归深度超出异常,则您要么遇到代码问题,要么需要不同的算法。看起来你的算法是 O(N*N),其中 N 是节点数。N 不需要很大就可以达到极限。
有更好的方法来解决这个问题。