最短路徑算法遞歸

作爲一種編程練習，我試圖用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

最短路徑算法遞歸

回答

相關問題