如何模擬這個深度第一搜索解決方案

我有一個益智遊戲，有一個State取決於拼圖中的棋子的排列方式。我正在嘗試使用深度優先搜索來解決這個難題，但是我對如何處理它感到困惑。根據我的理解，深度優先搜索將搜索圖形以找到解決方案，但我的難題不是以圖形的形式。我所知道的是目前的狀態和從該州可以實現的狀態。如何模擬這個深度第一搜索解決方案

我是否應該建立這個圖表，因爲我發現了我目前所處狀態的所有可能狀態？但是，這不會破壞目的 - 首先用各種可能的狀態構建圖表，然後搜索整個圖表以找出解決方案？

我有一種方法，可以使用Move探索當前狀態的所有可能的狀態，我相信我會派上用場，除非我不知道如何使用它。

來源

2015-10-12 Brejuro

您不必顯式構建圖形。在概念上，您可以將問題表示爲圖形，其中節點是狀態，邊是狀態之間的轉換。深度優先搜索是一直跟隨邊緣，直到達到最終狀態，然後再移動到另一邊。所以它看起來是這樣的（僞）：

def search(state): 
    if is_end_state(state): 
     # search down this branch finished, do something 
     return something 

    for move in possible_moves_from(state): 
     search(apply_move(state, move))

你最終會隱含構建圖形，通過遞歸調用和堆棧狀態，當您去。

請注意，如果您有循環（例如，您可以向左移動，然後向右移動回到完全相同的狀態），那麼您將不得不跟蹤已經訪問過的狀態，否則將永遠循環。事情是這樣的：

def search(state, seen_states): 
    if state in seen_states: 
     # already visited, don't visit again 
     return 

    seen_states.add(state) 

    # same as before:  
    if is_end_state(state): 
     return something 

    for move in possible_moves_from(state): 
     search(apply_move(state, move), seen_states)

在如何實現這個方面，我建議你seen_states是HashSet<State>，你讓你的State哈希的。

來源

2015-10-12 17:44:05 Claudiu

因此，基本上這隻會搜索一條路徑，然後倒帶，直到找到解決方案？我如何判斷當前狀態中是否存在可能的狀態之一？我的意思是，如果我將棋子移位得足夠多，我會得到重複的狀態，並且會永久循環。 – Brejuro

@Brejuro：查看更新。你只需要跟蹤已經看到的狀態，如果你已經看到它，就不要去那裏。通過保持一套。 – Claudiu

感謝您的幫助，將它作爲圖形進行建模是否合理？就像我在添加節點和邊緣一樣？我計劃也實現其他搜索算法，所以我不確定使用圖形實現是否有用。 – Brejuro

聽起來像深度先是我的錯誤方式。如果你有一個國家，並且你知道你可以從那個國家得到的所有國家，那麼首先寬度可能會更合適。有了BFS，你就會知道你所要的第一個解決方案就是最短的解決方案。

如果您確定有解決方案，那麼您不必擔心無限遞歸，因爲無論如何，在循環中捕獲的任何路徑不會是最短的，它們只會導致不必要的工作。

使用隊列的迭代解決方案將工作。

/** pseudocode **/ 
Queue q = new LinkedList(); 
q.put(myState) 
while (!q.isEmpty()) { 
    State s = q.remove(); 
    if (endState.equals(s)) { 
    return something; 
    } 
    for (State newState : s.getNextStates()) { 
    q.add(newState); 
    } 
}

如果你想要去的深度優先搜索，然後只需將隊列更改爲一個堆棧，但那麼你將不得不應對週期。

如果您的隊列項目是一個包含當前狀態路徑而不僅僅是當前狀態的包裝，那麼您可以輕鬆到達爲最短路徑穿過的深度和路徑（或者至少第一最短路徑如果存在多條相同深度的路線，則會發現路線。）

來源

2015-10-12 20:12:54 digitaljoel

如何模擬這個深度第一搜索解決方案

回答

相關問題