RETURN MAIN PAGE	2008 5.22 Xeon 3.16GHz 16GBで再度計算してみる、 ＴＳＰＬＩＢに登録されている最小値は d15112 : 1573084 以前のデータ 6-10　　 1697820.600363 4-12　　 1694061.186921 今回のデータ 5-12　1691632.257594 経路データ	クリックすると拡大しますtsp-d15112-2.JPG
		クリックすると拡大します。 I solved d15112. click left picture! you can see ditails..

	ＴＳＰ　traveling salesman problem セールスマン巡回問題　ｄ１５１１２を例にして ＴＳＰ　traveling salesman problem, for exsample d15112 german city data from TSPLIB. This program can solve completely hundred numbers city TSP problem in TSPLIB. I am Japanese and I am not good at English writting. If you want to know details of this program,give me e-mail. Comparing another TSPLIB data 2006 2.11 相当以前に書きなぐったようなようなものなので、何で文字列でデータを取り込んで変換しているのか わかりません。 このソースのグラフィックは共立出版の、「Ｗｉｎｄｏｗｓプログラムを１０倍簡単に作成する」を使っています。 ここに掲載している経路データは最初の配置のデータの後ろに経路の番号が入っています。 ２００６　１．２３ 意外と見ている人がいるようなので、ソースと経路のデータを付けておきます。 以前に１万都市を計算したときには経路の交差は有りませんでした。 表示はＮ８８−ＢＡＳＩＣで分割していました。 ２００５　８．６ 　このアルゴリズムは京都の物性物理（１９９５．１２月上旬）のシンポジュームに出して、 題名は「単純なアルゴリズムで数の多い都市のＴＳＰを解く」です。 去年、この報告書を入手しました。数百都市のものは最適値を得ていたのですが、提出は人に依頼していたので、最適値よりも小さい値が出たと書かれていました。 数百都市のものでは対称なものなどを除いてだいたい最適値は計算できています。
	ずっと以前に製作したものですが、最近では１万都市を超えるものがあるので再び去年計算してみました。 ＴＳＰＬＩＢに登録されている最小値は d15112 : 1573084 私のプログラムで計算した最小値は よく見ると４−１２の方が値が小さい。 6-10　　 1697820.600363 4-12　　 1694061.186921 6-10/true value=1.0793 　　　誤差７．９３％です。 4-12/true value=1.0769 　　　誤差７．６９％ 経路データ 6-10 path data is here. The structure of data is number of city, value,x location,y location ,,,,,,path city numberlist. 経路データの構造は、都市数、値、都市のＸ座標、Ｙ座標、、、、、経路の都市の番号です。 シフト数、セット数はおおよそ６辺りで良い数字になっています。 ソースなど興味のある方ご連絡ください。 ＴＳＰＬＩＢの数百都市のものでは対称なものなどを除いて最適値は計算できています。
	ＴＳＰを解くプログラム 　「ＴＳＰＵＤ３．Ｃ」 　　　　　　　　　　　　　　　　　１９９８　７／１４ 　　　　　　　　　　　　　　　　　　　　　石崎　豪洋 （４０＊４０）で見るように出来ています。 　ＴＳＰとは点を結ぶ距離を最小にする問題であり、日本語では巡回セールスマン問題と言われるものです。 　１９９５年の６月頃からに遺伝アルゴリズムを用いてＴＳＰ問題を解くプログラムを制作していました。 最初はＧｏｌｄｂｅｒｇの方法で解いて見ました。このアルゴリズムでは、１３〜１５都市以上で解こうとすると経路の交差が排除出来ない事が多いので、「遺伝的アルゴリズム」（産業図書）に載っている形質遺伝の方法を読んで作って見ました。 しかし、私の作り方では経路の交差が形質として遺伝してしまうのでした。 この形質遺伝のアルゴリズムも色々制作して見ました。 優良個体のｇｅｎｅから出現頻度の高いパターンを取り出して、そのパターンは破壊せずに交差等の交配を行なう事を条件を変えて行なって見ました。 形質遺伝として破壊せずに取って置くｇｅｎｅの長さ、形質遺伝の個数、など どのプログラムでも交配する個体の選び方としては、 域値を設けて全部の個体の中から上位のものを選ぶ。 この場合、全部の個体数の上位から一割、二割と変えて行く。 そして、淘汰域値以上の個体に対しては以下の様な交配を行なった。 １．最優良個体と残りの個体を交配 ２．ランダムに交配 結局、遺伝アルゴリズムでは１３〜１５都市以上の場合に経路の交差が排除出来ないので、以下の様なアルゴリズムで解いて見ました。 最初にランダムに巡回経路を設定する。 ２つの点を決める。これを２重ループで組合せを作る。 交換規則に １．単純に２都市を交換 　　　　　ａｂｃｄｅｆｇ　→　ａｆｃｄｅｂｇ 　　　　　　↑　　　↑　　　　　↑　　　↑ ２．取り出して挿入 　　　　　ａｂｃｄｅｆｇ　→　ａｃｄｅｂｆｇ 　　　　　　↑　　／＼　　　　　　　　↑ ３．一つのｓｕｂツアーの順を逆にする。 　　　　　ａ（ｂｃｄｅｆ）ｇ　→　ａ（ｆｅｄｃｂ）ｇ 以上の３つの規則で交換する。 交換して値が小さいものを最小値とする。 ループが終了したら経路リストを都市数の１／４だけシフトする。 これを３回行なう。 ここまでのアルゴリズムのプログラムが「ＴＳＰＵＤ３．Ｃ」です。 このプログラムはＴｕｒｂｏ　Ｃで書いてあり、動作している所が見ることが出来ます。 計算量は都市数の３乗になっています。 これを２乗に改良したものが以下のアルゴリズムです。 距離の計算は ｏｏａｏｏｏｂｏｏｏ dd1　　 dd2　　 dd3 として全体の和を直接全部計算せずに省略することで 全体の和はｄｄ１＋ｄｄ２＋ｄｄ３となり全体の計算量を決定するループは ａ＝１からａ＝都市数 ｂ＝ａ＋１からｂ＝都市数−１ 迄の２重ループであるので 計算量は都市数の２乗に比例する。 このプログラムは「Ｆ７．Ｃ」と言うものですが、ＦＭ−ＴｏｗｎｓのＨｉｇｈ−Ｃで書いてあり、表示はＮ８８と言う構成になっているので公表した所で実行する人は少ないと思われるので比較的に見た目の良い「ＴＳＰＵＤ３．Ｃ」にしておきます。 ＴＳＰＬＩＢのもので試した所、繰返し図形や格子点では最適解を得ることは困難です。 しかし、常に僅かながら最適解を得る確率は存在します。 ＧＲ６６６では登録されているものよりも良い値が出たのですが、 あとがきとして 　私の書くプログラムはＢＡＳＩＣで最初にコーディングしてからＣに書き直しています。構造化どころかＧＯＴＯやラベルに数字が残っているのが分ると思います。 個人で使う分にはＣ＋＋の様な言語は必要ないと思うのですが。 　また、綺麗に、見やすい、と言う概念は有りません。昔、メモリが足りなくてギチギチに詰ったソースを読み書きしていたので、何とも思わない悪い癖です。 Ｃ言語はわけのわからないｂｕｇが入ってしまい、ｄｅｂｕｇ不能になることが良く有るので新しいアルゴリズムをコーディングする際にはＢＡＳＩＣで書いてから動作確認してから書いています。 この様な訳で、このソースにはテクニックの様なものは有りません。 　このアルゴリズムは京都の物性物理（１９９５．１２月上旬）のシンポジュームに出して、報告書も作ったはずです。 題名は「単純なアルゴリズムで数の多い都市のＴＳＰを解く」です。 去年、この報告書を入手しました。数百都市のものは最適値を得ていたのですが、提出は人に依頼していたので、最適値よりも小さい値が出たと書かれていました。 数百都市のものでは対称なものなどを除いて最適値は計算できています。 参考文献 小林重信　遺伝的アルゴリズムの現状と課題　　計測と制御　　Ｖｏｌ３２，Ｎｏ１　　１９９３ 宇佐美義之、加納義樹、人工知能学会論文集８、（１９９４）３７７、Ｃｏｍｐｕｔｅｒ　Ｔｏｄａｙ６３（１９９４）４０． 新妻清三郎、村田安永、山田和年　機能的アルゴリズムに基づく巡回セールスマン問題の解法　人工知能学会誌　Ｖｏｌ１，Ｎｏ．１，ｐｐ１３０−１３６（１９９６）． Ｌ．デービス／編　遺伝アルゴリズムハンドブック　森北出版（１９９４）
	d１５１１２の計算結果　シフト数とセット数　最小値の順に書いてあります。
	2-2 1996394.230064 2-3 1810478.087667 2-4 1752354.081796 2-5 1701301.521610 2-6 1713263.955428 2-7 1713037.493664 2-8 1706248.332025 2-9 1704303.078981 2-10 1701356.904878 2-11 1691937.049389 2-12 1700410.917595 3-2 1997342.915433 3-3 1810831.180465 3-4 1750236.064202 3-5 1732097.269287 3-6 1720078.518472 3-7 1706764.458024 3-8 1701872.118909 3-9 1698200.330579 3-10 1702695.414250 3-11 1699245.928558 3-12 1702366.462164 4-2 2003363.110003 4-3 1812555.505602 4-4 1761783.302627 4-5 1722331.893255 4-6 1703626.554906 4-7 1707234.064172 4-8 1706630.718087 4-9 1702885.352403 4-10 * 4-11 1702388.667276 4-12 1694061.186921 5-2 2011742.690257 5-3 1813189.279503 5-4 1741338.758827 5-5 1729723.690579 5-6 1723107.378779 5-7 1711840.810422 5-8 1711841.865002 5-9 1705376.975846 5-10 1701749.923526 5-11 1701740.047231 5-12 1699955.369996 6-2 2010835.192682 6-3 1817043.077150 6-4 1713673.068078 6-5 1746601.658999 6-6 1723647.780357 6-7 1712659.293087 6-8 1699656.158867 6-9 1699461.945916 6-10 1697820.600363 6-11 1695410.087070 6-12 1698273.245200 7-2 1994416.394257 7-3 1808669.240680 7-4 1744097.898306 7-5 1734168.543146 7-6 1708680.437005 7-7 1710123.443701 7-8 1706487.763945 7-9 1699623.213589 7-10 1702900.666501 7-11 1700076.735797 7-12 1704120.440542 8-2 2009446.877573 8-3 1806565.812996 8-4 1751415.225799 8-5 1723041.531001 8-6 1718152.122962 8-7 1711014.881042 8-8 1708529.937962 8-9 1696947.797402 8-10 1701143.051816 8-11 1696289.684304 8-12 1702036.763572 9-2 1991048.739391 9-3 1806195.793848 9-4 1751526.299850 9-5 1727998.852296 9-6 1706869.306351 9-7 1709704.968232 9-8 1702630.800154 9-9 1702431.982383 9-10 1704135.446268 9-11 1701967.310512 9-12 1697352.001422
	/* 1995 1/25 優良解探索 100回探索して優良解を得る｡ 完全２乗アルゴリズム　１９９５　１１／２８ TSP Program 1995 9/2 F7.C 画面をコピーする為に結果をファイル出力 Ｎ８８Ｂａｓｉｃで画面ハードコピー 1000都市計算用 最後の交差排除 gene shift 1995 8/30 ユークリッド距離 都市データを１０倍にする load save debug 一万都市計算用 */ #include<stdio.h> #include<stdlib.h> #include<time.h> #include<math.h> #include<io.h> #include "screen_int.f" /* 画面初期化関数 */ #include "pset2.f" /* 点関数 */ #include "gcls.f" #include "line.f" #include "rectangle.f" void geneinit(void); void dsave(void); void dload(void); void est(void); void geneshift(int); void hyougi(void); long df,eb,aa,si,pf,sc,w,sp,ep,f,pj,kj,i,j,k,jj,a,b,ss,n,ti,c; long kai,kaj,scj; float px[20001], py[20001]; int g[20001], gh[20001], gt[20001],t[20001],g2[20001]; double dd,dd1,dd2,dd3; double lolo,d1,d2,d3,lo,da; double d11,d22,d33; float rr; int xx,yy,ssi; double ff,s; char st[20]; char file[64]; char file2[64]; char file22[10]; char buff[256]; char buff2[256]; FILE *fp2; FILE *fp; //file22[0]=92;file22[1]=0; main() { file22[0]=92;file22[1]=0; for(i=1;i<20;++i){st[i]=65+i;} pj = 20; f=0; sc=0; pf=0; scj=6; rr=10; xx=200;yy=200; /* Menu */ menu1: st[0]=12;st[1]=0; printf("%s",st); printf("\nＴＳＰ　Ｐｒｏｇｒａｍ Ｆ７ 1995 11/28 2004 4.20"); printf("\n完全２乗アルゴリズム評価関数探索"); printf("\nProgramed By T.Ishizaki for Turbo C VC++ ver 5.0 \n\n"); printf("\nd15112計算専用"); dload();lo=lo+1; menu2: //si=pj/4; printf("\nシフト数");scanf("%d",&ssi);si=pj/ssi; printf("\nセット数");scanf("%d",&scj); printf("\n都市数 %d　シフト %d セット数　%d ",pj,ssi,scj); /* printf("\n\n1.Search"); printf("\n2.都市数"); printf("\n3.Gene initial"); printf("\n4.Data save"); printf("\n5.Data load"); printf("\n6.終了"); printf("\n7.探索セット数"); printf("\n8.優良解探索"); printf("\n9.表示"); printf("\n0.シフト数"); aa=0; scanf("%d",&aa); if(aa==0) {scanf("%d",&i);si=pj/i;goto menu2;} if(aa==1) {sc=0;est();goto menu2;} if(aa==2) {scanf("%d",&pj);goto menu1;} if(aa==3) {geneinit();ti=clock();lo=(double)3000*pj;} if(aa==4) {printf("\n File name ?");scanf("%s",&file);dsave();goto menu2;} if(aa==5) {dload();lo=lo+1;goto menu2;} if(aa==6) exit(0); if(aa==7) {printf("\nセット数");scanf("%d",&scj);goto menu2;} */ aa=8; if (aa==8) { printf("\n優良解探索"); printf("\n探索回数 10回の探索でセット数で設定された探索をします｡"); printf("\n\n探索回数?");kaj=10; //scanf("%d",&kaj); printf("\n最小値の出力ファイルネーム"); strcpy(file2,"v"); _itoa(ssi,file22,10); strcat(file2,file22); strcat(file2,"-"); _itoa(scj,file22,10); strcat(file2,file22); strcat(file2,"-10.txt"); printf("%s",file2); // scanf("%s",&file2); printf("\n優良解の経路と値の出力ファイルネーム"); //scanf("%s",&file); strcpy(file,"k"); _itoa(ssi,file22,10); strcat(file,file22); strcat(file,"-"); _itoa(scj,file22,10); strcat(file,file22); strcat(file,"-10.txt"); printf("%s",file); scanf("%d",&i); if(NULL==(fp2=fopen(file2,"w"))) {printf("\n\n Cannot open File %s",file2);exit(0);} lolo=(double)100000*pj; for(kai=1;kai<kaj+1;++kai) { printf("%s",st); printf("\n\n回数 %d\n\n",kai); printf("\n最優良値 %f \n",lolo); fprintf(fp2,"%s",st); fprintf(fp2,"\n\n回数 %d\n\n",kai); fprintf(fp2,"\n最優良値 %f \n",lolo); geneinit(); /* j=rand()%pj; geneshift(j); */ lo=(double)100000*pj;sc=0; geneinit(); est(); if(lo<lolo) {lolo=lo;dsave();} fprintf(fp2,"\n%f",lo); printf("\n%f\n\n",lo); } fclose(fp2); goto menu2; } if(aa==9){hyougi();goto menu2;} goto menu2; }//　main /* Estimate */ void est() { l520: /*printf(" ####"); */ sc=sc+1; if(sc==scj) goto l1010; /* gene shift */ /* printf("\ngene shift %d \n\n",si); if(pj<100) for(i=1;i<pj+1;++i){printf("%d ",gt[i]);} */ for(i=1;i<si+1;++i){g2[i]=gt[pj-si+i];} for(i=1;i<pj+1-si;++i){gt[pj-i+1]=gt[pj-si+1-i];} for(i=1;i<si+1;++i){gt[i]=g2[i];} /* printf("\n"); for(i=1;i<pj+1;++i){printf("%d ",gt[i]);} scanf("%d",&a); */ /* ｷｮﾘ ｼｮｷﾁ */ dd1 = 0;dd2=0;dd3=0; for(a=1;a<pj-1;++a){ if(a>2) dd1=dd1+hypot(px[gt[a-1]] - px[gt[a-2]], py[ gt[a-1] ] - py[ gt[a-2] ]) ; dd3=0; for(j=a+2;j<pj;++j) /* 元は pj pj+1 は間違い*/ { dd3 = dd3 + hypot(px[gt[j]] - px[gt[j + 1]], py[ gt[j] ] - py[ gt[j + 1] ]) ; } dd2=0; for(b=a+1;b<pj;++b){ if(b>a+2) dd2=dd2+hypot(px[gt[b-2]] - px[gt[b-1]], py[ gt[b-2] ] - py[ gt[b-1] ]) ; /*printf("\n a %d b %d",a,b); printf("\n dd1 %f dd2 %f dd3 %f",dd1,dd2,dd3); */ /*scanf("%d",&i); */ /* 2ﾃﾝﾉｺｳｶﾝ */ d1=dd1+dd2+dd3; if((a==1)&&(b==2)) { d1=d1+hypot(px[gt[b]] - px[gt[a]], py[ gt[b] ] - py[ gt[a] ]) ; d1=d1+hypot(px[gt[b]] - px[gt[pj]], py[ gt[b] ] - py[ gt[pj] ]) ; d1=d1+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } if((a==1)&&(b>2)) { d1=d1+hypot(px[gt[b]] - px[gt[pj]], py[ gt[b] ] - py[ gt[pj] ]) ; d1=d1+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; d1=d1+hypot(px[gt[a]] - px[gt[b-1]], py[ gt[a] ] - py[ gt[b-1] ]) ; d1=d1+hypot(px[gt[b]] - px[gt[a+1]], py[ gt[b] ] - py[ gt[a+1] ]) ; } if((a>1)&&(b==a+1)){ d1=d1+hypot(px[gt[1]] - px[gt[pj]], py[ gt[1] ] - py[ gt[pj] ]) ; d1=d1+hypot(px[gt[a-1]] - px[gt[b]], py[ gt[a-1] ] - py[ gt[b] ]) ; d1=d1+hypot(px[gt[a]] - px[gt[b]], py[ gt[a] ] - py[ gt[b] ]) ; d1=d1+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } if((a>1)&&(b>a+1)){ d1=d1+hypot(px[gt[1]] - px[gt[pj]], py[ gt[1] ] - py[ gt[pj] ]) ; d1=d1+hypot(px[gt[a-1]] - px[gt[b]], py[ gt[a-1] ] - py[ gt[b] ]) ; d1=d1+hypot(px[gt[b]] - px[gt[a+1]], py[ gt[b] ] - py[ gt[a+1] ]) ; d1=d1+hypot(px[gt[a]] - px[gt[b-1]], py[ gt[a] ] - py[ gt[b-1] ]) ; d1=d1+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } /* ｿｳﾆｭｳ */ d2=dd1+dd2+dd3; if((a==1)&&(b==2)) { d2=d2+hypot(px[gt[b]] - px[gt[pj]], py[ gt[b] ] - py[ gt[pj] ]) ; d2=d2+hypot(px[gt[a]] - px[gt[b]], py[ gt[a] ] - py[ gt[b] ]) ; d2=d2+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } if((a==1)&&(b>2)) { d2=d2+hypot(px[gt[a+1]] - px[gt[pj]], py[ gt[a+1] ] - py[ gt[pj] ]) ; d2=d2+hypot(px[gt[b-1]] - px[gt[b]], py[ gt[b-1] ] - py[ gt[b] ]) ; d2=d2+hypot(px[gt[b]] - px[gt[a]], py[ gt[b] ] - py[ gt[a] ]) ; d2=d2+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } if((a>1)&&(b==a+1)){ d2=d2+hypot(px[gt[1]] - px[gt[pj]], py[ gt[1] ] - py[ gt[pj] ]) ; d2=d2+hypot(px[gt[a-1]] - px[gt[b]], py[ gt[a-1] ] - py[ gt[b] ]) ; d2=d2+hypot(px[gt[a]] - px[gt[b]], py[ gt[a] ] - py[ gt[b] ]) ; d2=d2+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } if((a>1)&&(b>a+1)){ d2=d2+hypot(px[gt[1]] - px[gt[pj]], py[ gt[1] ] - py[ gt[pj] ]) ; d2=d2+hypot(px[gt[a-1]] - px[gt[a+1]], py[ gt[a-1] ] - py[ gt[a+1] ]) ; d2=d2+hypot(px[gt[b-1]] - px[gt[b]], py[ gt[b-1] ] - py[ gt[b] ]) ; d2=d2+hypot(px[gt[b]] - px[gt[a]], py[ gt[b] ] - py[ gt[a] ]) ; d2=d2+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } /* ｻﾌﾞﾂｱｰｦｷﾞｬｸﾆﾂﾅｸﾞ */ d3=dd1+dd2+dd3; if((a==1)&&(b==2)) { d3=d3+hypot(px[gt[b]] - px[gt[pj]], py[ gt[b] ] - py[ gt[pj] ]) ; d3=d3+hypot(px[gt[a]] - px[gt[b]], py[ gt[a] ] - py[ gt[b] ]) ; d3=d3+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } if((a==1)&&(b>2)) { d3=d3+hypot(px[gt[b]] - px[gt[pj]], py[ gt[b] ] - py[ gt[pj] ]) ; d3=d3+hypot(px[gt[b]] - px[gt[b-1]], py[ gt[b] ] - py[ gt[b-1] ]) ; d3=d3+hypot(px[gt[a]] - px[gt[a+1]], py[ gt[a] ] - py[ gt[a+1] ]) ; d3=d3+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } if((a>1)&&(b==a+1)){ d3=d3+hypot(px[gt[1]] - px[gt[pj]], py[ gt[1] ] - py[ gt[pj] ]) ; d3=d3+hypot(px[gt[a-1]] - px[gt[b]], py[ gt[a-1] ] - py[ gt[b] ]) ; d3=d3+hypot(px[gt[a]] - px[gt[b]], py[ gt[a] ] - py[ gt[b] ]) ; d3=d3+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } if((a>1)&&(b>a+1)){ d3=d3+hypot(px[gt[1]] - px[gt[pj]], py[ gt[1] ] - py[ gt[pj] ]) ; d3=d3+hypot(px[gt[a-1]] - px[gt[b]], py[ gt[a-1] ] - py[ gt[b] ]) ; d3=d3+hypot(px[gt[b]] - px[gt[b-1]], py[ gt[b] ] - py[ gt[b-1] ]) ; d3=d3+hypot(px[gt[a+1]] - px[gt[a]], py[ gt[a+1] ] - py[ gt[a] ]) ; d3=d3+hypot(px[gt[a]] - px[gt[b+1]], py[ gt[a] ] - py[ gt[b+1] ]) ; } s=s+1; comp: if(pf==1){ printf("\n lo %f ",lo); printf("d1 %f ",d1); printf("d2 %f ",d2); printf("d3 %f ",d3); scanf("%d",&pf); } if((d3<d2)&&(d3<d1)) {if (d3<=lo) { w=abs(a-b)+1; if(a>b) {sp=b;ep=a;} else {sp=a;ep=b;} for(i=sp;i<ep+1;++i){t[i-sp+1]=gt[i];} for(i=1;i<w+1;++i){gt[i+sp-1]=t[w-i+1];} df=3; lo=d3;goto l200;}} /* d2 ｶﾞ ｻｲｼｮｳ ? */ if((d2<d3)&&(d2<d1)) { if (d2<lo) { /*printf("\n"); for(i=1;i<pj+1;++i){printf(" %d ",gt[i]);} */ df=2; lo=d2; jj=gt[a]; for(i=a;i<pj+1;++i){gt[i]=gt[i+1];} i=pj+1; l100: i=i-1; if(i>b){gt[i]=gt[i-1];goto l100;} gt[b]=jj; if(b>=a+2){ dd2=dd2-hypot(px[gt[a]] - px[gt[a+1]], py[ gt[a] ] - py[ gt[a+1] ]) ; dd2=dd2+hypot(px[gt[b-1]] - px[gt[b-2]], py[ gt[b-1] ] - py[ gt[b-2] ]) ; } goto l200;}} if (d1>=lo) goto l200; lo=d1; jj=gt[a];gt[a]=gt[b];gt[b]=jj; df=1; l200: if(f==1) goto l1000; sc=0; l250: st[0]=12;st[1]=0; printf("%s",st); d11=0; for(i=1;i<pj;++i){d11=d11+hypot(px[gt[i]] - px[gt[i+1]], py[ gt[i] ] - py[ gt[i+1] ]) ;} d11=d11+hypot(px[gt[1]] - px[gt[pj]], py[ gt[1] ] - py[ gt[pj] ]) ; //printf("\nd11 %f",d11); //printf("\n a %d b %d",a,b); //printf("\n dd1 %f dd2 %f dd3 %f",dd1,dd2,dd3); printf( "\nＴＳＰ　Ｐｒｏｇｒａｍ Ｆ７ 1995 11/28"); printf( "\n\n都市数 %d 世代 %f a= %d b=%d ",pj,s,a,b); printf( "\n評価値 %f sc %d", lo,sc); printf("\nTime %d",clock()-ti); // printf("\n d1 %f d2 %f d3 %f",d1,d2,d3); // printf("\n 1,pj %f",hypot(px[gt[1]] - px[gt[pj]], py[ gt[1] ] - py[ gt[pj] ])) ; // printf("\n a,a+1 %f",hypot(px[gt[a]] - px[gt[a+1]], py[ gt[a] ] - py[ gt[a+1] ])) ; // printf("\n b,b+1 %f",hypot(px[gt[b]] - px[gt[b+1]], py[ gt[b] ] - py[ gt[b+1] ])) ; // printf("\n lo-d11 %f",d11-lo); // printf("\n 操作 %d",df); hyougi(); scanf("%d",&f); l1000: printf(""); if(b+2<pj) dd3=dd3-hypot(px[gt[b+1]] - px[gt[b+2]], py[ gt[b+1] ] - py[ gt[b+2] ]) ; } /*loop b*/ dd2= 0; if(_kbhit()!=0) ss=_getch(); else ss=0; if(ss==' ') { if(f==0){f=1;printf("\n高速モード");} else {f=0;printf("表示 a %d b %d sc %d lo %f",a,b,sc,lo);}} if(ss=='e') {printf("a %d b %d sc %d",a,b,sc); goto l1010;} if(ss=='c') {printf("\n f=0");f=0;} if(ss=='p') {pf=pf+1;pf=pf%2;printf("\n動作トレース %d",pf);} if(ss=='s') dsave(); if(ss=='d') {printf("\n input a %d ",a);scanf("%d",&a); printf("\n input b %d ",b);scanf("%d",&b); } if(ss=='l') {printf("lo %f",lo);scanf("%f",&lo);} } /*loop a*/ goto l520; l1010: printf("\n"); } /* Gene init */ void geneinit() { srand( (unsigned)time( NULL ) ); for(j=1;j<pj+1;++j) { g[j] = rand()%(pj - j + 1) + 1; } for(j=1;j<pj+1;++j){t[j] = j; } for(jj=1;jj<pj+1;++jj) { gt[jj] = t[g[jj]]; for(j= g[jj] + 1 ;j< pj - jj + 1+1;++j){t[j - 1] = t[j]; } //if(jj<100) printf("%d ",gt[jj]); } //printf("\n"); } /* gene shift */ void geneshift(int sif) { printf("\ngene shift %d \n\n",sif); if(pj<100) for(i=1;i<pj+1;++i){printf("%d ",gt[i]);} for(i=1;i<sif+1;++i){g2[i]=gt[pj-sif+i];} for(i=1;i<pj+1-sif;++i){gt[pj-i+1]=gt[pj-sif+1-i];} for(i=1;i<sif+1;++i){gt[i]=g2[i];} } void dsave() { /*printf("\n File save Program"); printf("\n File name ?"); scanf("%s",&file); */ if(NULL==(fp=fopen(file,"w"))) { printf("\n\n Cannot open File %s",file);exit(0); } fprintf(fp,"%d\n",pj); fprintf(fp,"%f\n",lo); for(i=1;i<pj+1;++i) { fprintf(fp,"%f\n",px[i]); fprintf(fp,"%f\n",py[i]); } for(i=1;i<pj+1;++i) { fprintf(fp,"%d\n",gt[i]); } fclose(fp); } void dload() { printf("\n File load Program"); printf("\n File name ?"); //scanf("%s",&file); if(NULL==(fp=fopen("d15112.dat","r"))) {printf("\n\n Cannot open File %s",file);exit(0);} fgets(buff,255,fp); ff=atof(buff); pj=(int)ff; fgets(buff,255,fp); lo=atof(buff); for(i=1;i<pj+1;++i) { fgets(buff,255,fp); ff=atof(buff); px[i]=(float)ff; fgets(buff,255,fp); ff=atof(buff); py[i]=(float)ff; } for(i=1;i<pj+1;++i) { fgets(buff,255,fp); ff=atof(buff); gt[i]=(int)ff; } fclose(fp); } void hyougi(void){ //screen_int(0); /* 画面初期化 */ gint(640*2,480*2); gcls(); for(i=1;i<pj+1;++i) { rectangle(xx + px[i]/rr - 2, yy + py[i]/rr - 2,xx + px[i]/rr + 2, yy + py[i]/rr + 2,2); rectangle(xx+px[gt[a]]/rr-2,yy+py[gt[a]]/rr-2,xx+px[gt[a]]/rr+2,yy+py[gt[a]]/rr+2,7); rectangle(xx+px[gt[b]]/rr-2,yy+py[gt[b]]/rr-2,xx+px[gt[b]]/rr+2,yy+py[gt[b]]/rr+2,7); } for(i=1;i<pj;++i) { line(xx + px[ gt[i] ]/rr, yy + py[ gt[i] ]/rr,xx + px[ gt[i+1] ]/rr,yy + py[ gt[i+1] ]/rr,7); } line(xx + px[ gt[1] ]/rr, yy + py[ gt[1] ]/rr,xx + px[gt[ pj]]/rr, yy + py[ gt[pj] ]/rr,7); }//