如何为蛮力算法枚举所有可能性？

Question

这个问题可能没有具体说明，但我认为很重要。当您想要解决一个优化问题而又不太熟悉动态编程方法时，首先想到的是它。

我可以举一些简单的例子：

• 获取列表的min元素（非常简单）
• 列出集合的所有置换
• 列出集合的所有子集

这些问题都有成熟的解决方法。但也有问题不是很清楚：

• 列出两个字符串的所有编辑距离（我指的不是编辑操作中最短的一个）
• 列出两个序列的所有公共子序列
• 列出括号矩阵链乘法
的所有可能性

我不知道用蛮力法解决这些问题。我的问题是：

是否有一个系统的通用方法来用暴力算法列出所有的可能性？

Answer 1

回溯是寻找问题所有解决方案的最一般方法之一。根据维基百科，

回溯是一种用于寻找某一计算问题的全部（或部分）解的通用算法，它增量地构建候选解，一旦确定c不可能完成到有效解，就放弃每个部分候选c（“回溯”）。

使用回溯的经典教科书例子是八个皇后拼图，它要求在一个标准棋盘上排列八个棋后，这样就不会有皇后攻击任何其他棋后。