作者suck5566bird (5566最愛suck183)
看板Prob_Solve
標題[問題] 漢米耳頓問題
時間Sun Jan 13 21:30:56 2008
想請問一下
如果要用Computation theory裡的證明來證
有漢米爾頓路徑若已知道是NP-HARD
怎麼說明全都是正的Weight的有向圖裡找最長路徑也是NP-HARD?
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.113
1F：推 march20:把 Hamilton Cycle map 到你說的這個問題即可 01/14 05:45
2F：推 march20:hint: 最長路徑什麼時候會是 hamilton path 01/14 05:47
3F：推 march20:口也, 第一個推文把 cycle 改成 path XD 01/14 05:47