最短路径算法递归

作为一种编程练习，我试图用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循环是什么导致递归达到最大值？
感谢您的帮助。

来源

2012-08-15 Diego

有一个代码审查网站，这是一个Q/A网站。 – 2012-08-15 14:00:31

蟒蛇递归不让你走得很深...可能想看看迭代解决方案 – 2012-08-15 14:03:41

问题是，基于这个问题，我不应该走的很深......还有，感谢代码审查小费。 – Diego 2012-08-15 14:27:01

如果你打的递归深度超过例外，你要么有一个代码问题，或者您需要一个不同的算法。看起来你的算法是O（N * N），其中N是节点的数量。 N不需要非常大才能达到极限。

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

来源

2012-08-15 14:17:28 sizzzzlerz

最短路径算法递归

回答

相关问题