#include <math.h>#include <stdio.h>#include <string.h>#include <stdlib.h>#define	Nmax 110 //最大的節點數#define Vmax 110  //最大的速度交換子個數#define Max_size 130  // swarm的最大個數#define MaxEdge 150000  //最大的可能的邊的大小struct seq		{int size;int s[Nmax+1];};struct val		{float v[MaxEdge];float min;};struct velocity	{int size;int comp[Vmax][2];};struct particle	{int rank;struct seq x;struct velocity v;float f;                      float fl;struct seq best_x;float best_f;};struct swarm		{int size; struct particle p[Max_size+1];int rank_best;};struct graph 		{int N;float v[Nmax][Nmax];float l_max;float l_min;int n_edge;};struct particle 	best_best; //swarm全局最優struct particle 	extra_best;   //真正的最優struct graph 		G;int			hood; //neighbour的大小struct particle 	init;  //初始的int			iter,iter_min,iter_max;int			same_best; //最優的值出現第幾次int			same_best_thresh;float			same_best_val;int			seed=1; //隨機值的種子struct swarm		sw1;struct val		val;FILE *f_trace;FILE *f_graph; //讀TSPLIB文件struct graph 			graph_min_max(struct graph G);struct val				graph_min_tour(struct graph G);struct graph			read_graph(FILE *file);struct particle 		init_particle(struct graph G);struct swarm			init_swarm(int size, struct graph G);int			        move_slow(struct swarm sw,int swarm_size,float slow,int hood);struct swarm 			reduce_swarm(struct swarm sw);struct swarm			new_swarm(struct swarm sw,int swarm_size);struct velocity			alea_velocity(int N);struct particle			auto_move(struct particle p);struct particle			best_neighbour(struct swarm sw1,struct particle p,int k);struct velocity			coeff_pos_minus_pos(struct particle p1,struct particle p2,float coeff);struct velocity			coeff_times_vel(struct velocity v,float coeff);int						compare_particle(struct particle p1,struct particle p2);float					f(struct particle p,int rank1, int rank2);void					search(struct graph G, struct particle p1, struct particle p2);struct particle			move_towards(struct particle p1,struct particle p3,int move_type);struct particle			pos_plus_vel(struct particle p,struct velocity v,int type);struct particle 		previous_best(struct particle p,int type);float					tax_no_arc(int times,struct graph G);struct velocity			vel_plus_vel(struct velocity v1,struct velocity v2);int				alea(int min,int max);int				alea_diff(int min, int max, int num);float 			MAX(float a,float b);float 			MIN(float a,float b);struct seq 		rotate(struct seq s,int k);struct seq		seq(int k,int N);float   parameter1,  parameter2;void display_position(struct particle p,int type);void display_solution(struct particle p);/* =============================================================================== */void main(){FILE *f_graph;struct particle	best_hood;int				choice;int				density;float			kappa;int				i;int				iter,iter_min,iter_max;char			graph[256];int				max_iter;float			min_tour;float			slow;int				parallel;float			phi;struct particle	solution;int				swarm_size;float			target;int				vmax;float			x;int				xi;slow=0.5;same_best_thresh=2;f_trace=fopen("trace.txt","w");G.l_max=10;G.l_min=1;printf("\n輸入TSPLIB文件名:\n");scanf("%s",&graph);f_graph=fopen(graph,"r");G=read_graph(f_graph);G=graph_min_max(G);val=graph_min_tour(G);min_tour=val.min;x=G.N; xi=x-1;swarm_size=xi;sw1.size=swarm_size;printf("\n Neighbour 大小 ? (最大 = %i) ",sw1.size);printf("\n : ");scanf("%i",&hood);hood=MAX(1,MIN(hood,sw1.size));iter_min=0;        sw1=init_swarm(swarm_size,G);        if(sw1.size<swarm_size)                {                printf("\n 生成swarm時出錯");                goto error_end;                }iterations:printf("\n 輸入 迭代次數  ? (輸入0結束)：  ");scanf("%i",&max_iter);if (max_iter==0) return;printf("\n 輸入 參數1 ? : ");scanf("%f",&parameter1);printf("\n 輸入 參數2 ? :  ");scanf("%f",&parameter2);target=min_tour;iter_max=iter_min+max_iter;for (iter=iter_min;iter<iter_max;iter++)        {        printf("\n\n 第 %i 次迭代 , swarm 大小 %i, 可能的最小值 %f",iter,sw1.size,extra_best.f);        if (best_best.f<=extra_best.f)        display_solution(best_best);        else        display_solution(extra_best);        if (extra_best.f<same_best_val)                {                same_best=0;                same_best_val=extra_best.f;                }        else                {                same_best=same_best+1;                }        printf("\n 可能最小值 %f, 已出現 %i 次",same_best_val,same_best);                 sw1=reduce_swarm(sw1);                if (move_slow(sw1,swarm_size,slow,hood)==1)                        {                        sw1=new_swarm(sw1,swarm_size);                        }        for (i=0;i<sw1.size;i++)                {                best_hood=best_neighbour(sw1,sw1.p[i],hood);                if (best_hood.f<best_best.f) best_best=best_hood;                        sw1.p[i]=move_towards(sw1.p[i],best_hood,5);                        if (sw1.p[i].f<best_best.f)                                {                                best_best=sw1.p[i];                                }                if (best_best.f<=G.l_min*G.N || extra_best.f<=G.l_min*G.N )                        {                        printf("\n\n Particle %i. 最小 ",i+1);                        goto end;                        }                if (best_best.f<=target || extra_best.f<=target)                        {                        printf("\n 目標值: %f",target);                        goto end;                        }                }        if (best_best.f<=G.l_min*G.N || extra_best.f<=G.l_min*G.N )                {                printf("\n\n 找到最小 ");                goto end;                }        }end:printf("\n 找到的最小值:");if (best_best.f<=extra_best.f)        {solution=best_best;}else        { solution=extra_best;}display_solution(solution);sw1.p[sw1.size]=extra_best;sw1.size=sw1.size+1;iter_min=iter_max;goto iterations;return;error_end:printf("\n 出錯");}struct graph graph_min_max(struct graph G){int 		i,j;struct graph Gt;Gt=G;Gt.n_edge=0;Gt.l_max=0;Gt.l_min=1000000;for (i=0;i<G.N;i++)        {        for (j=0;j<G.N;j++)                {                if (j!=i)                        {                        Gt.l_max=MAX(G.v[i][j],Gt.l_max);                        if (G.v[i][j]>=0)                                {                                Gt.l_min=MIN(G.v[i][j],Gt.l_min);                                Gt.n_edge=Gt.n_edge+1;                                }                        }                }        }return Gt;}struct val graph_min_tour(struct graph G){int 	i,j;int		lmax;int		n_diff_val;int		nval;int		rank;float	x;struct val val;lmax=G.l_max;if (G.l_max>MaxEdge)        {        printf("\n邊值太大 ");        }for (i=0;i<MaxEdge;i++)        val.v[i]=0;for (i=0;i<G.N;i++)        {        for (j=0;j<G.N;j++)                {                if (i==j) continue;                if(G.v[i][j]>=0)                        rank=G.v[i][j]-G.l_min;                else                        rank=G.l_max+1-G.l_min;                val.v[rank]=val.v[rank]+1;                }        }val.min=0;n_diff_val=0;nval=0;for (i=0;i<G.l_max-G.l_min+1;i++)        if (val.v[i]>0)                {                n_diff_val=n_diff_val+1;                }for (i=0;i<G.l_max;i++)        {                for (j=0;j<val.v[i];j++)                        {                        val.min=val.min+(G.l_min+i);                        nval=nval+1;                        if (nval>=G.N) goto end;                        }        }end:x=G.N*(G.N-1);for (i=0;i<G.l_max-G.l_min+2;i++)        {        if (val.v[i]>0)                val.v[i]=val.v[i]/x;        }return val;}struct graph read_graph(FILE *file){char			bidon[50];char			comment[100];char			edge_weight_format[30];char			edge_weight_type[30];struct graph	Gt;int 			i,j;char			name[20];char			type[20];int index=0,index1=0;float  x[Nmax], y[Nmax];fscanf(file," %s %s\n",bidon,name);fscanf(file," %s %s\n",bidon,type);  fscanf(file," %s %s\n",bidon,comment);  fscanf(file,"%s %i\n",bidon,&Gt.N); // dimension  fscanf(file,"%s %s\n",bidon,edge_weight_type);  fscanf(file,"%s\n",bidon);  printf("\n  %s,  %s, (%s)",name,type,comment);  printf("\n 城市的個數: %i\n",Gt.N);for (i=0;i<Gt.N;i++){ fscanf(file,"%i %f %f\n",&index,&x[i],&y[i]); printf("%f %f\n",x[i],y[i]);}          for (i=0;i<Gt.N;i++)                  {                  for (j=0;j<Gt.N;j++)                          {                         if (i==j)      Gt.v[i][j]=0;                           else{                          Gt.v[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));                           }                          }                  }          return Gt;}struct particle init_particle(struct graph G){int i;struct particle init;init.rank=-1;init.x.size=G.N;for (i=0;i<G.N;i++)        init.x.s[i]=i;init.x.s[G.N]=0;init.v.size=0;init.f=f(init,-1,-1);init.best_x=init.x;init.best_f=init.f;return init;}struct swarm	init_swarm(int size,struct graph G){int 				i;struct swarm 		swt;float				x,x1;swt.size=size;init=init_particle(G);swt.rank_best=0;for (i=0;i<size;i++)        {        swt.p[i]=init;        swt.p[i].rank=i;        swt.p[i].best_x=swt.p[i].x;        swt.p[i].best_f=swt.p[i].f;        swt.p[i].v=alea_velocity(i+1);        swt.p[i]=pos_plus_vel(swt.p[i],swt.p[i].v,0);        if (swt.p[i].f<swt.p[swt.rank_best].f)                swt.rank_best=i;        }best_best=swt.p[swt.rank_best];extra_best=best_best;same_best_val=extra_best.f;same_best=0;return swt;}int	move_slow(struct swarm sw,int swarm_size, float slow,int hood){int		i;float	slow_thresh2;float	sensibility=8;int		v_size_tot,v_tot,v_tot_min;if (same_best>=same_best_thresh)        {        printf("\n 更新群");        return 1;        }v_tot=0;v_size_tot=0;for (i=0;i<sw.size;i++)        if (sw.p[i].v.size>0) {v_tot=v_tot+1;v_size_tot=v_size_tot+sw.p[i].v.size;}if (v_tot==0)        {        printf("\n更新群");        return 1;        }       v_tot_min=swarm_size*slow+1;      slow_thresh2=swarm_size*slow;if (sw.size<=slow_thresh2 && slow>0)        {        printf("\n更新群");        return 1;        }if (v_tot<v_tot_min)        {        printf("\n 更新群");         return 1;        }return 0;}struct swarm reduce_swarm(struct swarm sw){struct swarm	diff;int				i,j;diff.size=1;diff.p[0]=sw.p[0];for (i=1;i<sw.size;i++)        {        for (j=0;j<diff.size;j++)                {                if (sw.p[i].f==diff.p[j].f)                        {                        if (compare_particle(sw.p[i],diff.p[j])==0)                                goto next_check;                        }                }        diff.p[diff.size]=sw.p[i];        diff.p[diff.size].rank=diff.size;        diff.size=diff.size+1;        next_check:;        }return diff;}struct swarm new_swarm(struct swarm sw,int swarm_size){struct particle	current_best;int				i;int				rank_best;int				type;struct swarm 	swt;for (i=0;i<swarm_size;i++)        {        if (i>=sw.size)                {                swt.p[i]=init;                swt.p[i].rank=i;                }        else                {                 swt.p[i]=previous_best(sw.p[i],0);                }        swt.p[i]=auto_move(swt.p[i]);        swt.p[i].v=alea_velocity(G.N-2);        if (swt.p[i].f<swt.p[i].best_f)                {                swt.p[i].best_f=swt.p[i].f;                swt.p[i].best_x=swt.p[i].x;                }        if (swt.p[i].x.s[0]!=0) swt.p[i].x=rotate(swt.p[i].x,0);        }best_best=swt.p[0];for (i=0;i<swarm_size;i++)        {        if (swt.p[i].f<best_best.f)                        best_best=swt.p[i];        }swt.size=swarm_size;rank_best=best_best.rank;if (rank_best<0) rank_best=0;if (extra_best.f<best_best.f)        {        extra_best.rank=rank_best;        if (extra_best.x.s[0]!=0) extra_best.x=rotate(extra_best.x,0);        swt.p[rank_best]=extra_best;        best_best=extra_best;        }swt.rank_best=rank_best;best_best.v.size=0;swt.p[swt.rank_best].v.size=0;return swt;}struct velocity	alea_velocity(int N){int				i;struct velocity vt;vt.size=N;for (i=0;i<vt.size;i++)        {        vt.comp[i][0]=alea(0,G.N-1);        vt.comp[i][1]=alea_diff(0,G.N-1,vt.comp[i][0]);        }return vt;}struct particle auto_move(struct particle p){int 			i,j,k;struct particle	pt,pt1;struct velocity v;float t;pt=p;        v.size=1;        next_step2:        for (j=0;j<G.N-1;j++)                {                v.comp[0][0]=j;                for (k=j+1;k<G.N;k++)                        {                        v.comp[0][1]=k;                        pt1=pos_plus_vel(pt,v,1);                  search(G,pt,pt1);                        }                }        return pt;}struct particle	best_neighbour(struct swarm sw1,struct particle p,int k)