[理工] NP問題

看板Grad-ProbAsk作者 (O_O)時間7年前 (2017/02/07 12:35), 7年前編輯推噓8(8推 0噓 18→)
留言26則, 5人參與, 最新討論串1/3 (看更多)
想請教三個問題，是P還是NP 1.Find a positive weight directed cycle in a weighted directed graph 2.（修正）Find the smallest cycle in a graph, where the edge-weight is 1 for e ach edge 3.The 2-CNF-Satisfiability problem 我都認為是NP，不過爬文好像認為是P，想請教一下@@ （出自交大103資演） -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.99 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486442120.A.03C.html
推
02/07 12:39, , 1F
1.weight取負再跑bellman ford可測負cycle 所以是P
02/07 12:39, 1F
所以是只要測出有cycle就好嗎？
→
02/07 12:40, , 2F
2. run Edmond Karp algo可求
02/07 12:40, 2F
二打錯了，我應該是要問 Find the smallest cycle in a graph, where the edge-weight is 1 for each edge
→
02/07 12:41, , 3F
3. 我直接背…
02/07 12:41, 3F
推
02/07 12:42, , 4F
2cnf是特例 可以用配置圖算出有解無解 一定是P
02/07 12:42, 4F
→
02/07 12:43, , 5F
3cnf以上都可以reduce成2sat 所以是NPC
02/07 12:43, 5F
原來如此！
推
02/07 12:52, , 6F
2cnf可以畫圖解
02/07 12:52, 6F
推
02/07 12:56, , 7F
三個都p
02/07 12:56, 7F
→
02/07 13:42, , 8F
1. 是跑topological吧......
02/07 13:42, 8F
啊，是用DFS然後看back edge？ ※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 13:46:02
→
02/07 13:48, , 9F
都可以找cycle, 至於要正的話可以再額外處理一下
02/07 13:48, 9F
Topological跑完不是是求出先後順序嗎，要如何化為找positive cycle呢？ ※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 13:50:44
推
02/07 13:54, , 10F
2就改良一下floyd shall,看對角線的值就可以知道最小cyc
02/07 13:54, 10F
→
02/07 13:54, , 11F
le大小多少
02/07 13:54, 11F
推
02/07 14:03, , 12F
1一般應該都是找有無cycle, 找cycle在那這種進階的是屬
02/07 14:03, 12F
→
02/07 14:03, , 13F
於很難的問題(以前修演算法問助教得到的答案
02/07 14:03, 13F
→
02/07 14:04, , 14F
抱歉，我要修正一下，topological 可以判斷是否有cycle
02/07 14:04, 14F
→
02/07 14:05, , 15F
無法找。至於找cycle，例如bellmen-ford，可以從pred
02/07 14:05, 15F
→
02/07 14:05, , 16F
去尋找，但也僅限於找到"一個"
02/07 14:05, 16F
→
02/07 14:06, , 17F
也如同你說的，可以用DFS去改良，搭配back edge去找
02/07 14:06, 17F
→
02/07 14:06, , 18F
positive cycle
02/07 14:06, 18F
推
02/07 14:07, , 19F
正想回這個XD topological無法做代表一定有cycle 故可以
02/07 14:07, 19F
→
02/07 14:07, , 20F
拿來判斷有無
02/07 14:07, 20F
→
02/07 14:07, , 21F
但難的是找到全部的 cycle
02/07 14:07, 21F
推
02/07 14:07, , 22F
應該是是說，有cycle沒辦法做出topological order吧，說
02/07 14:07, 22F
→
02/07 14:08, , 23F
用topological sort判斷有無cycle好像怪怪的
02/07 14:08, 23F
→
02/07 14:08, , 24F
對我就是要說HERO大講的XD
02/07 14:08, 24F
→
02/07 14:10, , 25F
兩個是等價的
02/07 14:10, 25F
→
02/07 14:11, , 26F
痾,有點會錯意，但其實我就是這個意思...
02/07 14:11, 26F
懂！感謝各位解惑！ ※ 編輯: ssssIssss (140.112.25.99), 02/07/2017 14:27:51
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1OcKw80y (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
理工
8
26
[理工] NP問題 NP問題
ssssIssss
7年前, 02/07
理工
1
3
[理工] NP問題 NP問題
sooge
5年前, 01/20
理工
7
23
[理工] NP問題 NP問題
ponponjerry
5年前, 01/25
在新視窗開啟完整討論串 (共3篇)
‣ 更多 ssssIssss 的文章
文章代碼(AID): #1OcKw80y (Grad-ProbAsk)