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

[newpuma (還很新)]

第一個關於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
推 krusnoopy: 2-1 建構heap沒有用到遞迴,沒用到什麼策略
→ krusnoopy: 2-2 當然不代表,你舉的背包問題即是
推 krusnoopy: 2-3 此問題相當於在數線上找最多不重疊的區間,每次找[a
→ krusnoopy: ,b]中b最小的選,即可找到最多不重疊的區間,屬於greedy,
→ krusnoopy: 這可能要多查資料(立宇上課說的解法)
→ krusnoopy: 2-4 greedy
推 yupog2003: 1-1這個問題本身不well defined，所以屬於無解
→ yupog2003: 1-3，這兩個問題都是P的問題，P包含於NP，所以他們也是
→ yupog2003: NP的問題
→ yupog2003: 注意，NP為容易驗證的問題，所有P和NP-complete的問題
→ yupog2003: 都是NP問題
→ yupog2003: 我做的題目還不夠多，目前還沒看到不是NP的問題...
→ yupog2003: 1-4，NP，因為他也是屬於容易驗證的問題
→ Gabino: 2-1 heap sort 使用 greedy
推 w181496: 1-2可用Floyd
推 FRAXIS: 1-2 最小 cycle 有特殊名字叫 girth, girth finding 是 P
推 FRAXIS: 最大 Cycle 是 NPC 因為這可以拿來解 Hamiltonian cycle
推 FRAXIS: 1-3 Maximum cut (定義在圖上不是在網路流）是 NPC
→ yupog2003: 感謝F大幫我更正
→ yupog2003: 看成minimum cut了
推 FRAXIS: Maximum flow 是 P，而且其結果可以找出 Minimum cut
推 FRAXIS: 1-4 maximum independent set in an interval graph 是 P
→ aa06697: 1-2 可以用dfs 找到back edge就是cycle了 全部跑完花O(V+
→ aa06697: E) = O(V^3) 是polynomial time
推 FRAXIS: 用 DFS 要如何保證找到最小的 cycle？
推 Transfat: aa大是不是打錯了dfs花O(V+E)=O(V^2)吧