算法/回溯
回溯是一种通用的算法技术，它考虑搜索所有可能的组合以解决优化问题。回溯也称为深度优先搜索或分支限界。通过插入更多关于问题的知识，可以修剪搜索树以避免考虑看起来没有希望的情况。虽然回溯对我们不知道更有效解决方案的难题很有用，但对于其他技术更擅长的解决日常问题来说，它是一个糟糕的解决方案。
然而，动态规划和贪婪算法可以被认为是对回溯的优化，因此回溯背后的通用技术对于理解这些更高级的概念很有用。首先学习和理解回溯技术为这些更高级的技术提供了良好的垫脚石，因为您不必一次学习多个新概念。
回溯方法
|
这种方法足够通用，可以应用于大多数问题。但是，即使小心改进回溯算法，它也可能仍然需要指数时间而不是多项式时间。此外，回溯算法的精确时间分析可能极其困难：相反，给出了可能不紧密的更简单的上限。
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 开头的数字之和，然后每个后续数字是任何数字加上最后一个数字的总和。显示性能改进。）
这个问题没有直接的自相似性，因此问题首先需要进行概括。方法：如果没有自相似性，请尝试概括问题，直到它具有自相似性。
在这里，回溯是已知的最佳解决方案之一。