為什麼回溯演算法是深度優先的？

顧名思義，為什麼要回溯？ 因為打了一條走不了的路，所以我又回到了上一層，然後往另乙個方向走，就是先探探深度，撞牆後，再往其他方向探查，明明是先探深。

因為你選擇了其中乙個方向繼續前進，所以你會直接遇到某個條件，然後回到之前的起點，再次嘗試另一條路。 如果寬度是優先事項，那麼它應該同時在多個方向上。

我忘了，這門資料結構課程是退還給老師的，好像是按後面的順序來講的！ 對不起！

回溯方法被稱為萬能解決方案，它對許多問題都有很好的效果，例如迷宮。 回溯演算法實際上是乙個深度優先的搜尋嘗試過程，它主要在搜尋嘗試過程中尋找問題的解，當它發現不滿足解條件時，它會“回溯”返回（即遞迴返回）並嘗試另一條路徑。 許多複雜、大規模的問題都可以追溯到這個問題，這就是所謂的“萬能求解法”。

說白了，回顧法就是窮舉法。 回溯方法一般是用遞迴求解的，但當然這也帶來了乙個缺點，時間複雜度一般都比較大

在我看來，回溯演算法是一種很好的理解演算法，類似於DFS，當條件滿足時執行，當條件不滿足時，在另乙個分支上執行回溯，直到遍歷所有結果。 實際上，這是一種依靠倒塌城鎮遞迴的方法。 因此，時間複雜度也很大。

這是一種相對簡單的回溯演算法，是一種遍歷圖的方法。 即：從圖的頂點訪問圖中的所有頂點，每個頂點僅訪問一次（已連線和斷開連線的地圖）。

棋盤是乙個 8x8 的棋盤。 現在把“馬”放在任意指定的方格中，按照“馬”棋的規則移動“馬”（如圖所示，如果空格標為點，則表示西洋棋中的馬移動了“日”字）。 每個方格只需要進入一次，導致“馬”走過棋盤的所有 64 個方格。

這個問題在貪婪演算法中也提到過，其中使用了回溯方法，這是一種易於理解和實現的演算法。

注意：當 int a = x + movex[i] 寫為 x = x + movex[i] 時，這裡犯了乙個錯誤，這相當於不做回溯。

回溯演算法，也稱為啟發式演算法，是一種系統地搜尋問題解決方案的方法。 回溯演算法的基本思想是：從一條路前進，能前進就前進，不能就回去，再試一次。

3. 使用深度優先方法搜尋解空間。 4. 使用極限函式避免移動到無法生成解的子空間。 乙個問題的解空間通常是在尋找問題的解的過程中動態產生的，這是回溯演算法的乙個重要特徵。

1.跳棋問題：33個方格的頂點放置了32個棋子，只有**的頂點是空的，沒有棋子。

西洋棋的規則是，任何乙個棋子都可以水平或垂直跳過相鄰的棋子，輸入乙個空的頂點並捕獲跳過的棋子。 嘗試設計一種演算法來找到一種下棋的方法，這樣最後棋盤上就只剩下一顆棋子了**。 演算法實現提示 使用回溯演算法，每次找到可以行走的棋子時，都可以四處走動並捕捉它。

如果沒有孩子可以走，或者還剩下不止乙個孩子，那就回去走一段可以走的路。 當 31 個被吃掉時，只剩下乙個，程式結束。 2.

今天，它只允許向右跳，不能向左跳。 例如，圖 4（a） 顯示了跳過路線，並列印出所採用的路線。 列印格式為：

0，0->2,1->3,3->1,4->3,5->2,7->4,8…演算法分析：如圖1（b）所示，馬最多有四個方向，如果原始橫坐標為J，縱坐標為I，則四個方向的運動可以表示為：1：

i,j）→（i+2,j+1）； i<3,j<8) 2: （i,j）→（i+1,j+2）； i<4,j<7) 3: （i,j）→（i-1,j+2）； i>0,j<7) 4:

從[1]開始，按照移動規則依次選擇某個方向，如果達到（4,8），則轉到s3，否則繼續尋找到達的下乙個頂點; s3：列印路徑。 演算法設計：

procedure try(i:integer); var j:integer; begin for j:

1 到 4 如果新坐標滿足條件，則開始記錄新坐標; 如果到達目的地，則列印 else try（i+1）; 回歸到前乙個坐標，即回溯; end; end;

回溯是對問題答案的系統搜尋。 為了回溯，您首先需要為問題定義乙個解決方案空間，該空間必須包含至少乙個問題的解決方案（這可能是最優的）。

回溯方法的步驟如下：

1） 定義乙個包含問題解決方案的解決方案空間。

回溯演算法的乙個有趣功能是，在執行搜尋的同時生成解決方案空間。 在搜尋過程中的任何時候，都只保留從起始節點到當前節點的路徑。 因此，回溯演算法的空間要求是 o（從起始節點開始的最長路徑的長度）。

此屬性很重要，因為解空間的大小通常是最長路徑長度的指數或階乘。 因此，如果要儲存所有解決方案空間，那麼再多的空間也不夠用。

在演算法設計方面，回溯演算法的定義是：使用深度優先生成狀態節點並使用剪枝函式的演算法是回溯演算法。

例如，Eight Queens 問題是回溯演算法的典型示例。 八皇后問題生成並遍歷狀態空間樹，根據深度優先順序生成狀態空間節點，所謂深度優先，類似於二叉樹的預序遍歷，如果找不到合適的位置，就會回到狀態空間樹的上層繼續遍歷。 說白了，回溯演算法是一種窮盡的方法。

但是，回溯演算法使用剪枝函式來剪下不太可能達到最終狀態（即應答狀態）的節點。 這減少了狀態空間樹節點的生成;

回溯法又稱啟發式法，處理問題的方式比較委婉，暫時放棄了對問題大小的限制，按一定順序逐一列舉問題的候選解。 當發現當前候選解決方案不太可能是正確的解決方案時，將選擇下乙個候選解決方案。 如果當前候選者松了一口氣，並且能夠滿足除問題大小要求之外的所有其他需求，則當前候選解決方案將繼續擴大大小並繼續探索。

如果候選解決方案滿足所有要求（包括問題的大小），則該解決方案是問題的解決方案。 在啟發式演算法中，丟棄當前候選解決方案並轉到下乙個候選解決方案的過程稱為回溯。 擴充套件當前候選解決方案以繼續啟發式的過程稱為前向啟發式。

1）定義給定問題的解決方案空間。

為了找到問題的正確解決方案，回顧法首先會委婉地測試某種可能的情況。 在測試的過程中，一旦我們發現原來選擇的假設情況不正確，我們就會立即自覺地後退一步，做出新的選擇，然後繼續向前測試，依此類推，直到我們有了解決方案或證明沒有解決方案。

以下是回溯的 3 個要素。

以下是影響演算法效率的因素：

為了縮小範圍，讓我們使用所示的 8x8 西洋棋的八位皇后進行分析。 根據西洋棋的規則，女王的攻擊是水平的、垂直的和對角線的。

皇后可以攻擊同一列中的所有其他棋子，因此可以推斷出每列只能有 1 個皇后，即每個皇后佔據一列。 棋盤上一共有8列，只有8位皇后。

為了放置符合條件的8個皇后的布局，可以按以下步驟進行：

擴容到n行n列也是一樣，下面用回溯的方法解決n個queen問題： execute：