[問題] 請問有關P,NP,NP-HARD

看板Prob_Solve作者 (if)時間16年前 (2007/11/28 22:22), 編輯推噓3(3推 0噓 6→)
留言9則, 3人參與, 最新討論串1/2 (看更多)
大家好~ 小弟對於NP-HARD有些問題不懂, 所以上來請教大家, 分別是: 1.拿到一個問題，是否為NP-hard?怎麼證他是不是NP-hard? 2.如果是NP-hard該怎麼解? 3.如果不是NP-hard那是什麼問題?該怎麼解?步驟有哪些? 會不會用到最佳化?啟發式? 4.解這類的題目對解題者的意義是什麼? 5.polynomial time reducible的目的是什麼? 謝謝大家~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.71.246
推
11/29 00:33, , 1F
你需要的是一本演算法課本
11/29 00:33, 1F
推
11/29 01:49, , 2F
演算法課本其實通常不會有太多章節講這部份又太厚
11/29 01:49, 2F
→
11/29 01:49, , 3F
計算理論方面的書籍應該比較合適
11/29 01:49, 3F
→
11/29 01:50, , 4F
關於1，最簡單也最常用的作法是利用5
11/29 01:50, 4F
→
11/29 01:51, , 5F
2. approximation.. random .. genetic ..pseudo polynomia
11/29 01:51, 5F
→
11/29 01:51, , 6F
可能的太多了，還可以硬幹，只能說一切視題目而定
11/29 01:51, 6F
→
11/29 01:52, , 7F
3. 可以分很多類，解法很多，步驟不一，有可能會。
11/29 01:52, 7F
推
11/29 19:58, , 8F
4. 這是哲學問題, 就跟雞為什麼要過馬路一樣
11/29 19:58, 8F
→
11/29 19:59, , 9F
5. 可把陌生的題目以可接受的代價轉換成別的比較熟悉的題目
11/29 19:59, 9F
‣ 更多 ifye 的文章
文章代碼(AID): #17JNcO5q (Prob_Solve)
‣ 更多 ifye 的文章
文章代碼(AID): #17JNcO5q (Prob_Solve)