0

这个问题可能没有具体说明，但我认为它非常重要。当您想解决优化问题并且您对方法不是很熟悉时dynamic programming，这是您想到的第一个想法。

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

  • 获取列表的最小元素（非常简单）
  • 列出一个集合的所有排列
  • 列出集合的所有子集

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

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

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

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

4

1 回答 1

2

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

回溯是一种通用算法，用于找到某个计算问题的所有（或部分）解决方案，它逐步构建解决方案的候选者，并在确定 c 不可能完成时放弃每个部分候选者 c（“回溯”）有效的解决方案。

使用回溯的经典教科书示例是八皇后谜题，它要求在标准棋盘上所有八皇后的排列，以便没有皇后攻击任何其他。

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

于 2013-03-25T07:28:35.630 回答