作者frank4133 (HYF)
看板Grad-ProbAsk
標題Re: [理工] 106清大計科 7 8
時間Tue Jan 31 11:25:23 2023
※ 引述《bochengchen (LFII)》之銘言：
: 請問各位大大
: 1.
: 第七題的第四小題
: https://imgur.com/u9KXQTy.jpg
: 這個敘述應該是false，想請問各位大大該如何解釋？
看到原文底下有提到if p!=np, 沒有>=1的approximation algo
但是有點困惑洪捷不是還教2-approximation vertex problem & TSP嗎?
想請問是不是我有搞錯哪裡？
: 2.
: 第八題
: https://imgur.com/BVt9zsS.jpg
: 不知道這兩個小題該怎麼做比較好呢？
這題題目提到given.... 所以我以為是指已知圖G跟k值問是否滿足每點degree >= |S|-k
所以是為一decision problem非求optimal solution
但是爬文看大家的討論都是在證NP-hard
所以想請問是怎麼判斷題目是要求optimal solution呢？
還是說只能以通常這種題目都是要證NP-complete來做判斷？
謝謝！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.160.64.61 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1675135525.A.BD7.html
1F：推 jasonking3c: 第一題我也想問 近似演算法的p(n)不是必>1嗎？ 01/31 19:47
2F：推 zhlun0428: 2的是etsp不是tsp 有限制條件 02/02 09:58
3F：→ frank4133: 了解，感謝！ 02/09 19:33