[理工] 103 交大資演 NP問題

[amge1524 (台灣加油)]

Assume P != NP

For each of the following problems, decide whether it is a P-problem or an
NP-hard (or NP-Complete) problem, or neither.

(1) Find a shortest simple path between two nodes in a directed graph with
negative and/or postive edge weights, and containing negative weight cycles.

想請教一下板上各位榜首大哥大姐, 這題林立宇題庫班的時候答案給 neither

原因是因為負 cylce 會讓這個問題變得沒有意義, 但題目已經說明是simple path了

path 本身的定義就是不包含重複點, 不知道各位大哥哥大姊姊會怎麼解釋這題 ~ 感恩

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.133.195.20
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1453562277.A.662.html
推 goldflower: 你怎麼沒有直接問林立宇XD  不是聽說他蠻熱心
→ goldflower: 說實在的  交大沒給答案也只能自己猜= =  2.3隨便選
→ amge1524: 可是 shortest simple path 不是 P 嗎? 還是我哪裡誤會
推 goldflower: 因為找有負cycle的才會變這樣  可以從上一NPC reduce
推 goldflower: 等  對耶是simple path  那應該是p可解
推 FRAXIS: NPC吧
推 goldflower: simple path還是npc嗎？ 為何咧@@？
→ jerry031181: 推林立宇人超好  simple path的話就是P了
→ amge1524: 他人真的很好XDD 哈哈 只是題庫班結束了 囧
→ yaxauw: 林立宇有創google group啊 上去問就好
推 FRAXIS: 對於任一無向圖 你把每條邊的權重設成 -1
→ FRAXIS: 如果 shortest simple path 長度是 |V| - 1 那你就找到了
→ FRAXIS: 一條 Hamiltonian path
→ jerry031181: F大 我認為他要在任意的圖只要滿足條件都成立吧
推 FRAXIS: 不太懂 我把任意無向圖 邊的權重設成 -1
→ FRAXIS: 然後對於一組 u, v 把 (u,v) 的權重設成 0
→ FRAXIS: (我是假設 (u,v)不在原來的圖中）
→ FRAXIS: 這樣圖一定會有負環 (如果 u, v 是在同一個連通元件）
→ FRAXIS: 你找到從 u ~ v 長度為 -(|V|-1) 的簡單路徑
→ FRAXIS: 就會是原來圖上的從 u 到 v 的 Hamiltonian path 不是嗎？
推 FRAXIS: 喔 我沒看到有向圖的條件 不過上面的論述把無向圖換成
→ FRAXIS: 有向圖應該也沒關係
→ jerry031181: 你把它條件限制太多了 給一個圖 裏面有正負邊有負
→ jerry031181: cycle 任兩個點的SP不一定可以像你那樣reduce成解HP
推 FRAXIS: 我是要把 HP reduce 到這問題.. 不然要怎麼證 NPC?
→ jerry031181: 可是你把原圖的邊全部改掉了耶...
推 FRAXIS: 從一個 HP 的 instance (G, u, v) 我們要判斷有沒有 u ~ v
→ FRAXIS: 的 HP  我建立一個 weighted graph G' 這 G' 上面
→ FRAXIS: 從 u ~ v 有一條 cost 為 -(|V| - 1) 的 path 若且唯若
→ FRAXIS: 原圖 G 上有一條 u ~ v 的 HP 所以 G' 當然跟 G 不同..
→ jerry031181: SP不一定會經過每個點啊...iff應該証不出來
→ amge1524: 但把所有Edge的Weight都改成-1, 這樣最短就要走最長了
→ amge1524: 大概知道F大想reduce的方法, 但又感覺原問題好像跑
→ amge1524: Bellman-Ford 就可以解了 這樣就會是P了 囧
→ amge1524: 好像知道問題了 Bellman-Ford也不能解 所以應該是NP
→ amge1524: 沒想到一個看起來簡單的問題竟然是NP 囧
→ weber6669650: 如果有解一定有polynomial 的解，但他有可能有負cyc
→ weber6669650: le則一定無解 ，如果你宣稱你有一個解法可以解，但
→ weber6669650: 遇到負cycle就矛盾了所以才選neither 。
有問林立宇老師了, 這題是NP沒錯, 附上林立宇老師的說法

因為 longest path problem 可以 reduce 到這個問題的 decision 版本:
在限制 instance graph 含有正 cycle 的情形下,
longest path problem 仍為 NP-complete
所以將 LP 問題之 problem instance G 中所有邊的 weight 皆取負
則可成為此問題的一個 problem instance G'
這樣找到 G' 的 shortest simple path 就相當於找到 G 的 longest simple path
※ 編輯: amge1524 (220.133.195.20), 01/24/2016 22:55:21
推 FRAXIS: 所以是他當初給錯答案還是原 po 聽錯了..
→ FRAXIS: 原來是給錯答案了..
→ amge1524: 他看錯題目了XD 他漏看"simple" path XDD
→ jerry031181: 我搞錯F大意思了～  感謝
推 goldflower: 感謝各位QQ  我也瞭解了