代码之家 › 专栏 › 技术社区 › tidy

如何列举暴力算法的所有可能性?

brute-force algorithm

tidy · 技术社区 · 11 年前

这个问题可能没有具体说明,但我认为它非常重要。当你想解决一个优化问题,但你不太熟悉 dynamic programming 方法,这是你脑海中浮现的第一个想法。

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

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

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

有没有一种系统的通用方法来列出暴力算法的所有可能性?

1 回复 | 直到 11 年前

James Waldby - jwpat7 11 年前

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

回溯是一种通用算法,用于查找某些计算问题的所有(或部分)解,它逐步构建解的候选者,并在确定c不可能完成为有效解时立即放弃每个部分候选者c(“回溯”)。

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

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

推荐文章

Kev1n91 · 在MATLAB中加速暴力求解具有特定均值的分布

7 年前

zniwalla · 今天的算法挑战[结束]

7 年前

reptilianyeti · C++错误:“不匹配运算符<…”

9 年前

Softey · Python RSA Brute强制检查

10 年前

CMPS · 使用深度优先遍历为图形着色

10 年前