最短线路连接方法.docVIP

// 最短线路连接方法.cpp : Defines the entry point for the console application. //注：本程序不包含星形连接方式.事实上，应该普遍考虑神经网络的连接方式.并且由于递归调用的固有缺陷，使运算量非常大，输入的点数不可太多. #include stdio.h #includemath.h #includestdlib.h #define N 50 //限制点数不超过N. int main(int argc, char* argv[]) { void distance(double d[][N],double a[][2],int n);//作用是使d[i][j]代表第i、j两个点之间的距离，以便直接引用其元素，减少运算量. double sum(int b[],double d[][N],int n);//用来计算按照某一连接方式，线路的总长度. void fn(int b[],double d[][N],double*p,int c[],int j,int n);/*将各点的序号排序，并通过指针操控*p=s以及主函数中的int c[].其中 s用来存储前边排列的最短线路长度，c[]用来存储与之相应的点的序号*/ int n,i,b[N],c[N]; //b[N]用来存放点的序号，以后排序即对此序列进行操作. double a[N][2],d[N][N],s,*p=s; //a[N][2]用来存储各点的坐标，d[i][j]=d[j][i]表示i、j两点之间的距离. printf(请输入点数：\n); scanf(%d,n); printf(输入各点的坐标(平面坐标)：\n); for(i=0;in;i++) //循环的同时，初步给b[i]、c[i]赋值. { scanf(%lf%lf,a[i][0],a[i][1]); b[i]=c[i]=i; } distance(d,a,n); //利用a[N][2]提供的各点的坐标信息，给方阵d各元素赋值，使d[i][j]代表i、j两点间的距离. *p=sum(b,d,n); //给s=*p赋初值. fn(b,d,p,c,0,n); //排序，并最终给出最短路线长s,以及相应的连接方式. printf(最短线路长为%lf\n其顺次连接方式为：\n,*p); for(i=0;in;i++) printf((%lf,%lf),,a[c[i]][0],a[c[i]][1]); FILE*fp; fp=fopen(D:\\link.dat,w); fprintf(fp,%lf %lf\n,a[c[0]][0],a[c[0]][1]); for(i=1;in;i++) fprintf(fp,%lf %lf\n,a[c[i]][0],a[c[i]][1]); fclose(fp); printf(\nThis file has been saved.\n); return 0; } void distance(double d[][N],double a[][2],int n) //使d[i][j]=d[j][i]表示i、j两点间的距离. { int i,j; for(i=0;in;i++) for(j=0;j=i;j++) d[i][j]=d[j][i]=pow(pow(a[i][0]-a[j][0],2)+pow(a[i][1]-a[j][1],2),0.5); } double sum(int b[],double d[][N],int n) //计算按照某一连接方式，线路的长度. { int i; double s=0; for(i=0;in-1;i++) s+=d[b[i]][b[i+1]]; return s; } void fn(int b[],double d[][N],double*p,int c[],int j,int n)//调用函数并且利用指针，既不失独立性，又能对函数外的变量进行操控. { int k,t; if(j==n) { if(*psum(b,d,n)) { *p=sum(b,d,n); for(t=0;tn;t++) c[t]=b[t]; } } for(k=j;kn;k++) { t=b[j]; b[j]=b[k]; b[k]=t; fn(b,d,p,c,j+1,n); t=b[j]; b[j]=b[k]; b[k]=t; } }