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

Question

可能未指定此问题，但我认为这非常重要。当你想解决一个优化问题，并且你不熟悉dynamic programming方法时，这是你想到的第一个想法。

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

• 获取列表（很简单）
• 列表中选择一个集合的所有排列
• 列表中选择一个集合的所有子集的最小元素

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

• 列表中的两个字符串的所有edit distance（我的意思是不是编辑操作中最短的一个）
• 列表common subsequence两个控制顺序
• 所有列表圆括号matrix chain multiplication
的所有可能性

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

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

Answer 1

Backtracking是查找问题的所有解决方案的最通用方法之一。每维基百科，

回溯查找所有（或部分）的解决方案，一些计算问题的通用算法，即逐步尽快建立考生的解决方案，并放弃每个部分候选人C（“回溯”），因为它确定c不可能完成到一个有效的解决方案。

使用回溯的经典教科书示例是八个皇后拼图，它要求在标准棋盘上安排八个国际象棋皇后，以免皇后攻击任何其他棋王。

你提到的两个问题，
•列表中有两个序列
•列表圆括号矩阵链乘积
的所有可能性可以是所有公共子容易使用回溯处理。我不确定编辑距离问题。