2 qq 22584569 qq_22584569 于 2016.04.08 12:52 提问

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

#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;
}

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

2个回答

CSDNXIAON
CSDNXIAON   2016.04.08 13:01

算法之时间复杂度和空间复杂度
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

UnityFire
UnityFire   2016.04.09 10:43

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

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
TSP旅行商时间复杂度与空间复杂度
其实我不是很喜欢这些个复杂度们的,不知道怎么的就是弱项呢,所以只能耐下心来慢慢分析了,以下将记录我这段时间所学。 TSP(旅行商问题):动态规划算法: 空间复杂度:2^n,分析:动态规划需要枚举所有子图,那么对于n个点的图来说共有多少子图呢?因为每个点都有选与不选的权力,so,需要2^n空间 来存储。 时间复杂度:2^n*n^2 ,分析:
TSP_旅行商问题 - 遗传算法(四)
本文修改日志:2017.01.22:整理并发布第一版博文;2018.05.01:修改源代码170行(添加float),double RateVariation = float(rand()%100)/100; 一、前言    【旅行商问题】旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该...
TSP_旅行商问题 - 蛮力法DFS(一)
本文基于蛮力法(此处采用深度优先遍历,DFS)解决旅行商问题。通过遍历出所有满足条件的路径情况,并保持更新最优解,直到所有情况都遍历完,得到全局最优解。但是,使用蛮力法需要遍历的城市个数高达city_num的阶乘,当city_num=12的时候,需遍历479001600种情况,程序所需时间以小时为单位。
TSP:旅行商问题与内存优化的动态规划
旅行商问题(TSP)的内存优化
TSP问题之回溯算法
TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市,要求路径的总和最小。考虑用回溯算法求解。w(vi,vj)表示城市i与j间的直接距离,w(vi,vj)=∞表示城市i与j间无直接路径。将图中n个顶点编号为1,2,…,n,以顶点1为起点,旅
贪心算法:旅行商问题(TSP)
TSP问题(Traveling Salesman Problem,旅行商问题),由威廉哈密顿爵士和英国数学家克克曼T.P.Kirkman于19世纪初提出。问题描述如下: 有若干个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市出发必须经过每一个城市且只在一个城市逗留一次,最后回到出发的城市,问如何事先确定一条最短的线路已保证其旅行的费用最少? 另一个类似的问题为:一个邮递员从邮局
TSP_旅行商问题 - 贪心算法
TSP_旅行商问题 - 贪心算法 TSP_旅行商问题-贪心算法 TSP_旅行商问题-模拟退火算法 TSP_旅行商问题-遗传算法 TSP_旅行商问题-基本蚁群算法 问题描述 寻找最短路径使得其经过所有城市 测试数据集:tsp.eil51问题 1 37 52 2 49 49 3 52 64 4 20 26 5 40 30 6 21 47 7 17 63 8 31 62 9 52 ...
【算法设计与分析基础】蛮力法解决旅行商问题
蛮力法解题思想:旅行商问题(又叫货郎担问题)可以表述为求一个最短的哈密顿回路问题。因为是回路,所以可以假设所有的回路都起点和终点都为同一个点,从而生成n-1个中间城市的排列。通过递归函数遍历所有城市,并记录每一种排列所得路径的长度,比较后得到最短路径。       对于上图所示的图,很显然最短的回路为:a→b→d→c→a;    首先我们选择a为出发点,遍历以a为起点/终点的所有可能的路径,
基于分支限界法的旅行商问题(TSP)二
和上篇一样,考前写写伪代码,考完了补上具体的解释和代码。     状态{矩阵,结果集,下界} 全局结果集列表,全局上界初始为Infinite 建立一个heap,存储状态,出堆规则为拥有最小的下界。 利用reduced cost matrix 来把矩阵进行化简,把化简消耗作为下界,将初始状态加入heap 当heap不为空时 {   从heap中弹出一个状态,赋值给两个临时状态。
动态规划经典问题--TSP问题
Travelling Salesman Problem 旅行商问题,即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 旅行商问题