Professor. 2016-04-08 04:52 采纳率: 37.5%
浏览 7147
已结题

旅行商问题算法流程图及时间复杂度

#include "iostream"
using namespace std;
int fact(int n)
{ //阶乘函数
int x = 1;
for(int i=n;i>0;i--)
x*=i;
return x;
}
void perm(int n,FILE *fp)
{
int i,b,k;
int *fa = new int[n+1]; //保存阶乘结果
int *r = new int[n],*r2 = new int[n];
int*num = new int[n];
//r 计算逆序数;r2计算对应位数;num保存排列结果
int tot = 0;
for ( i=0;i<n+1;i++)
fa[i] =fact(i);
fp=fopen("data.txt","wb");
for (int count=0;count<fa[n];count++)
{
//一共n!个排列,对每个数,计算其对应的序列

    tot = count; //r,r2 保存变进制数结果,即对应的逆序数组
    for (b=n-1;b>=1;b--) 
    {
        r2[n-1-b] = r[n-1-b] = tot/fa[b]; 
        tot = tot % fa[b];
    }
    r[n-1] = r2[n-1] = 0;
    //根据逆序数,计算每个数字所在位数
    for ( b=1;b<n-1;b++) 
    {
        for ( k=b-1;k>=0;k--) 
        {
            if(r[k]<=r[b])
                r2[b] ++;
        }
    }
    for ( i=0;i<n-1;i++) {
        r2[n-1] += (i+1 - r2[i]);
    }
    //根据位数计算出排列
    for ( i=0;i<n;i++) 
    {
        num[r2[i]] = i+1;
    }
    for(i=0;i<n;i++)
        fprintf(fp,"%d ",num[i]);
    fprintf(fp,"\n");
}
fclose(fp);

}
void travel(int **dis,int n,int m,FILE fp,int beginIndex)
{
int k=0,i;
int curdis;
int Mindis=10000;
int **help=new int
[fact(n)];
for(i=0;i<fact(n);i++)
help[i]=new int[n];
fp = fopen("data.txt","rb");
while(k<fact(n))
{
curdis=0;
for(i=0;i<n;i++)
{
fscanf(fp,"%d",&help[k][i]);

}
if(help[k][0]==beginIndex)
{
for(i=0;i<n-1;i++)
{
curdis += dis[help[k][i]-1][help[k][i+1]-1];
}
curdis += dis[help[k][i]-1][help[k][0]-1];
if(curdis<Mindis)
{
Mindis=curdis;
}
}
k++;
}
cout<<Mindis<<endl;
fclose(fp);

k=0;
fp = fopen("data.txt","rb");
while(k<fact(n))
{
    curdis = 0;
    for(i=0;i<n;i++)
    {
        fscanf(fp,"%d",&help[k][i]);    
    }
    if(help[k][0]==beginIndex)
    {
        for(i=0;i<n-1;i++)
            curdis += dis[help[k][i]-1][help[k][i+1]-1];
        curdis += dis[help[k][i]-1][help[k][0]-1];
        if(curdis==Mindis)
        {
            for(i=0;i<n;i++)
                printf("%d ",help[k][i]);
            printf("%d\n",beginIndex);
        }
    }
     k++;
}
fclose(fp);

}
int main()
{
int n,i,j,beginIndex;
cout<<"请输入城市个数:";
cin>>n;
cout<<"从第几个城市出发:";
cin>>beginIndex;
int **dis=new int*[n];
for(i=0;i dis[i]=new int[n];
cout for(i=0;i for(j=0;j cin>>dis[i][j];
FILE *fp;
perm(n,fp);
travel(dis,n,n,fp,beginIndex);
return 0;
}

这是用穷举法解决旅行商问题的算法,跪求大神来份流程图和时间复杂度怎么算?谢大神!

  • 写回答

1条回答

  • SpecterFire_Qi 2016-04-09 02:43
    关注

    时间复杂度是总运算次数表达式中受n的变化影响最大的那一项,列出你每次运算的运算次数就可以算出来了

    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题