| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1249 人关注过本帖
标题:[求助]旅行商问题:为什么矩阵大了运行结果就显示不出来,源代码如下
只看楼主 加入收藏
brookelily
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2006-11-3
收藏
 问题点数:0 回复次数:4 
[求助]旅行商问题:为什么矩阵大了运行结果就显示不出来,源代码如下

#include "stdio.h"
#define n 6
#include<iostream.h>

#define MAX 100000000
typedef int DataType;
DataType bestc;
DataType bestx[n+1];
//DataType a[n][n]={{0,30,6,4},{30,0,5,10},{6,5,0,20},{4,10,20,0}};
DataType a[n+1][n+1]={0, 0,0,0,0,0,0 ,
0,0 , 702 , 454 ,842 , 2396 , 1196,
0,702, 0 , 324 , 1093, 2136 , 764,
0,454 ,324 ,0 ,1137 ,2180 , 798,
0,842, 1093 , 1137 , 0 , 1616 , 1857,
0,2396 ,2136 , 2180 ,1616 ,0 ,2900,
0,1196 , 764 , 798 , 1857 , 2900 , 0 };
DataType x[n+1];
DataType cc;
void Swap(int x[],int i,int j)
{
int temp=x[i];
x[i]=x[j];
x[j]=temp;
}
void tSP(int i)
{// 旅行商问题的回溯算法
int j;
if (i == n)
{// 位于一个叶子的父节点
// 通过增加两条边来完成旅行
if (a[x[n-1]][x[n]]!=0&&a[x[n]][1]!=0&&
(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc ==0))
{// 找到更优的旅行路径
x[i+1];
for(j = 1; j <= n; j++)
bestx[j] = x[j];
bestc=cc+a[x[n-1]][x[n]] + a[x[n]][1];
}
}
else {// 尝试子树
for (j = i; j <= n; j++)
//能移动到子树x [ j ]吗?
if (a[x[i-1]][x[j]] !=0 &&
(cc+a[x[i-1]][x[i]]<bestc||bestc == 0))
{//能搜索该子树
Swap(x,i,j);
cc += a[x[i-1]][x[i]];
tSP(i+1);
cc -= a[x[i-1]][x[i]];
Swap(x,i,j);
}
}
}
DataType TSP()
{// 用回溯算法解决旅行商问题
int i;
// x 是排列
for (i = 0; i <= n; i++)
{
x[i]=i;
// bestc=0;
bestx[i]=x[i];
}
bestc=MAX;

cc = 0;
// 搜索x [ 2 : n ]的各种排列
tSP(2);
return bestc;
}
void main()
{
int i;
//a[4][4]={{0,30,6,4},{30,0,5,10},{6,5,0,20},{4,10,20,0}};
TSP();
for(i=1;i<=n;i++)
printf("%d",bestx[i]);
printf("\n The lowest cost is %d\n",bestc);
}


[此贴子已经被作者于2007-8-7 20:15:00编辑过]

搜索更多相关主题的帖子: 源代码 商问题 旅行 矩阵 DataType 
2007-08-07 20:13
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 
因为时间复杂度是O(n!)的

[此贴子已经被作者于2007-8-7 21:11:39编辑过]



汗,都懒得写代码了.......... cheat了一个威望,哈.....
2007-08-07 20:52
brookelily
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2006-11-3
收藏
得分:0 
以下是引用cwande在2007-8-7 20:52:30的发言:
因为时间复杂度是O(2^n)的

那怎么样改进阿,有办法吗?

2007-08-07 21:01
cwande
Rank: 2
等 级:新手上路
威 望:3
帖 子:333
专家分:0
注 册:2006-8-18
收藏
得分:0 

说错了,是n!的
这本来就是经典的npc问题,可以用遗传算法进行改进,但没有多项式时间算法
如果n不大的话,可以用压缩状态的动态规划做,时间复杂度为O(n*2^n),
但同时空间也需要O(n*2^n)-_-


汗,都懒得写代码了.......... cheat了一个威望,哈.....
2007-08-07 21:10
wingyip
Rank: 1
等 级:新手上路
威 望:2
帖 子:119
专家分:0
注 册:2007-7-16
收藏
得分:0 
上面的恐怖啊。

2007-08-08 08:59
快速回复:[求助]旅行商问题:为什么矩阵大了运行结果就显示不出来,源代码如下
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017591 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved