作者ifye (if)
看板Prob_Solve
標題[問題] 請問有關P,NP,NP-HARD
時間Wed Nov 28 22:22:15 2007
大家好~
小弟對於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
1F：推 PRAM:你需要的是一本演算法課本 11/29 00:33
2F：推 dh3014:演算法課本其實通常不會有太多章節講這部份又太厚 11/29 01:49
3F：→ dh3014:計算理論方面的書籍應該比較合適 11/29 01:49
4F：→ dh3014:關於1，最簡單也最常用的作法是利用5 11/29 01:50
5F：→ dh3014:2. approximation.. random .. genetic ..pseudo polynomia 11/29 01:51
6F：→ dh3014:可能的太多了，還可以硬幹，只能說一切視題目而定 11/29 01:51
7F：→ dh3014:3. 可以分很多類，解法很多，步驟不一，有可能會。 11/29 01:52
8F：推 ledia:4. 這是哲學問題, 就跟雞為什麼要過馬路一樣 11/29 19:58
9F：→ ledia:5. 可把陌生的題目以可接受的代價轉換成別的比較熟悉的題目 11/29 19:59