[理工] 資演 P與NP、演算法策略

看板Grad-ProbAsk作者 (還很新)時間9年前 (2016/12/30 16:52), 9年前編輯推噓11(11推 0噓 15→)
留言26則, 7人參與, 最新討論串1/1
第一個關於P與NP問題是： 1 在一個有負環的圖上找出最短路徑，這樣應該是沒辦法，是屬於NP還是屬於無解？ 2 Find the smallest cycle in a graph, where the edge-weight is 1 for each edge. 若這是一個P問題，那找出最小cycle是用什麼方法？ 那largest cycle是怎麼求得呢 3 在網路流中找出maximum cut為什麼是NP問題，maximum flow才是P問題嗎？ 4 maximum independent set in an interval grapg到底是Np還是無解？ 第二個問題關於演算法策略的問題是： 1 請問Heap-sort有用到什麼演算法策略嗎，我知道建構heap樹是有用到遞迴，這樣可以直 接認定他的策略是divide and conquer嗎 2 無多項式時間解的問題就代表沒有使用到演算法策略嗎？像是0-1揹包問題其實不具多項 式時間解，但我們應該可以說有使用Dynamic programing吧？ 3 一樣是Finding a maximum independent set in an interval graph著到底有沒有解，有 沒有用到什麼策略？ 4 Ford-Fulkerson是使用哪一種演算法策略呢？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.200.186 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483087960.A.345.html ※ 編輯: newpuma (223.140.200.186), 12/30/2016 16:53:41
推
12/30 18:27, , 1F
2-1 建構heap沒有用到遞迴,沒用到什麼策略
12/30 18:27, 1F
→
12/30 18:28, , 2F
2-2 當然不代表,你舉的背包問題即是
12/30 18:28, 2F
推
12/30 18:31, , 3F
2-3 此問題相當於在數線上找最多不重疊的區間,每次找[a
12/30 18:31, 3F
→
12/30 18:32, , 4F
,b]中b最小的選,即可找到最多不重疊的區間,屬於greedy,
12/30 18:32, 4F
→
12/30 18:32, , 5F
這可能要多查資料(立宇上課說的解法)
12/30 18:32, 5F
→
12/30 18:32, , 6F
2-4 greedy
12/30 18:32, 6F
推
12/30 18:59, , 7F
1-1這個問題本身不well defined，所以屬於無解
12/30 18:59, 7F
→
12/30 19:02, , 8F
1-3，這兩個問題都是P的問題，P包含於NP，所以他們也是
12/30 19:02, 8F
→
12/30 19:02, , 9F
NP的問題
12/30 19:02, 9F
→
12/30 19:04, , 10F
注意，NP為容易驗證的問題，所有P和NP-complete的問題
12/30 19:04, 10F
→
12/30 19:04, , 11F
都是NP問題
12/30 19:04, 11F
→
12/30 19:05, , 12F
我做的題目還不夠多，目前還沒看到不是NP的問題...
12/30 19:05, 12F
→
12/30 19:07, , 13F
1-4，NP，因為他也是屬於容易驗證的問題
12/30 19:07, 13F
→
12/30 19:12, , 14F
2-1 heap sort 使用 greedy
12/30 19:12, 14F
推
12/30 19:20, , 15F
1-2可用Floyd
12/30 19:20, 15F
推
12/30 23:02, , 16F
1-2 最小 cycle 有特殊名字叫 girth, girth finding 是 P
12/30 23:02, 16F
推
12/30 23:04, , 17F
最大 Cycle 是 NPC 因為這可以拿來解 Hamiltonian cycle
12/30 23:04, 17F
推
12/30 23:07, , 18F
1-3 Maximum cut (定義在圖上不是在網路流）是 NPC
12/30 23:07, 18F
→
12/30 23:09, , 19F
感謝F大幫我更正
12/30 23:09, 19F
→
12/30 23:10, , 20F
看成minimum cut了
12/30 23:10, 20F
推
12/30 23:10, , 21F
Maximum flow 是 P，而且其結果可以找出 Minimum cut
12/30 23:10, 21F
推
12/31 00:57, , 22F
1-4 maximum independent set in an interval graph 是 P
12/31 00:57, 22F
→
12/31 11:07, , 23F
1-2 可以用dfs 找到back edge就是cycle了 全部跑完花O(V+
12/31 11:07, 23F
→
12/31 11:07, , 24F
E) = O(V^3) 是polynomial time
12/31 11:07, 24F
推
12/31 21:21, , 25F
用 DFS 要如何保證找到最小的 cycle？
12/31 21:21, 25F
推
01/01 17:07, , 26F
aa大是不是打錯了dfs花O(V+E)=O(V^2)吧
01/01 17:07, 26F
‣ 更多 newpuma 的文章
文章代碼(AID): #1OPY1OD5 (Grad-ProbAsk)