如何使用廣度優先搜索解決難題？

Question

我在幾個學期前就讀過這門課，但當時我沒學到太多東西。我觀看了MIT關於廣度優先搜索的講座。我從中學到了很多東西，但它只是教會了我BFS是搜索圖的好算法，真棒。我需要解決一個難題。

所以我用C++編寫了這個謎題，但現在我需要找出計算機解決問題的方法。根據我的理解，我將不得不讓計算機將這個難題的所有狀態生成爲圖形，然後讓計算機使用BFS來查找已解決的狀態？我如何計算我的謎題有多少個頂點和邊？我所說的謎題是「餅乾桶三角遊戲」。任何幫助將不勝感激如何解決這個壞男孩。

對不起，我沒有提到這個難題的工作原理。因此，您會得到一個帶有14個掛鉤和15個位置的三角形，外觀與此類似：

* 
    2 3 
    4 5 6 
7 8 9 A 
B C D E F 

*其中*表示空白。現在，有點像跳棋，你只能在另一個釘上跳到空的空間，所以在這裏只有兩個有效的移動，4比1或6比1，中間釘被移除，導致：

1 
    2 * 
    4 5 * 
7 8 9 A 
B C D E F 

跳躍栓釘6比1

之後你繼續這樣做，直到只有一個掛留在董事會。

Answer 1

下面是標準的做法，以這樣的狀態空間搜索問題：

創建可以產生下一個可能狀態的功能： 此功能需要能夠採取某種信息代表董事會，並返回可能會發生的舉動清單（或由此產生的董事會）。例如，您可以遍歷每個掛鉤，計算給定掛鉤可能生成的移動，並將它們追加到列表中，直到您檢查完所有移動。

使用BFS以生成/搜索圖： 初始化當前節點到起始狀態，然後啓動廣度優先搜索。對於每個節點，計算下一個可能的狀態並將它們添加到搜索隊列的末尾。保留已添加到隊列中的每個狀態的字典（因爲它比列表更有效）。如果您生成詞典中的一個，請丟棄它而不是編輯它。最終，你會到達一個只有1個掛鉤的董事會，此時你的搜索將取得成功。

這是通過廣度優先搜索解決難題的標準方法。您不需要事先知道有多少個頂點和邊，因爲您的代碼會隨着它的生成而生成圖。請注意，它不會自動生成狀態空間的完整圖形。爲了做到這一點，每次出現重複棋盤狀態時都需要添加邊緣。