3

这是[来自 CLRS] 的问题：

将优化问题 LONGEST-PATH-LENGTH 定义为将无向图的每个实例和两个顶点与两个顶点之间最长简单路径中的边数相关联的关系。定义决策问题LONGEST-PATH = {：G=(V,E)是一个无向图，u,v包含在V中，k >= 0是一个整数，G中存在一条从u到v的简单路径由至少有 k 个边}。证明当且仅当 LONGEST-PATH 包含在 P 中时，优化问题 LONGEST-PATH-LENGTH 可以在多项式时间内求解。

我的解决方案：给定一个算法 A，它可以在多时间内求解 G(u,v)，所以我们在 G(u,v) 上运行 A，如果它返回 'YES' 和 k' 使得 k' 是最长的路径G(u,v)，现在我们要做的就是比较 if

k =< k'

如果然后解决最长路径长度。如果我们收到“NO”或 k>=k'，则不存在解决方案。

所以 polytime 运行 A + 常数进行比较，然后找到最长的路径长度，它需要 poly time。这也是唯一可能的，因为 G(u,v) 在 Polytime (in P) 中运行，因此 G(u,v,k) 也在 polytime (in P) 中运行，因此由于最长路径可以简化为最长路径-长度，那么最长路径长度在 P 中。

我们可以用相反的方式解决它，我们所做的是，运行 G(u,v,k') for k'=0 到 n，每次检查是否 k==k'，所以我们解决了它。运行时分析：n*polytime+ n*(constant comparsion)=polytime

谁能告诉我我的回答是否合理？如果不是，请告诉我哪里出错了

你也能给我一些关于如何学习算法的建议，以及我应该采取什么方法来解决算法问题（或图形问题）

谢谢，麻烦您了

4

1 回答 1

2

你的回答是合理的，但我会尝试正式地支持它（以清晰的方式分别格式化案例，更准确地了解多项式时间的含义，那种东西......）

我想指出的唯一一件事是，在您的第二次缩减（显示决策问题解决了优化问题）中，k=0 到 N 的解决方案并不普遍。多项式时间是根据输入的长度确定的，因此在 N 是一般数字（例如重量或其他东西）而不是输入中的项目计数（如本例中）的问题中，您需要使用可以肯定的是，更高级的二进制搜索。

于 2011-12-09T12:31:11.927 回答