cgv*_*val 3 algorithm complexity-theory
在研究了这两个问题之后,我无法断定它们之间的区别.
汉密尔顿路径
哈密顿路径是图形的两个顶点之间的路径,它只访问每个顶点一次.给定图G和两个不同的节点S和E,是否有在哈密尔顿路径G从S到E？
我发现这个问题是NP-Complete
最短路径
在图论中,最短路径问题是在图中的两个顶点(或节点)之间找到路径使得其组成边缘的权重之和最小化的问题.这个问题是P.
它们之间的实际区别是什么？他们的复杂程度如何计算？
哈密顿路径问题实际上是在图中寻找最长的简单路径.很容易看出这两个问题基本相同(最长的简单路径和哈密顿路径).这个问题确实是一个经典的NP完全问题.
它是NP完全的,因为从另一个(已经证实的)NP-硬问题到这个问题的多项式减少,因此(从多项式约简的传递性)这个问题也是NP-Hard.因为它也在NP中,所以它是NP-Complete.
在另一方面的最短路径是不同的一个,它会询问什么是最短的从A点的方式到B点,这是P中,因为是解决它(多项式算法Dijkstra算法,贝尔曼-福特,BFS对于非加权图).
关于"And how is there complexity calculated?"我假设你的意思是我们如何确定它们的复杂性类 - 在这种情况下,最短路径在P中,因为我们有一个确定性的多项式时间算法来解决它(上面提到的一些),而哈密顿路径的复杂性类是NP-Complete因为它既是NP-Hard(还有来自另一个已证实的NP-Hard问题的多项式减少),也是NP(我们可以在非确定性图灵机上的多项式时间内轻松解决它).
请注意,我们不知道汉密尔顿路径是否在P中,因为我们不知道P = NP.