|
阅读：1701回复：10
计算机科学几个难题
1、（对称）货郎担问题（TSP） 计算机科学中的一个难题
//这个题目大家都熟悉，就不说了，很显然，穷举法，它的复杂度是关于n！的；即 //使用动态规划，也要n（n-1）*2^(n-2)，指数规模呢。是典型的NP问题。 : 2、SAT问题（可满足性问题） 这个问题定义如下： 首先，为了输入方便，数学符号用读音，不够规范，但大家理解为目的：）。 设L={ A,B,...,A非,B非,... },C1,C2,...,Ck是L的有限子集,称为子句。每个Ci中不 出 现L中互补的一对（即x属于Ci，则x非不属于Ci）,i=1,2,...,k,所谓可满足性问题，是确 定 是否存在一集合S包含于L，且满足以下两个要求： （1）S中不包含互补的一对元素，即x若属于S，则x非不属于S； （2）S交Ci ！=空集,i=1,2,...,k。 这个是NP完备问题，算的上最难的，又称NPC问题。大家注意，它有数理逻辑的背景， 你想想那个合取范式：）。 : 3、球面上N个点的分布问题（N为素数） : N=5，7，13，17 : 球面上N个点怎样分布，才能使的他们之间的距离之和最大？ : 这个问题我头次见到，呵呵，题目详实，就不说了。然而我粗略分析一下，也是极为 头疼：）。应该是个最优化问题，转化为角度的关系后，初看象线形规划问题，求一个和式 的极值，对于变量序列，有一系列的范围要求；然而，却不这么简单。N是素数，变量序列? 变量个数（角度个数）是以C(N,2)速度增长的，最重要的是，那一系列的范围要求，是非常 难找的，更不用说整个题目的解题了。或许有另外的角度，我在想，大家不妨谈谈思路啊。 顺便说一句，素数和我们是不是有仇：）？它哪儿都插一脚…… |
|
最新喜欢： skylgl
|
|
沙发#
发布于：2002-12-12 00:02
这是水区！
|
|
|
板凳#
发布于：2002-12-12 08:24
这是水区！灌 |
|
|
|
地板#
发布于：2002-12-12 08:33
这是水区为什么我们不灌,这是水区我们当然要灌,没理由这是水区我们不灌,不是水区我们偏偏要灌.你说是不是啊
|
|
|
地下室#
发布于：2002-12-12 09:43
np问题都是理论问题，大伙没几个能碰到----除了搞研究的
|
|
|
|
5楼#
发布于：2002-12-12 11:46
不好意思╋第一
|
|
|
|
6楼#
发布于：2002-12-12 12:10
好难的问题。
|
|
|
|
7楼#
发布于：2002-12-12 16:21
都会 :D :D :D :D
开玩笑的。别砸我。 |
|
|
8楼#
发布于：2002-12-12 21:14
都是计算理论的问题 确实是计算机届的经典中的经典
不过确实难中之难 或许有生之年都未必有突破咯 就象 计算机围棋的实现 |
|
|
9楼#
发布于：2002-12-13 00:06
都是计算理论的问题 确实是计算机届的经典中的经典 老兄说得对 |
|
|
|
10楼#
发布于：2002-12-13 11:32
为什么不灌，不灌白不灌
|
|
|