求解最长路径长度。我的解决方案正确吗？
这是问题 [来自 CLRS]：
将优化问题 LONGEST-PATH-LENGTH 定义为以下关系： 将无向图的每个实例和两个顶点与数字相关联 两个顶点之间最长简单路径中的边数。定义决策 问题 LONGEST-PATH = {: G=(V,E) 是一个无向 图，V中包含u,v，k>=0为整数，存在简单路径 G 中从 u 到 v 至少由 k 个边组成}。表明优化问题 LONGEST-PATH-LENGTH 可以在多项式时间内求解当且仅当 LONGEST-PATH包含在P中。
我的解决方案： 给定一个算法 A，它可以在多时间中求解 G(u,v)，因此如果它返回“YES”和 k'，我们就在 G(u,v) 上运行 A，这样 k' 是 G(u,v) 中的最长路径，v），现在我们要做的就是比较如果
k =< k'
最长路径长度被解决，如果我们收到“NO”或k>=k'，那么不存在解决方案，
因此需要运行A +常数进行比较 。 ，然后找到最长的这也是唯一可能的，因为 G(u,v) 在 Polytime 中运行（在 P 中），因此 G(u,v,k) 也在 Polytime 中运行（在 P 中），因此最长的路径可以减少到最长路径长度，那么最长路径长度在 P 中。
我们可以用相反的方式解决它，我们所做的是，运行 G(u,v,k')，其中 k'=0 到 n，每次检查是否k==k'，所以我们解决了 它。 运行时分析： n*polytime+ n*(constant comparsion)=polytime
有人能告诉我我的答案是否合理吗？如果没有，请告诉我哪里出了问题，
你也可以给我一些关于如何学习算法的建议，以及我应该采取什么方法来解决算法问题（或图形问题），
谢谢
This is the question [From CLRS]:
Define the optimization problem LONGEST-PATH-LENGTH as the relation that
associates each instance of an undirected graph and two vertices with the number
of edges in a longest simple path between the two vertices. Define the decision
problem LONGEST-PATH = {: G=(V,E) is an undirected
graph, u,v contained in V, k >= 0 is an integer, and there exists a simple path
from u to v in G consisting of at least k edges}. Show that the optimization problem
LONGEST-PATH-LENGTH can be solved in polynomial time if and only if
LONGEST-PATH is contained in P.
My solution:
Given an algorith A, that can solve G(u,v) in polytime, so we run the A on G(u,v) if it returns 'YES" and k' such that k' is the longest path in G(u,v), now all we have to do it compare if
k =< k'
if then the longest path length is solved. If we recieve "NO" or k>=k', then there exists no solution.
so polytime to run A + constant for comparsion, then to find the longest path length it takes poly time. Also this is only possible since G(u,v) runs in Polytime (in P), thus G(u,v,k) runs also in polytime (in P), therefore since longest path can be reduced to longest-path-length, then longest-path-length is in P.
we can solve it the oposite way, what we do is, run G(u,v,k') for k'=0 to n, every time check if the k==k', is so we solved it.
run time analysis for this:
n*polytime+ n*(constant comparsion)=polytime
Can someone tell me if my answer is reasonable? if not please tell me where i've gone wrong
Also can you give me some advice to how to study algorithms ,and what approch i should take to solve a algorith question (or a graph question)
please and thankyou
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
你的回答是合理的，但我会尝试稍微正式地支持它（以清晰的方式分别格式化案例，更准确地了解多项式时间的含义，诸如此类的东西......）
我唯一想要的需要指出的是，在第二次简化中（显示决策问题解决了优化问题），k=0 到 N 的解决方案并不通用。多项式时间是根据输入的长度来确定的，因此在 N 是一般数字（例如重量或其他东西）而不是输入中的项目计数的问题中（如本例所示）情况）你需要使用更高级的二分搜索来确定。
Your answer is reasonable but I would try to shore it up a little bit formally (format the cases separately in a clear manner, be more precise about what polynomial time means, that kind of stuff...)
The only thing that I would like to point out is that in your second reduction (showing the decision problem solves the optimization problem) the for k=0 to N solution is not general. Polynomial time is determined in relation to the length of input so in problems where N is a general number (such as weight or something) instead of a number of a count of items from the input (as in this case) you need to use a more advanced binary search to be sure.