演算法/回溯
回溯是一種通用的演算法技術，它考慮搜尋所有可能的組合以解決最佳化問題。回溯也稱為深度優先搜尋或分支限界。透過插入更多關於問題的知識，可以修剪搜尋樹以避免考慮看起來沒有希望的情況。雖然回溯對我們不知道更有效解決方案的難題很有用，但對於其他技術更擅長的解決日常問題來說，它是一個糟糕的解決方案。
然而，動態規劃和貪婪演算法可以被認為是對回溯的最佳化，因此回溯背後的通用技術對於理解這些更高階的概念很有用。首先學習和理解回溯技術為這些更高階的技術提供了良好的墊腳石，因為您不必一次學習多個新概念。
回溯方法
|
這種方法足夠通用，可以應用於大多數問題。但是，即使小心改進回溯演算法，它也可能仍然需要指數時間而不是多項式時間。此外，回溯演算法的精確時間分析可能極其困難：相反，給出了可能不緊密的更簡單的上限。
LCS 問題類似於 Unix "diff" 程式所做的。Unix 中的 diff 命令將兩個文字檔案A 和B 作為輸入，並輸出A 和B 之間的逐行差異。例如，diff 可以顯示A 中缺少的行已新增到B 中，以及A 中存在但在B 中刪除的行。目標是獲得一個可以用來將A 轉換為B 的新增和刪除列表。對這個問題過於保守的解決方案會說A 中的所有行都被刪除了，而B 中的所有行都被添加了。雖然這會在粗略的意義上解決這個問題，但我們關心的是實現正確轉換所需的最小新增和刪除次數。考慮如何自己實現這個問題的解決方案。
LCS 問題，而不是處理文字檔案中的行，而是關心在兩個不同的陣列之間找到共同的項。例如，
let a := array {"The", "great", "square", "has", "no", "corners"}
let b := array {"The", "great", "image", "has", "no", "form"}
我們要找到在a 和b 中以相同順序找到的項的最長子序列。a 和b 的 LCS 是
- "The", "great", "has", "no"
現在考慮另外兩個序列
let c := array {1, 2, 4, 8, 16, 32}
let d := array {1, 2, 3, 32, 8}
這裡，c 和d 有兩個最長的公共子序列
- 1, 2, 32；和
- 1, 2, 8
注意
- 1, 2, 32, 8
不是一個公共子序列，因為它只是一個d 的有效子序列，而不是c（因為c 在 32 之前有 8）。因此，我們可以得出結論，對於某些情況，LCS 問題的解決方案並不唯一。如果我們有更多關於序列的資訊，我們可能更喜歡一個子序列而不是另一個：例如，如果序列是計算機程式中的文字行，我們可能會選擇保持函式定義或配對註釋分隔符完整的子序列（而不是選擇在語法中未配對的分隔符）。
在頂層，我們的問題是實現以下函式
// lcs -- returns the longest common subsequence of a and b function lcs(array a, array b): array
它以兩個陣列作為輸入，並輸出子序列陣列。
如何解決這個問題？您可以從注意到如果兩個序列以相同的詞開頭，那麼最長的公共子序列總是包含那個詞。您可以自動將該詞新增到您的列表中，並且您只需要將問題簡化為找到其餘兩個列表的最長公共子集。因此，問題變小了，這很好，因為它表明取得了進展。
但是，如果兩個列表沒有以相同的詞開頭，那麼a 中的第一個元素或b 中的第一個元素，或兩者都不屬於最長的公共子序列。但是，其中一個可能在裡面。如何確定哪一個（如果有）要新增？
該解決方案可以用回溯方法來思考：嘗試兩種方式看看！無論哪種方式，兩個子問題都在操作更小的列表，因此您知道遞迴最終會終止。哪個試驗導致更長的公共子序列就是贏家。
我們不透過從陣列中刪除該項來“丟棄”它，而是使用陣列切片。例如，切片
- a[1,..,5]
表示元素
- {a[1]，a[2]，a[3]，a[4]，a[5]}
陣列本身的陣列。如果您的語言不支援切片，您將不得不將開始和/或結束索引與整個陣列一起傳遞。這裡，切片只有以下形式
- a[1,..]
它在使用 0 作為陣列中第一個元素的索引時，會產生一個不包含第 0 個元素的陣列切片。（因此，此演算法的非切片版本只需要傳遞開始有效索引，並且該值必須從完整陣列的長度中減去才能獲得偽切片的長度。）
// lcs -- returns the longest common subsequence of a and b
function lcs(array a, array b): array
if a.length == 0 OR b.length == 0:
// if we're at the end of either list, then the lcs is empty
return new array {}
else-if a[0] == b[0]:
// if the start element is the same in both, then it is on the lcs,
// so we just recurse on the remainder of both lists.
return append(new array {a[0]}, lcs(a[1,..], b[1,..]))
else
// we don't know which list we should discard from. Try both ways,
// pick whichever is better.
let discard_a := lcs(a[1,..], b)
let discard_b := lcs(a, b[1,..])
if discard_a.length > discard_b.length:
let result := discard_a
else
let result := discard_b
fi
return result
fi
end
在後面的部分中，將改進為 Dijkstra 演算法。
如果您已經找到了“更好”的東西，並且您正在一個永遠不會像您已經看到的那樣好的分支上，您可以提前終止該分支。（要使用的示例：以 1 2 開頭的數字之和，然後每個後續數字是任何數字加上最後一個數字的總和。顯示效能改進。）
這個問題沒有直接的自相似性，因此問題首先需要進行概括。方法：如果沒有自相似性，請嘗試概括問題，直到它具有自相似性。
在這裡，回溯是已知的最佳解決方案之一。