h**x
发帖数: 34 | 1 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
决某 NP-complete 问题的吗？
如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
谢谢！
http://en.wikipedia.org/wiki/NP-complete
非常粗略的说，就是算法上只能做到指数级运算时间，而不是多项式运算时间
Boolean satisfiability problem (Sat.)
N-puzzle
Knapsack problem
Hamiltonian path problem
Travelling salesman problem
Subgraph isomorphism problem
Subset sum problem
Clique problem
Vertex cover problem
Independent set problem
Dominating set problem
Graph coloring problem |
Z****g
发帖数: 13731 | 2 poor-defined question.
【在 h**x 的大作中提到】
: 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
: 决某 NP-complete 问题的吗？
: 如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
: 谢谢！
:
: http://en.wikipedia.org/wiki/NP-complete
: 非常粗略的说，就是算法上只能做到指数级运算时间，而不是多项式运算时间
: Boolean satisfiability problem (Sat.)
: N-puzzle
: Knapsack problem
|
h**x
发帖数: 34 | 3
哪不清楚？愿闻其详。
【在 Z****g 的大作中提到】
: poor-defined question.
|
G*O
发帖数: 687 | 4 没看懂
【在 h**x 的大作中提到】
: 麻烦想了解一下诸位在实际工作（比如，金融，生物，工程计算，等领域）中有需要解
: 决某 NP-complete 问题的吗？
: 如果有，能否说明一下具体是哪个 NPC problem，以及 problem size 有多大。
: 谢谢！
:
: http://en.wikipedia.org/wiki/NP-complete
: 非常粗略的说，就是算法上只能做到指数级运算时间，而不是多项式运算时间
: Boolean satisfiability problem (Sat.)
: N-puzzle
: Knapsack problem
|
Z****g
发帖数: 13731 | 5 computer science althorithm problem.
【在 G*O 的大作中提到】
: 没看懂
|
J****7
发帖数: 375 | 6 只有修过CS课的（而且是研究生的算法课）才会对NP-complete有很深的印象，昨天看
到Ziheng 的回贴就猜到Ziheng有CS的背景，而且是在美国上的CS。
好奇的是，Ziheng现在还作土木吗？土木在所有的工学院里的专业里面已经算是最不青春的专业，也是最吃青春饭的专业。 |
k****n
发帖数: 3803 | 7 本科算法课也会讲NP-complete的，另外OR也上这方面的课吧
青春的专业，也是最吃青春饭的专业。
【在 J****7 的大作中提到】
: 只有修过CS课的（而且是研究生的算法课）才会对NP-complete有很深的印象，昨天看
: 到Ziheng 的回贴就猜到Ziheng有CS的背景，而且是在美国上的CS。
: 好奇的是，Ziheng现在还作土木吗？土木在所有的工学院里的专业里面已经算是最不青春的专业，也是最吃青春饭的专业。
|
J****7
发帖数: 375 | 8 本科的课还是很初级的介绍，高等算法重点讲这个，期末考试的难题也是这个，所以才
能加深理解，有很深的印象。
NPC问题大家去google，这里扯，太费时间了。
【在 k****n 的大作中提到】
: 本科算法课也会讲NP-complete的，另外OR也上这方面的课吧
:
: 青春的专业，也是最吃青春饭的专业。
|
