ETS.zip_ETS_推销员问题_推销员问题 ets

/********************************************************************* 1.实验目的： 通过实验理解算法的概念、算法的表示、算法的时间复杂度和空间复杂度分析； 运用熟悉的编程工具对推销员问题进行求解，初步学会分析算法的时间复杂度和空间复杂度；　 2.实验内容： 有一推销员，欲到n(n<=10)个城市推销产品。 为了节省旅行费用，在出发前他查清了任意两个城市间的旅行费用， 想找到一条旅行路线，仅经过每个城市一次，且使旅行费用最少。 本问题已知城市n，和n*n的表达任意两个城市间费用的矩阵。 试求最短路径及其费用； 3.实验要求： 编制程序并对其时间复杂度和空间复杂度进行分析. *********************************************************************/ #include<iostream> #include<string.h> using namespace std; #define MAXNUM 10 int cost[MAXNUM][MAXNUM]; //花费 int seq[MAXNUM]; //路径 bool used[MAXNUM]; //是否重复 int n; int tcost; //总花费 int minicost; //最小花费 int cho[MAXNUM]; //当前最优路径 int input() { cout<<"输入城市数："<<endl; cin>>n; cout<<"输入n*n的费用："<<endl; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>cost[i][j]; } } return 0; } void f(int m) { for(int i=0;i<n;i++) { if(!used[i]) { used[i]=true; seq[n-m]=i; if(m>1) { f(m-1); } else//n==1 { tcost=0; for(int j=0;j<n-1;j++) { tcost+=cost[seq[j]][seq[j+1]]; } if(tcost<minicost || minicost==0) { minicost=tcost; for(int k=0;k<n;k++) { cho[k]=seq[k]; } } } used[i]=false; } } }; int ETS() { f(n); return 0; } int output() { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cout<<cost[i][j]<<endl; } } cout<<"最小花费:"<<minicost<<endl; cout<<"路径:"<<endl; for(int j=0;j<n;j++) cout<<"第"<<j+1<<"站是:"<<cho[j]+1<<endl; return 0; } int main() { memset(cost,0,sizeof(cost)); memset(cost,0,sizeof(seq)); memset(cost,0,sizeof(used)); memset(cho,0,sizeof(cho)); n=0; tcost=0; minicost=0; input(); ETS(); output(); return 0; }