algorithm - 如何枚举暴力算法的所有可能性？

Question

这个问题可能没有具体说明，但我觉得很重要。当你想解决一个优化问题，而你对动态规划方法不是很熟悉时，它是你脑海中的第一个想法。

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

• 获取列表的最小元素(非常简单)
• 列出集合的所有排列
• 列出集合的所有子集

这些问题都有成熟的方法。但是还有问题不是很清楚:

• 列出两个字符串的所有编辑距离(我的意思不是最短的编辑操作)
• 列出两个序列的所有公共(public)子序列
• 列出括号矩阵链乘法的所有可能性

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

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

Answer 1

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

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other.

你提到的两个问题，
• 列出两个序列的所有公共(public)子序列
• 列出括号矩阵链乘法的所有可能性
可以使用回溯轻松处理。我不确定编辑距离问题。