作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 演算法 NP COMPLETE
時間Tue Oct 1 00:33:42 2019
第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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1569861224.A.F24.html
1F：→ DLHZ: 沒特別指名應該就是全部 10/01 08:09
2F：→ DLHZ: 如果這樣說的話2c看起來無誤？ 10/01 08:15
3F：→ DLHZ: sat是指某個公式是不是satisfiability 應該沒特別要求幾個 10/01 08:16
4F：→ DLHZ: 14我想看一下完整的題目 10/01 08:50
5F：→ DLHZ: 16.2他有提到 正權重longest path等價於負權重shortest path 10/01 09:19
6F：→ DLHZ: interval graph就是用一些實數長度的線組成的graph 10/01 09:21
7F：推 FRAXIS: 14 因為是 undirected graph 所以每條邊 weight 都是 1 10/01 11:04
8F：→ FRAXIS: 16 (2) 題目已經說了 是 shortest simple path 10/01 11:05
9F：→ FRAXIS: 所以有解 無解的是找 shortest path 因為你可以在 10/01 11:06
10F：→ FRAXIS: negative cycle 上一直繞圈 10/01 11:06
11F：→ FRAXIS: 25 題目寫的是 instance, SAT 問題很難 因為現在找不到 10/01 11:08
12F：→ FRAXIS: 一般性的方法可以有效率的解所有 instance 10/01 11:08
13F：→ FRAXIS: 但是不代表所有 instances 都很難解 像是 SAT 的特殊形式 10/01 11:09
14F：→ FRAXIS: 2-SAT 就很容易解 10/01 11:09
15F：→ FRAXIS: 3-SAT 是 SAT 的特例 但是難度跟 SAT 是一樣的 10/01 11:10