algorithm - 求解最长路径长度。我的解决方案正确吗？

Question

这是[来自 CLRS] 的问题:

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

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

k =< k'

if 那么最长的路径长度就解决了。如果我们收到“NO”或 k>=k'，则不存在解决方案。

所以 polytime 运行 A + 常量进行比较，然后找到最长的路径长度需要 poly 时间。这也是唯一可能的，因为 G(u,v) 在 Polytime 中运行(在 P 中)，因此 G(u,v,k) 也在 Polytime 中运行(在 P 中)，因此最长路径可以减少为最长路径- length，则longest-path-length在P中。

我们可以用相反的方法解决它，我们所做的是，对 k'=0 到 n 运行 G(u,v,k')，每次检查是否 k==k'，所以我们解决了它. 对此的运行时分析: n*polytime+ n*(常数比较)=polytime

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

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

谢谢你

Answer 1

你的回答是合理的，但我会尝试稍微正式地支持它(以清晰的方式分别格式化案例，更准确地说明多项式时间的含义，诸如此类......)

我唯一想指出的是，在您的第二次简化中(显示决策问题解决了优化问题)，对于 k=0 到 N 的解决方案并不通用。多项式时间是根据输入的长度确定的，因此在 N 是一般数字(例如重量或其他东西)而不是输入中的项目计数的问题中(如本例所示) case) 你需要使用更高级的二进制搜索来确定。