回溯演算法 (Backtracking)#

回溯演算法（Backtracking）是一種透過試錯來尋找問題解的演算法策略，本質上是帶有剪枝功能的深度優先搜尋（DFS）。

核心思維#

回溯法的精髓：嘗試 ➡️ 檢查 ➡️ 遞迴 ➡️ 失敗則撤銷

這是對解空間樹的深度優先走訪，遇到死路就「回溯」到上一步嘗試其他可能。

回溯三要素#

要素說明
選擇列表當前可做的選擇
路徑已經做出的選擇
結束條件到達決策樹底層的條件

與其他演算法的關係#

演算法特點效率
暴力搜尋窮舉所有可能最低
回溯法DFS + 剪枝中等
動態規劃記憶化 + 最優子結構最高（適用時）

回溯法是暴力搜尋的最佳化版本，透過剪枝提前排除無效分支。

跨倉庫導讀#

Backward 近似演算法與鬆弛 回溯演算法原理 Forward