主题：关于TSP得讨论
zhoucl01
[专家分：0] 发布于 2006-04-20 09:41:00
旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
有兴趣得人,请来一起讨论.
刚刚看到得一种用邻接矩阵得变换来得出问题得最后解,有人有用这种方法计算过得,一起讨论中...
回复列表 （共5个回复）
沙发
lt19870917 [专家分：750] 发布于 2006-04-20 11:31:00
该问题是不容易驾驭的问题,算法复杂度是指数级别的,谁能证明无多项式级别的解,或能给出多项式级别的解,图灵奖只是时间问题
板凳
rickone [专家分：15390] 发布于 2006-04-20 18:17:00
最小哈密顿环,NP问题，不是那么容易的。
3 楼
flysun0311 [专家分：2040] 发布于 2006-04-20 18:20:00
呵呵在离散上学到过,不过用程序编出来,我还没有这个水平.是不是这个问题也可以叫做周游问题呢
4 楼
rickone [专家分：15390] 发布于 2006-04-20 19:03:00
可计算的问题有两类，一类是有多项式时间复杂度算法的问题P类问题；另一类是计算复杂性为O(a^n)（大O中一横杠）,a>1。
NP问题现在最好的算法的复杂度是O(2^n)，但是这个问题是不是P类问题还不知道，就是只知道上界，不知道上确界，而且也没有证明不存在，这个问题是当代计算机科学理论的一大难题。
NP的意思就是Nondeterministic Polynomial，“非确定的多项式”。
5 楼
zhoucl01 [专家分：0] 发布于 2006-04-22 00:10:00
谢谢各位的回复,我现在着眼于这个问题的一些问题解法的算法改进,只能做一步是一步咯!
我来回复
您所在位置：