[問題] 漢米耳頓問題

看板Prob_Solve作者 (5566最愛suck183)時間18年前 (2008/01/13 21:30), 編輯推噓3(3推 0噓 0→)
留言3則, 1人參與, 最新討論串1/1
想請問一下 如果要用Computation theory裡的證明來證 有漢米爾頓路徑若已知道是NP-HARD 怎麼說明全都是正的Weight的有向圖裡找最長路徑也是NP-HARD? -- -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.113
推
01/14 05:45, , 1F
把 Hamilton Cycle map 到你說的這個問題即可
01/14 05:45, 1F
推
01/14 05:47, , 2F
hint: 最長路徑什麼時候會是 hamilton path
01/14 05:47, 2F
推
01/14 05:47, , 3F
口也, 第一個推文把 cycle 改成 path XD
01/14 05:47, 3F
‣ 更多 suck5566bird 的文章
文章代碼(AID): #17YXAHGb (Prob_Solve)