實現騎士的遊覽圖，並將其與不同的搜索算法一起使用

Question

我想實現騎士遊，並使用不同的搜索算法運行它，如bfs，dfs，a *等。用戶在棋盤上選擇一個位置，然後事情會完成。問題是在選擇之後，我應該創建整個圖，就像從第一個位置到第二個位置等所有可能的移動，或者我應該一步一步地進行，然後根據其算法，在第一級搜索，然後是下一級兒童的孩子？我希望我的問題對我的英語很清楚並且很抱歉。

Answer 1

在每次迭代中，從隊列中彈出一個節點，直到到達目的地。通過使用列表記錄先前的歷史移動來放棄重複移動。爲了簡化實現，每次都將當前的移動歷史數組推入隊列。這顯然是一個BFS（廣度優先搜索）算法，它將保證找到的第一條路線是最短路線。

---

你不搜索棋盤;搜索展示位置的空間：

初始狀態：沒有騎士被放置

有效舉措：發生在任何空閒的瓷磚騎士

目標狀態：所有的瓦片被佔據或攻擊

基本算法（狀態空間的BFS）：

將初始狀態推送到BFS隊列。 當隊列中有東西時： 從隊列中移除一個狀態。 對於每個未佔用的圖塊： 創建當前狀態的副本。 將一個騎士添加到該瓷磚。 如果新狀態不存在於隊列中： 如果新狀態是目標狀態，則結束。 否則將其添加到隊列中。

Answer 2

如果我正確地理解了這個問題，一個可行的方法不是根據生成後繼狀態來明確地表示遊戲樹，而是通過使用用於生成所有可能的函數的函數來遞歸地保留板的實例並實現搜索移動，執行移動並撤消移動;通過這樣做，遊戲樹的被檢查部分將通過使用調用堆棧來隱含地表示，而回溯步驟通過撤銷最後的移動並從當前的遞歸調用返回來實現。