{struct particle bestt;float			coeff;float			dmin, dmax;float			dist[Nmax];int				i,j;int				rank_dmin[Nmax];float			kx;float			weight1;kx=k;        bestt=previous_best(p,0);        for (i=1;i<kx/2;i++)                {                j=p.rank+i;                if (j>sw1.size-1) {j=j-sw1.size;};                if(sw1.p[j].best_f<bestt.f)                        {                        bestt=previous_best(sw1.p[j],0);                        }                }        for (i=1;i<kx/2;i++)                {                j=p.rank-i;                if (j<0) {j=sw1.size+j;};                if(sw1.p[j].f<bestt.f)                        {                        bestt=previous_best(sw1.p[j],0);                        }                }return bestt;}struct velocity	coeff_pos_minus_pos(struct particle p1,struct particle p2,float coeff){int 			i,j,k,n1,nt;int				GN;struct particle pt;struct velocity vt;float			d0,d;if (p1.rank>=0 && (p1.rank==p2.rank)) {vt.size=0; return vt;};vt.size=0;pt=p2;GN=p2.x.size;if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0);if (p1.x.s[0]!=0)        {        printf("\n 出錯，路線不是從第 1 個城市開始",p1.rank);        return vt;        }for (i=1;i<GN-1;i++)        {        nt=pt.x.s[i];        n1=p1.x.s[i];        for (j=i;j<GN;j++)                        {                        if (p1.x.s[j]==nt)                                {                                if (j!=i)                                        {                                        pt.x.s[i]=n1;                                        vt.comp[vt.size][0]=n1;                                        for (k=i+1;k<GN;k++)                                                {                                                if (pt.x.s[k]==n1)                                                        {                                                        pt.x.s[k]=nt;                                                        vt.comp[vt.size][1]=nt;                                                        vt.size=vt.size+1;                                                        if (vt.size>Vmax)                                                                goto stop;                                                        goto next_node;                                                        }                                                }                                        return vt;                                        }                                }                        }        next_node:;        }vt=coeff_times_vel(vt,coeff);        return vt;stop:printf("\n 點數太多");return vt;}struct velocity	coeff_times_vel(struct velocity v,float coeff){float			coefft;int				i;struct velocity vt,vt0;if (v.size==0) return v;vt=v;if (coeff==0) {vt.size=0;return vt;};coefft=coeff;if (coeff<0)        {         for (i=0;i<v.size;i++)                {                vt.comp[i][0]=v.comp[v.size-i-1][0];                vt.comp[i][1]=v.comp[v.size-i-1][1];                coefft=-coeff;                }        } if (coefft==1)                return v;if (coefft<1)        {         vt.size=coefft*v.size;        return vt;        }vt0=vt;for (i=0;i<coefft;i++)        {        vt=vel_plus_vel(vt,vt0);        }vt.size=MIN(coefft*v.size,Vmax);return vt;}int	compare_particle(struct particle p1,struct particle p2){int	i;int GN;GN=p1.x.size;for (i=0;i<GN;i++)        {        if (p1.x.s[i]!=p2.x.s[i]) return 1;        }if (p1.v.size!=p2.v.size) return 1;for (i=0;i<p1.v.size;i++)        {        if (p1.v.comp[i][0] != p2.v.comp[i][0]) return 1;        if (p1.v.comp[i][1] != p2.v.comp[i][1]) return 1;        }return 0;}void	search(struct graph G, struct particle p1, struct particle p2){float			f_l;int				i,j;float			min1;struct particle pt;struct velocity vt;if (p2.f<p1.f) return ;vt.size=1;min1=p2.f;for (i=0;i<G.N-1;i++)        {        for (j=i+1;j<G.N;j++)                {                vt.comp[0][0]=i;                vt.comp[0][1]=j;                pt=pos_plus_vel(p2,vt,0);                if (pt.f<min1)                        min1=pt.f;                }        }return ;}struct particle	move_towards(struct particle p,struct particle pg,int move_type){struct particle pi;struct particle pit,pgt;struct particle	pt;float			d1,d2;float			alpha, beta, gamma, delta, eta;float			phi;int				tot_vel;struct velocity	v1,v2,v3;tot_vel=0;pi=previous_best(p,0);pt.rank=p.rank;explicit_velocities:v1=coeff_times_vel(p.v,parameter1);if (pi.f<pg.f) pit=pi; else pit=pg;v3=coeff_pos_minus_pos(pit,p,parameter2);v2=vel_plus_vel(v1,v3);        pt=pos_plus_vel(p,v2,1);        pt.v=v2;        tot_vel=tot_vel+v2.size;        goto end;end:if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0);if (pt.f<p.best_f)        {        pt.best_x=pt.x;        pt.best_f=pt.f;        }else        {        pt.best_x=p.best_x;        pt.best_f=p.best_f;        } pt.rank=p.rank;return pt;}struct particle	pos_plus_vel (struct particle p,struct velocity v, int type){float			ft[Vmax+1];int				i,i1;int				last_trans;int				n1,n2;struct particle	pt,ptemp;int				rank1,rank2;struct velocity	vtemp;if (v.size==0) return p;ptemp=p;if (type>=0)        {        ft[0]=p.f;        }for (i=0;i<v.size;i++)        {        n1=v.comp[i][0];        n2=v.comp[i][1];        for (i1=0;i1<G.N+1;i1++)                {                if (ptemp.x.s[i1]==n1)                        {                        rank1=i1;                        if (rank1==G.N) rank1=0;                        ptemp.x.s[i1]=n2;                        }                else                        {                        if (ptemp.x.s[i1]==n2)                                {                                rank2=i1;                                if (rank2==G.N) rank2=0;                                ptemp.x.s[i1]=n1;                                }                        }                }                if (type>0)                        {                        ptemp.f=f(ptemp,rank1,rank2);                        if (ptemp.f<ptemp.best_f)                                {                                ptemp.best_x=ptemp.x;                                ptemp.best_f=ptemp.f;                                }                        if(ptemp.f<extra_best.f)                                {                                extra_best=ptemp;                                }                        }        }        if (type==0)                {                ptemp.f=f(ptemp,-1,-1);               if ( ptemp.f<ptemp.best_f)                        {                        ptemp.best_x=ptemp.x;                        ptemp.best_f=ptemp.f;                        }                if(ptemp.f<extra_best.f)                        {                        extra_best=ptemp;                        }                }        pt=ptemp;        goto end;end:if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0);if (extra_best.x.s[0]!=0) extra_best.x=rotate(extra_best.x,0);return pt;}struct particle previous_best(struct particle p, int type){struct particle pt;if (type==0)pt=p;pt.x=p.best_x;pt.f=p.best_f;if (pt.x.s[0]!=0) pt.x=rotate(pt.x,0);return pt;pt=p;pt.best_x=p.x;pt.best_f=p.f;return pt;}float tax_no_arc(int l,struct graph G)        {        float 	tax=1.1; /* >=1 */        float 	x;       x=tax*G.l_max+(G.N-1)*(G.l_max-G.l_min);        return x;        }struct velocity	vel_plus_vel(struct velocity v1,struct velocity v2){int				i;struct velocity vt;vt=v1;vt.size=MIN(v1.size+v2.size,Vmax);for (i=v1.size;i<vt.size;i++)        {        vt.comp[i][0]=v2.comp[i-v1.size][0];        vt.comp[i][1]=v2.comp[i-v1.size][1];        }return vt;}int alea(int min,int max){int ir;float r;srand(seed);r=rand();seed=r;r=r/RAND_MAX; /* Normally, RAND_MAX = 32767 = 2^31-1 */r=0.5+min+r*(max-min);ir=r;return ir;}int alea_diff(int min,int max, int num){int	temp1,temp2;if (num==min)        {        temp1=alea(min+1,max);        return temp1;        }if (num==max)        {        temp1=alea(min,max-1);        return temp1;        }temp1=alea(min,num-1);temp2=alea(num+1,max);if (alea(0,100)<50)        {        return temp1;        }else        {        return temp2;        }}float MAX(float a,float b){if (a>b) return a; return b;}float MIN(float a,float b){if (a<b) return a; return b;}struct seq rotate(struct seq s,int k){int i,j;struct seq st;if (s.s[0]==k) return s;for (i=0;i<s.size;i++)        {        if (s.s[i]!=k) continue;                for (j=i;j<s.size;j++)                        st.s[j-i]=s.s[j];                for (j=0;j<i;j++)                        st.s[j+s.size-i]=s.s[j];        }st.s[s.size]=st.s[0];st.size=s.size;return st;}void display_solution(struct particle p){if (p.rank<0)        {        printf("\n Extra particle");        }display_position(p,1);}float f(struct particle p,int rank1,int rank2){float				d;float				delta_f;float 				ft;int 				i;int					n,n0,n1,n2,ni;int					no_arc;float				val1,val2;no_arc=0;if (rank1>=0) goto modif;ft=0;for (i=0;i<G.N;i++)        {        n=p.x.s[i];        n0=p.x.s[i+1];if (n0>G.N || n>G.N)        {        printf("\nERROR arc %i=>%i",n+1,n0+1);        printf(" value %f",G.v[n][n0]);        }        if (G.v[n][n0]<0)                {                delta_f=tax_no_arc(no_arc,G);                no_arc=no_arc+1;                }        else                {                delta_f=G.v[n][n0];                }        ft=ft+delta_f;        }goto end;modif:n1=p.x.s[rank1];n2=p.x.s[rank2];ft=p.f;if (rank1==0) i=G.N-1; else i=rank1-1;ni=p.x.s[i];if (G.v[ni][n1]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[ni][n1];if (G.v[ni][n2]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[ni][n2];ft=ft-val2+val1;if (rank1==G.N-1) i=0; else i=rank1+1;ni=p.x.s[i];if (G.v[n1][ni]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[n1][ni];if (G.v[n2][ni]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[n2][ni];ft=ft-val2+val1;if (rank2==0) i=G.N-1; else i=rank2-1;ni=p.x.s[i];        if (G.v[ni][n1]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[ni][n1];        if (G.v[ni][n2]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[ni][n2];        ft=ft-val1+val2;if (rank2==G.N-1) i=0; else i=rank2+1;ni=p.x.s[i];        if (G.v[n1][ni]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[n1][ni];        if (G.v[n2][ni]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[n2][ni];        ft=ft-val1+val2;if (abs(rank1-rank2)==1 || abs(rank1-rank2)==G.N-1) // Particular cases n1=>n2 or n2=>n1        {        if (G.v[n1][n2]<0) val1=tax_no_arc(no_arc,G); else val1=G.v[n1][n2];        if (G.v[n2][n1]<0) val2=tax_no_arc(no_arc,G); else val2=G.v[n2][n1];        ft=ft-val1-val2;        }end:if (ft<extra_best.f)        {        extra_best=p;        extra_best.f=ft;        if (extra_best.x.s[0]!=0) extra_best.x=rotate(extra_best.x,0);        }return ft;}void display_position(struct particle p,int type){int 	i;float 	x;printf("\n particle %i: ",p.rank+1);for (i=0;i<p.x.size+1;i++)        printf(" %i",p.x.s[i]+1);}