作者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