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也上这方面的课吧 : : 青春的专业,也是最吃青春饭的专业。
|