[理工] 演算法 NP COMPLETE

看板Grad-ProbAsk作者 (Mistel)時間6年前 (2019/10/01 00:33), 編輯推噓1(1推 0噓 14→)
留言15則, 2人參與, 6年前最新討論串1/1
第25題 請問SAT到底是特別指3-SAT還是所有的satisfiability problem ？ 如圖 https://i.imgur.com/7rf0leg.jpg
https://i.imgur.com/Ulb09MI.jpg
圖一詳解範例舉2-SAT不是NP-COMPLETE 但圖2(c)選項說3-SAT problem as difficult as SAT 看過維基，SAT應該是3-SAT？ 第14題 https://i.imgur.com/FJaOnAV.jpg
請問problem 2為什麼是shortest path problem？ 即使使用folyd warshall也不會保證拜 訪所有邊恰一次吧？ 第16題 https://i.imgur.com/VkAnOZn.jpg
https://i.imgur.com/jeJCd6c.jpg
請問選項（2），有負cycle不是無解嗎？為什麼是NP-COMPLETE？ 再請問選項（9）的interval graph是什麼？ 另外，選項（5）跟前面第14題的問題2差異點是什麼呢？ 懷疑人生.... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.50.75 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1569861224.A.F24.html
→
10/01 08:09, 6年前 , 1F
沒特別指名應該就是全部
10/01 08:09, 1F
→
10/01 08:15, 6年前 , 2F
如果這樣說的話2c看起來無誤？
10/01 08:15, 2F
→
10/01 08:16, 6年前 , 3F
sat是指某個公式是不是satisfiability 應該沒特別要求幾個
10/01 08:16, 3F
→
10/01 08:50, 6年前 , 4F
14我想看一下完整的題目
10/01 08:50, 4F
→
10/01 09:19, 6年前 , 5F
16.2他有提到 正權重longest path等價於負權重shortest path
10/01 09:19, 5F
→
10/01 09:21, 6年前 , 6F
interval graph就是用一些實數長度的線組成的graph
10/01 09:21, 6F
推
10/01 11:04, 6年前 , 7F
14 因為是 undirected graph 所以每條邊 weight 都是 1
10/01 11:04, 7F
→
10/01 11:05, 6年前 , 8F
16 (2) 題目已經說了 是 shortest simple path
10/01 11:05, 8F
→
10/01 11:06, 6年前 , 9F
所以有解 無解的是找 shortest path 因為你可以在
10/01 11:06, 9F
→
10/01 11:06, 6年前 , 10F
negative cycle 上一直繞圈
10/01 11:06, 10F
→
10/01 11:08, 6年前 , 11F
25 題目寫的是 instance, SAT 問題很難 因為現在找不到
10/01 11:08, 11F
→
10/01 11:08, 6年前 , 12F
一般性的方法可以有效率的解所有 instance
10/01 11:08, 12F
→
10/01 11:09, 6年前 , 13F
但是不代表所有 instances 都很難解 像是 SAT 的特殊形式
10/01 11:09, 13F
→
10/01 11:09, 6年前 , 14F
2-SAT 就很容易解
10/01 11:09, 14F
→
10/01 11:10, 6年前 , 15F
3-SAT 是 SAT 的特例 但是難度跟 SAT 是一樣的
10/01 11:10, 15F
‣ 更多 mistel 的文章
文章代碼(AID): #1TaYveya (Grad-ProbAsk)