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

看板Grad-ProbAsk作者 (台灣加油)時間10年前 (2016/01/23 23:17), 10年前編輯推噓12(12推 0噓 32→)
留言44則, 6人參與, 最新討論串1/2 (看更多)
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
推
01/23 23:24, , 1F
你怎麼沒有直接問林立宇XD 不是聽說他蠻熱心
01/23 23:24, 1F
→
01/23 23:26, , 2F
說實在的 交大沒給答案也只能自己猜= = 2.3隨便選
01/23 23:26, 2F
→
01/23 23:28, , 3F
可是 shortest simple path 不是 P 嗎? 還是我哪裡誤會
01/23 23:28, 3F
推
01/23 23:33, , 4F
因為找有負cycle的才會變這樣 可以從上一NPC reduce
01/23 23:33, 4F
推
01/23 23:38, , 5F
等 對耶是simple path 那應該是p可解
01/23 23:38, 5F
推
01/24 02:17, , 6F
NPC吧
01/24 02:17, 6F
推
01/24 09:55, , 7F
simple path還是npc嗎？ 為何咧@@？
01/24 09:55, 7F
→
01/24 10:46, , 8F
推林立宇人超好 simple path的話就是P了
01/24 10:46, 8F
→
01/24 11:20, , 9F
他人真的很好XDD 哈哈 只是題庫班結束了 囧
01/24 11:20, 9F
→
01/24 13:42, , 10F
林立宇有創google group啊 上去問就好
01/24 13:42, 10F
推
01/24 19:11, , 11F
對於任一無向圖 你把每條邊的權重設成 -1
01/24 19:11, 11F
→
01/24 19:11, , 12F
如果 shortest simple path 長度是 |V| - 1 那你就找到了
01/24 19:11, 12F
→
01/24 19:11, , 13F
一條 Hamiltonian path
01/24 19:11, 13F
→
01/24 19:38, , 14F
F大 我認為他要在任意的圖只要滿足條件都成立吧
01/24 19:38, 14F
推
01/24 20:25, , 15F
不太懂 我把任意無向圖 邊的權重設成 -1
01/24 20:25, 15F
→
01/24 20:28, , 16F
然後對於一組 u, v 把 (u,v) 的權重設成 0
01/24 20:28, 16F
→
01/24 20:28, , 17F
(我是假設 (u,v)不在原來的圖中）
01/24 20:28, 17F
→
01/24 20:29, , 18F
這樣圖一定會有負環 (如果 u, v 是在同一個連通元件）
01/24 20:29, 18F
→
01/24 20:29, , 19F
你找到從 u ~ v 長度為 -(|V|-1) 的簡單路徑
01/24 20:29, 19F
→
01/24 20:30, , 20F
就會是原來圖上的從 u 到 v 的 Hamiltonian path 不是嗎？
01/24 20:30, 20F
推
01/24 20:34, , 21F
喔 我沒看到有向圖的條件 不過上面的論述把無向圖換成
01/24 20:34, 21F
→
01/24 20:34, , 22F
有向圖應該也沒關係
01/24 20:34, 22F
→
01/24 20:57, , 23F
你把它條件限制太多了 給一個圖 裏面有正負邊有負
01/24 20:57, 23F
→
01/24 20:58, , 24F
cycle 任兩個點的SP不一定可以像你那樣reduce成解HP
01/24 20:58, 24F
推
01/24 21:00, , 25F
我是要把 HP reduce 到這問題.. 不然要怎麼證 NPC?
01/24 21:00, 25F
→
01/24 21:08, , 26F
可是你把原圖的邊全部改掉了耶...
01/24 21:08, 26F
推
01/24 21:22, , 27F
從一個 HP 的 instance (G, u, v) 我們要判斷有沒有 u ~ v
01/24 21:22, 27F
→
01/24 21:23, , 28F
的 HP 我建立一個 weighted graph G' 這 G' 上面
01/24 21:23, 28F
→
01/24 21:24, , 29F
從 u ~ v 有一條 cost 為 -(|V| - 1) 的 path 若且唯若
01/24 21:24, 29F
→
01/24 21:25, , 30F
原圖 G 上有一條 u ~ v 的 HP 所以 G' 當然跟 G 不同..
01/24 21:25, 30F
→
01/24 22:04, , 31F
SP不一定會經過每個點啊...iff應該証不出來
01/24 22:04, 31F
→
01/24 22:05, , 32F
但把所有Edge的Weight都改成-1, 這樣最短就要走最長了
01/24 22:05, 32F
→
01/24 22:06, , 33F
大概知道F大想reduce的方法, 但又感覺原問題好像跑
01/24 22:06, 33F
→
01/24 22:08, , 34F
Bellman-Ford 就可以解了 這樣就會是P了 囧
01/24 22:08, 34F
→
01/24 22:12, , 35F
好像知道問題了 Bellman-Ford也不能解 所以應該是NP
01/24 22:12, 35F
→
01/24 22:13, , 36F
沒想到一個看起來簡單的問題竟然是NP 囧
01/24 22:13, 36F
→
01/24 22:44, , 37F
如果有解一定有polynomial 的解，但他有可能有負cyc
01/24 22:44, 37F
→
01/24 22:44, , 38F
le則一定無解 ，如果你宣稱你有一個解法可以解，但
01/24 22:44, 38F
→
01/24 22:44, , 39F
遇到負cycle就矛盾了所以才選neither 。
01/24 22:44, 39F
有問林立宇老師了, 這題是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
推
01/24 23:15, , 40F
所以是他當初給錯答案還是原 po 聽錯了..
01/24 23:15, 40F
→
01/24 23:21, , 41F
原來是給錯答案了..
01/24 23:21, 41F
→
01/24 23:21, , 42F
他看錯題目了XD 他漏看"simple" path XDD
01/24 23:21, 42F
→
01/24 23:30, , 43F
我搞錯F大意思了～ 感謝
01/24 23:30, 43F
推
01/24 23:44, , 44F
感謝各位QQ 我也瞭解了
01/24 23:44, 44F
‣ 更多 amge1524 的文章
文章代碼(AID): #1MevcbPY (Grad-ProbAsk)
‣ 更多 amge1524 的文章
文章代碼(AID): #1MevcbPY (Grad-ProbAsk)