静岡理工科大学 菅沼ホーム 目次 索引

逐次改善法( TSP )

    1. A. C++
    2. B. Java
    3. C. PHP
    4. D. Ruby
    5. E. Python
    6. F. C#
    7. G. VB

  プログラム(使用方法)は,巡回セールスマン問題( TSP )を逐次改善法によって解くためのものです.なお,このプログラムは,クラスを使用して記述しています.

  1. C++

      C++11 においては,「メルセンヌ・ツイスター法による擬似乱数生成エンジン」を使用することができます.
    /****************************/
    /* 巡回セールスマン問題     */
    /*      反復改善法          */
    /*      coded by Y.Suganuma */
    /****************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    #include <time.h>
    #include "MT.h"
    
    int kyori(int, int *, int **);
    
    /*************************/
    /* クラスIterationの定義 */
    /*************************/
    class Iteration {
    		int **city;   //都市の位置データ
    		int max_try;   // 最大試行回数
    		int n_city;   // 都市の数
    		int out_d;   // 表示間隔
    		int **rg;   // 都市間の距離
    		int *seq_w1;   // 都市を訪れる順序(ワーク)
    		int *seq_w2;   // 都市を訪れる順序(ワーク)
    		int neib;   // 近傍(2 or 3)
    		int out_lvl;   // 出力レベル
                           //   =0 : 最終出力だけ
                           //   n>0 : n回毎に出力(負の時はファイル)
    		int out_m;   // 出力方法
                         //   =-1 : 出力しない
                         //   =0 : すべてを出力
                         //   =1 : 評価値だけを出力(最終結果だけはすべてを出力)
    		int sel;   // エッジの選択方法
                       //   =0 : 最良のものを選択
                       //   =1 : 最初のものを選択
    		char o_file[100];   // 出力ファイル名
    	public:
    		int *seq;   // 都市を訪れる順序
    		Iteration(long, char *);   // コンストラクタ
    		Iteration (int, int, int, int, int, int, int, char *, int **);   // コンストラクタ
    		Iteration();   // コンストラクタ
    		~Iteration();   // デストラクタ
    		int Optimize();   // 最適化の実行
    		int Change(int *);   // 改善
    		void Output(int, int, int);   // 出力
    };
    
    /****************************/
    /* コンストラクタ           */
    /*      seed : 乱数の初期値 */
    /*      name : ファイル名   */
    /****************************/
    Iteration::Iteration (long seed, char *name)
    {
    	double x, y;
    	int ct, i1, i2, sw;
    	FILE *in;
    					// 乱数の初期設定
    	init_genrand(seed);
    					// ファイルのオープン
    	in = fopen(name, "r");
    	if (in == NULL) {
    		printf("***error  データファイル名が不適当\n");
    		exit(1);
    	}
    					// 基本データ
    	fscanf(in, "%*s %d %*s %d %*s %d %*s %d", &n_city, &max_try, &sel, &neib);
    	fscanf(in, "%*s %d %*s %d", &out_lvl, &out_m);
    	fscanf(in, "%*s %s %*s %d", o_file, &out_d);
    					// 都市の位置データ
    	city = new int * [n_city];
    	for (i1 = 0; i1 < n_city; i1++) {
    		city[i1] = new int [2];
    		fscanf(in, "%d %d", &city[i1][0], &city[i1][1]);
    	}
    					// ファイルのクローズ
    	fclose(in);
    					// 距離テーブルの作成
    	rg = new int * [n_city];
    
    	for (i1 = 0; i1 < n_city; i1++) {
    		rg[i1] = new int [n_city];
    		for (i2 = i1+1; i2 < n_city; i2++) {
    			x          = city[i2][0] - city[i1][0];
    			y          = city[i2][1] - city[i1][1];
    			rg[i1][i2] = (int)(sqrt(x * x + y * y) + 0.5);
    		}
    	}
    
    	for (i1 = 1; i1 < n_city; i1++) {
    		for (i2 = 0; i2 < i1; i2++)
    			rg[i1][i2] = rg[i2][i1];
    	}
    					// 都市を訪れる順序(初期設定)
    	seq    = new int [n_city];
    	seq_w1 = new int [n_city];
    	seq_w2 = new int [n_city];
    
    	for (i1 = 0; i1 < n_city; i1++) {
    		sw = 0;
    		while (sw == 0) {
    			ct = (int)(genrand_real3() * n_city);
    			if (ct >= n_city)
    				ct = n_city - 1;
    			seq[i1] = ct;
    			sw      = 1;
    			for (i2 = 0; i2 < i1 && sw > 0; i2++) {
    				if (ct == seq[i2])
    					sw = 0;
    			}
    		}
    	}
    }
    
    /******************/
    /* コンストラクタ */
    /******************/
    Iteration::Iteration ()
    {
    	n_city = 0;
    }
    
    /****************/
    /* デストラクタ */
    /****************/
    Iteration::~Iteration ()
    {
    	int i1;
    
    	if (n_city > 0) {
    
    		for (i1 = 0; i1 < n_city; i1++) {
    			delete [] city[i1];
    			delete [] rg[i1];
    		}
    		delete [] city;
    		delete [] rg;
    
    		delete[] seq;
    		delete [] seq_w1;
    		delete [] seq_w2;
    	}
    }
    
    /****************/
    /* 最適化の実行 */
    /****************/
    int Iteration::Optimize ()
    {
    	int k1, max, n_tri, sw;
    					// 初期設定
    	n_tri = 0;
    	max   = kyori(n_city, seq, rg);
    
    	if (out_m >= 0 && abs(out_lvl) > 0) {
    		printf("***試行回数 %d 距離 %d\n", n_tri, -max);
    		Output(out_lvl, n_tri, max);
    	}
    					// 実行
    	sw = 1;
    	for (n_tri = 1; n_tri <= max_try && sw > 0; n_tri++) {
    						// 改善
    		sw = Change(&max);
    						// 出力
    		if (out_d > 0 && n_tri%out_d == 0)
    			printf("***試行回数 %d 距離 %d\n", n_tri, -max);
    
    		if (out_m >= 0 && abs(out_lvl) > 0) {
    			if (n_tri%abs(out_lvl) == 0)
    				Output(out_lvl, n_tri, max);
    		}
    	}
    					// 最終出力
    	if (out_m >= 0) {
    		n_tri--;
    		k1    = out_m;
    		out_m = 0;
    		printf("***試行回数 %d 距離 %d\n", n_tri, -max);
    		Output(out_lvl, n_tri, max);
    		out_m = k1;
    	}
    
    	return n_tri;
    }
    
    /*******************************/
    /* 出力                        */
    /*      sw : >=0 : 出力先未定  */
    /*           < 0 : ファイル    */
    /*      n_tri : 現在の試行回数 */
    /*      r : 距離の負値         */
    /*******************************/
    void Iteration::Output(int sw, int n_tri, int r)
    {
    	int i1, k = 0, n, pr;
    	char *now;
    	time_t aclock;
    	FILE *out;
    
    	if (sw >= 0) {
    		printf("   出力先は(0:出力なし,n:画面にn個づつ,-1:ファイル)? ");
    		scanf("%d", &pr);
    	}
    	else
    		pr = -1;
    
    	if (pr != 0) {
    
    		if (pr > 0) {
    			out = stdout;
    			getchar();
    		}
    		else {
    			time(&aclock);
    			now = ctime(&aclock);
    			out = fopen(o_file, "a");
    			fprintf(out, "***試行回数 %d 距離 %d 時間 %s\n", n_tri, -r, now);
    		}
    
    		if (out_m == 0) {
    			for (i1 = 0; i1 < n_city; i1++) {
    				n = seq[i1];
    				fprintf(out, "  %d %d %d\n", n, city[n][0], city[n][1]);
    				if (pr > 0) {
    					k++;
    					if (k == pr) {
    						getchar();
    						k = 0;
    					}
    				}
    			}
    		}
    
    		if (pr <= 0)
    			fclose(out);
    	}
    }
    
    /**************************************/
    /* エッジの入れ替え                   */
    /*      r_m : 距離の負値              */
    /*      return : =0 : 改善がなかった  */
    /*               =1 : 改善があった    */
    /**************************************/
    int Iteration::Change(int *r_m)
    {
    	int ch = 0, i1, i2, i3, i4, k, k1, k2, max, n1, n2, n3, nn, r, sw = 0;
    
    	max = *r_m;
    
    	n3  = (int)(genrand_real3() * (n_city - 2));
    	if (n3 > n_city-3)
    		n3 = n_city - 3;
                             // 2近傍
    	for (i1 = 0; i1 <= n_city-3 && ch == 0; i1++) {
    
    		if (n3 == 0)
    			n1 = n_city - 2;
    		else
    			n1 = n_city - 1;
    
    		for (i2 = n3+2; i2 <= n1 && ch == 0; i2++) {
                                  // 枝の場所((n3,n3+1), (k1,k2))
    			k1 = i2;
    			if (i2 == n_city-1)
    				k2 = 0;
    			else
    				k2 = i2 + 1;
                                  // 枝の入れ替え
    			seq_w1[0] = seq[n3];
    			k         = 1;
    			for (i3 = k1; i3 >= n3+1; i3--) {
    				seq_w1[k] = seq[i3];
    				k++;
    			}
    
    			nn = k2;
    			while (nn != n3) {
    				seq_w1[k] = seq[nn];
    				k++;
    				nn++;
    				if (nn > n_city-1)
    					nn = 0;
    			}
                                  // 評価
    			r = kyori(n_city, seq_w1, rg);
    
    			if (r > max) {
    				max = r;
    				sw  = 1;
    				for (i3 = 0; i3 < n_city; i3++)
    					seq_w2[i3] = seq_w1[i3];
    				if (sel > 0)
    					ch = 1;
    			}
    		}
    
    		n3++;
    		if (n3 > n_city-3)
    			n3 = 0;
    	}
                             // 3近傍
    	if (neib == 3 && ch == 0) {
    
    		for (i1 = 0; i1 <= n_city-3 && ch == 0; i1++) {
    
    			n1 = n_city - 2;
    			n2 = n_city - 1;
    
    			for (i2 = n3+1; i2 <= n1 && ch == 0; i2++) {
    
    				for (i3 = i2+1; i3 <= n2 && ch == 0; i3++) {
                                  // 枝の場所((n3,n3+1), (i2,i2+1), (k1,k2))
    					k1 = i3;
    					if (i3 == n_city-1)
    						k2 = 0;
    					else
    						k2 = i3 + 1;
                                  // 枝の入れ替えと評価
                                       // 入れ替え(その1)
    					seq_w1[0] = seq[n3];
    					k         = 1;
    					for (i4 = i2; i4 >= n3+1; i4--) {
    						seq_w1[k] = seq[i4];
    						k++;
    					}
    
    					for (i4 = k1; i4 >= i2+1; i4--) {
    						seq_w1[k] = seq[i4];
    						k++;
    					}
    
    					nn = k2;
    					while (nn != n3) {
    						seq_w1[k] = seq[nn];
    						k++;
    						nn++;
    						if (nn > n_city-1)
    							nn = 0;
    					}
                                       // 評価(その1)
    					r = kyori(n_city, seq_w1, rg);
    
    					if (r > max) {
    						max = r;
    						sw  = 1;
    						for (i3 = 0; i3 < n_city; i3++)
    							seq_w2[i3] = seq_w1[i3];
    						if (sel > 0)
    							ch = 1;
    					}
                                       // 入れ替え(その2)
    					seq_w1[0] = seq[n3];
    					k         = 1;
    					for (i4 = k1; i4 >= i2+1; i4--) {
    						seq_w1[k] = seq[i4];
    						k++;
    					}
    
    					for (i4 = n3+1; i4 <= i2; i4++) {
    						seq_w1[k] = seq[i4];
    						k++;
    					}
    
    					nn = k2;
    					while (nn != n3) {
    						seq_w1[k] = seq[nn];
    						k++;
    						nn++;
    						if (nn > n_city-1)
    							nn = 0;
    					}
                                       // 評価(その2)
    					r = kyori(n_city, seq_w1, rg);
    
    					if (r > max) {
    						max = r;
    						sw  = 1;
    						for (i3 = 0; i3 < n_city; i3++)
    							seq_w2[i3] = seq_w1[i3];
    						if (sel > 0)
    							ch = 1;
    					}
                                       // 入れ替え(その3)
    					seq_w1[0] = seq[n3];
    					k         = 1;
    					for (i4 = i2+1; i4 <= k1; i4++) {
    						seq_w1[k] = seq[i4];
    						k++;
    					}
    
    					for (i4 = i2; i4 >= n3+1; i4--) {
    						seq_w1[k] = seq[i4];
    						k++;
    					}
    
    					nn = k2;
    					while (nn != n3) {
    						seq_w1[k] = seq[nn];
    						k++;
    						nn++;
    						if (nn > n_city-1)
    							nn = 0;
    					}
                                       // 評価(その3)
    					r = kyori(n_city, seq_w1, rg);
    
    					if (r > max) {
    						max = r;
    						sw  = 1;
    						for (i3 = 0; i3 < n_city; i3++)
    							seq_w2[i3] = seq_w1[i3];
    						if (sel > 0)
    							ch = 1;
    					}
                                       // 入れ替え(その4)
    					seq_w1[0] = seq[n3];
    					k         = 1;
    					for (i4 = i2+1; i4 <= k1; i4++) {
    						seq_w1[k] = seq[i4];
    						k++;
    					}
    
    					for (i4 = n3+1; i4 <= i2; i4++) {
    						seq_w1[k] = seq[i4];
    						k++;
    					}
    
    					nn = k2;
    					while (nn != n3) {
    						seq_w1[k] = seq[nn];
    						k++;
    						nn++;
    						if (nn > n_city-1)
    							nn = 0;
    					}
                                       // 評価(その4)
    					r = kyori(n_city, seq_w1, rg);
    
    					if (r > max) {
    						max = r;
    						sw  = 1;
    						for (i3 = 0; i3 < n_city; i3++)
    							seq_w2[i3] = seq_w1[i3];
    						if (sel > 0)
    							ch = 1;
    					}
    				}
    			}
    
    			n3++;
    			if (n3 > n_city-3)
    				n3 = 0;
    		}
    	}
                             // 設定
    	if (sw > 0) {
    		*r_m = max;
    		for (i1 = 0; i1 < n_city; i1++)
    			seq[i1] = seq_w2[i1];
    	}
    
    	return sw;
    }
    
    /*********************************/
    /* 距離の計算                    */
    /*      n_c : 都市の数           */
    /*      p : 都市番号             */
    /*      rg : 都市間の距離        */
    /*      return : 距離(負)      */
    /*********************************/
    int kyori(int n_c, int *p, int **rg)
    {
    	int i1, n1, n2, range = 0;
    
    	n1 = p[0];
    
    	for (i1 = 1; i1 < n_c; i1++) {
    		n2     = p[i1];
    		range -= rg[n1][n2];
    		n1     = n2;
    	}
    
    	n2     = p[0];
    	range -= rg[n1][n2];
    
    	return range;
    }
    
    /****************/
    /* main program */
    /****************/
    int main(int argc, char *argv[])
    {
    	long *seed;
    	int i1, n;
    	char **i_file;
    	FILE *in;
    	Iteration *it;
    					// 入力ミス
    	if (argc <= 1) {
    		printf("***error  ファイル名を入力して下さい\n");
    		exit(1);
    	}
    					// 入力OK
    	else {
    						// ファイルのオープン
    		in = fopen(argv[1], "r");
    		if (in == NULL) {
    			printf("***error  ファイル名が不適当です\n");
    			exit(1);
    		}
    						// 入力データファイル名の入力
    		fscanf(in, "%d", &n);
    
    		seed   = new long [n];
    		i_file = new char * [n];
    
    		for (i1 = 0; i1 < n; i1++) {
    			i_file[i1] = new char [100];
    			fscanf(in, "%s", i_file[i1]);
    			seed[i1] = 1000 * i1 + 1234567;
    		}
    
    		fclose(in);
    						// 実行(乱数の初期値を変える)
    		for (i1 = 0; i1 < n; i1++) {
    			printf("\n+++++ケース %d+++++\n", i1+1);
    							// 入力と初期設定
    			it = new Iteration (seed[i1], i_file[i1]);
    							// 最適化
    			it->Optimize();
    		}
    	}
    
    	return 0;
    }
    
    
    //------------------------ケーススタディデータ(data.txt)------
    /*
    3
    data1.txt
    data1.txt
    data2.txt
    */
    //---------------------データファイル(data1.txt)------------
    /*
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    -58 37
    55 -19
    6 -79
    27 -30
    44 -94
    33 -58
    -94 87
    -9 3
    33 69
    43 -57
    */
    
    //---------------------データファイル(data2.txt)------------
    /*
    都市の数 50 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    86 27
    82 16
    29 37
    27  1
    90 88
    40 92
    87 53
    24 99
    11 80
    61  8
    30 93
     4 81
    86 90
    84 52
    96 45
     4 34
    53  6
    45 12
    23 97
    61 46
    49 16
    82 74
    48 36
    13  5
    12  6
    33 26
     8 50
    98 98
    79 65
    36 56
    42 25
    52 12
    88 79
    27 51
    86 51
    14 35
    77 37
    44  0
    78 13
    21 55
    82 26
    25 88
    55  0
    10 59
    41 33
     7  4
    56 99
    19 34
    92 46
    27 35
    */
    
    //---------------------MT.h---------------------------
    //   A C-program for MT19937, with initialization improved 2002/1/26.
    //   Coded by Takuji Nishimura and Makoto Matsumoto.
    //
    //   Before using, initialize the state by using init_genrand(seed)  
    //   or init_by_array(init_key, key_length).
    //
    //   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
    //   All rights reserved.                          
    //
    //   Redistribution and use in source and binary forms, with or without
    //   modification, are permitted provided that the following conditions
    //   are met:
    //
    //     1. Redistributions of source code must retain the above copyright
    //        notice, this list of conditions and the following disclaimer.
    //
    //     2. Redistributions in binary form must reproduce the above copyright
    //        notice, this list of conditions and the following disclaimer in the
    //        documentation and/or other materials provided with the distribution.
    //
    //     3. The names of its contributors may not be used to endorse or promote 
    //        products derived from this software without specific prior written 
    //        permission.
    //
    //   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    //   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    //   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    //   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
    //   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    //   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    //   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
    //   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
    //   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
    //   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
    //   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    //
    //
    //   Any feedback is very welcome.
    //   http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
    //   email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
    
    
    //   The original version of http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c was modified by Takahiro Omi as
    //   - delete line 47 "#include<stdio.h>"
    //   - delete line 174 int main(void){...}
    //   - change N -> MT_N
    //   - change N -> MT_N
    //   - change the file name "mt19937ar.c" -> "MT.h"
    
    
    /*
    // Period parameters
    #define MT_N 624
    #define MT_M 397
    #define MATRIX_A 0x9908b0dfUL   // constant vector a
    #define UPPER_MASK 0x80000000UL // most significant w-r bits
    #define LOWER_MASK 0x7fffffffUL // least significant r bits
    
    static unsigned long mt[MT_N]; // the array for the state vector
    static int mti=MT_N+1; // mti==MT_N+1 means mt[MT_N] is not initialized
    
    // initializes mt[MT_N] with a seed
    void init_genrand(unsigned long s)
    {
        mt[0]= s & 0xffffffffUL;
        for (mti=1; mti<MT_N; mti++) {
            mt[mti] = 
    	    (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); 
            // See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier.
            // In the previous versions, MSBs of the seed affect
            // only MSBs of the array mt[].
            // 2002/01/09 modified by Makoto Matsumoto
            mt[mti] &= 0xffffffffUL;
            // for >32 bit machines
        }
    }
    
    // initialize by an array with array-length
    // init_key is the array for initializing keys
    // key_length is its length
    // slight change for C++, 2004/2/26
    void init_by_array(unsigned long init_key[], int key_length)
    {
        int i, j, k;
        init_genrand(19650218UL);
        i=1; j=0;
        k = (MT_N>key_length ? MT_N : key_length);
        for (; k; k--) {
            mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525UL))
              + init_key[j] + j; // non linear
            mt[i] &= 0xffffffffUL; // for WORDSIZE > 32 machines
            i++; j++;
            if (i>=MT_N) { mt[0] = mt[MT_N-1]; i=1; }
            if (j>=key_length) j=0;
        }
        for (k=MT_N-1; k; k--) {
            mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941UL))
              - i; // non linear
            mt[i] &= 0xffffffffUL; // for WORDSIZE > 32 machines
            i++;
            if (i>=MT_N) { mt[0] = mt[MT_N-1]; i=1; }
        }
    
        mt[0] = 0x80000000UL; // MSB is 1; assuring non-zero initial array
    }
    
    // generates a random number on [0,0xffffffff]-interval
    unsigned long genrand_int32(void)
    {
        unsigned long y;
        static unsigned long mag01[2]={0x0UL, MATRIX_A};
        // mag01[x] = x * MATRIX_A  for x=0,1
    
        if (mti >= MT_N) { // generate N words at one time
            int kk;
    
            if (mti == MT_N+1)   // if init_genrand() has not been called,
                init_genrand(5489UL); // a default initial seed is used
    
            for (kk=0;kk<MT_N-MT_M;kk++) {
                y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
                mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y & 0x1UL];
            }
            for (;kk<MT_N-1;kk++) {
                y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
                mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
            }
            y = (mt[MT_N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
            mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];
    
            mti = 0;
        }
      
        y = mt[mti++];
    
        // Tempering
        y ^= (y >> 11);
        y ^= (y << 7) & 0x9d2c5680UL;
        y ^= (y << 15) & 0xefc60000UL;
        y ^= (y >> 18);
    
        return y;
    }
    
    // generates a random number on [0,0x7fffffff]-interval
    long genrand_int31(void)
    {
        return (long)(genrand_int32()>>1);
    }
    
    // generates a random number on [0,1]-real-interval
    double genrand_real1(void)
    {
        return genrand_int32()*(1.0/4294967295.0); 
        // divided by 2^32-1
    }
    
    // generates a random number on [0,1)-real-interval
    double genrand_real2(void)
    {
        return genrand_int32()*(1.0/4294967296.0); 
        // divided by 2^32
    }
    
    // generates a random number on (0,1)-real-interval
    double genrand_real3(void)
    {
        return (((double)genrand_int32()) + 0.5)*(1.0/4294967296.0); 
        // divided by 2^32
    }
    
    // generates a random number on [0,1) with 53-bit resolution
    double genrand_res53(void) 
    { 
        unsigned long a=genrand_int32()>>5, b=genrand_int32()>>6; 
        return(a*67108864.0+b)*(1.0/9007199254740992.0); 
    } 
    // These real versions are due to Isaku Wada, 2002/01/09 added
    */
    			

  2. Java

      中間結果,及び,最終結果を,図示することが可能です.
    /****************************/
    /* 巡回セールスマン問題     */
    /*      反復改善法          */
    /*      coded by Y.Suganuma */
    /****************************/
    import java.io.*;
    import java.util.Random;
    import java.util.Date;
    import java.util.StringTokenizer;
    import java.awt.*;
    import java.awt.event.*;
    
    /*************************/
    /* クラスIterationの定義 */
    /*************************/
    class Iteration {
    	private int max_try;   // 最大試行回数
    	private int neib;   // 近傍(2 or 3)
    	private int out_d;   // 表示間隔
    	private int [][] rg;   // 都市間の距離
    	private int [] seq_w1;   // 都市を訪れる順序(ワーク)
    	private int [] seq_w2;   // 都市を訪れる順序(ワーク)
    	private int out_lvl;   // 出力レベル
                               //   =0 : 最終出力だけ
                               //   n>0 : n回毎に出力(負の時はファイル)
    	private int out_m;   // 出力方法
                             //   =-1 : 出力しない
                             //   =0 : すべてを出力
                             //   =1 : 評価値だけを出力(最終結果だけはすべてを出力)
    	private int sel;   // エッジの選択方法
                           //   =0 : 最良のものを選択
                           //   =1 : 最初のものを選択
    	private String o_file;   // 出力ファイル名
    	private Win_it wn;   // Win_itオブジェクト
    	private Random rn;   // 乱数
    
    	int [][] city;   //都市の位置データ
    	int n_city;   // 都市の数
    	int n_tri;   // 試行回数
    	int [] seq;   // 都市を訪れる順序
    	int n_eg;   // 交換した枝の数
    	int [] eg;   // 交換した枝
    	int range;   // 現在の評価値
    	int display;   // 画面表示
                       //   =0 : 画面表示を行わない
                       //   =1 : 結果だけを表示
                       //   =2 : 初期状態と結果を表示
                       //   =3 : ワンステップ毎表示
    
    	/****************************/
    	/* コンストラクタ           */
    	/*      seed : 乱数の初期値 */
    	/*      name : ファイル名   */
    	/****************************/
    	Iteration (int seed, String name) throws IOException, FileNotFoundException
    	{
    		double x, y;
    		int ct, i1, i2, sw;
    		String line;
    		StringTokenizer dt;
    		BufferedReader in = new BufferedReader(new FileReader(name));
    
    		n_tri = 0;
    		n_eg  = 0;
    		eg    = new int [6];
    						// 乱数の初期設定
    		rn  = new Random(seed);
    						// 基本データ
    		line = in.readLine();
    		dt   = new StringTokenizer(line, " ");
    		dt.nextToken();
    		n_city = Integer.parseInt(dt.nextToken());
    		dt.nextToken();
    		max_try = Integer.parseInt(dt.nextToken());
    		dt.nextToken();
    		sel = Integer.parseInt(dt.nextToken());
    		dt.nextToken();
    		neib = Integer.parseInt(dt.nextToken());
    
    		line = in.readLine();
    		dt   = new StringTokenizer(line, " ");
    		dt.nextToken();
    		out_lvl = Integer.parseInt(dt.nextToken());
    		dt.nextToken();
    		out_m = Integer.parseInt(dt.nextToken());
    
    		line = in.readLine();
    		dt   = new StringTokenizer(line, " ");
    		dt.nextToken();
    		o_file = dt.nextToken();
    		dt.nextToken();
    		out_d = Integer.parseInt(dt.nextToken());
    
    		line = in.readLine();
    		dt   = new StringTokenizer(line, " ");
    		dt.nextToken();
    		display = Integer.parseInt(dt.nextToken());
    
    		line = in.readLine();
    		dt   = new StringTokenizer(line, " ");
    		dt.nextToken();
    		int font = Integer.parseInt(dt.nextToken());
    		dt.nextToken();
    		int width = Integer.parseInt(dt.nextToken());
    		int height = Integer.parseInt(dt.nextToken());
    						// 都市の位置データ
    		city = new int [n_city][2];
    		for (i1 = 0; i1 < n_city; i1++) {
    			line = in.readLine();
    			dt   = new StringTokenizer(line, " ");
    			city[i1][0] = Integer.parseInt(dt.nextToken());
    			city[i1][1] = Integer.parseInt(dt.nextToken());
    		}
    						// ファイルのクローズ
    		in.close();
    						// 距離テーブルの作成
    		rg = new int [n_city][n_city];
    
    		for (i1 = 0; i1 < n_city; i1++) {
    			for (i2 = i1+1; i2 < n_city; i2++) {
    				x          = city[i2][0] - city[i1][0];
    				y          = city[i2][1] - city[i1][1];
    				rg[i1][i2] = (int)(Math.sqrt(x * x + y * y) + 0.5);
    			}
    		}
    
    		for (i1 = 1; i1 < n_city; i1++) {
    			for (i2 = 0; i2 < i1; i2++)
    				rg[i1][i2] = rg[i2][i1];
    		}
    						// 都市を訪れる順序(初期設定)
    		seq    = new int [n_city];
    		seq_w1 = new int [n_city];
    		seq_w2 = new int [n_city];
    
    		for (i1 = 0; i1 < n_city; i1++) {
    			sw = 0;
    			while (sw == 0) {
    				ct = (int)(rn.nextDouble() * n_city);
    				if (ct >= n_city)
    					ct = n_city - 1;
    				seq[i1] = ct;
    				sw      = 1;
    				for (i2 = 0; i2 < i1 && sw > 0; i2++) {
    					if (ct == seq[i2])
    						sw = 0;
    				}
    			}
    		}
    						// Windowの生成
    		if (display > 0)
    			wn = new Win_it (this, font, width, height);
    	}
    
    	/****************/
    	/* 最適化の実行 */
    	/****************/
    	int Optimize () throws IOException, FileNotFoundException
    	{
    		int k1, sw;
    		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    					// ワンステップづつ実行しない場合
    		if (display < 3) {
    						// 初期設定
    			range = kyori(n_city, seq, rg);
    						// 初期状態の出力(図)
    			if (display == 2) {
    				wn.Draw();
    				System.out.println("   図を確認したらreturnキーを押してください");
    				in.readLine();
    			}
    						// 初期状態の出力(文字)
    			if (out_m >= 0 && Math.abs(out_lvl) > 0) {
    				System.out.println("***試行回数 " + n_tri + " 距離 " + (-range));
    				Output(out_lvl);
    			}
    						// 実行
    			sw = 1;
    			for (n_tri = 1; n_tri <= max_try && sw > 0; n_tri++) {
    							// 改善
    				sw = Change();
    							// 出力(文字)
    				if (out_d > 0 && n_tri%out_d == 0)
    					System.out.println("***試行回数 " + n_tri + " 距離 " + (-range));
    
    				if (out_m >= 0 && Math.abs(out_lvl) > 0) {
    					if (n_tri%Math.abs(out_lvl) == 0)
    						Output(out_lvl);
    				}
    			}
    						// 最終出力(図)
    			if (display == 1 || display == 2) {
    				wn.Draw();
    				System.out.println("   図を確認したらreturnキーを押してください");
    				in.readLine();
    			}
    						// 最終出力(文字)
    			if (out_m >= 0) {
    				n_tri--;
    				k1    = out_m;
    				out_m = 0;
    				System.out.println("***試行回数 " + n_tri + " 距離 " + (-range));
    				Output(out_lvl);
    				out_m = k1;
    			}
    		}
    					// ワンステップづつ実行する場合
    		else {
    						// 初期設定
    			range = kyori(n_city, seq, rg);
    						// 初期状態の出力(図)
    			wn.Draw();
    			System.out.println("   図を確認したらreturnキーを押してください");
    			in.readLine();
    						// 初期状態の出力(文字)
    			if (out_m >= 0 && Math.abs(out_lvl) > 0) {
    				System.out.println("***試行回数 " + n_tri + " 距離 " + (-range));
    				Output(out_lvl);
    			}
    						// マウスによる実行
    			System.out.print("\n終了したらreturnキーを押してください\n");
    			in.readLine();
    						// 最終出力(文字)
    			if (out_m >= 0) {
    				k1    = out_m;
    				out_m = 0;
    				System.out.println("***試行回数 " + n_tri + " 距離 " + (-range));
    				Output(out_lvl);
    				out_m = k1;
    			}
    		}
    
    		return n_tri;
    	}
    
    	/*******************************/
    	/* 出力                        */
    	/*      sw : >= 0 : 出力先未定 */
    	/*           < 0 : ファイル    */
    	/*******************************/
    	void Output(int sw) throws IOException, FileNotFoundException
    	{
    		int i1, k = 0, n, pr;
    		String now;
    		PrintStream out = null;
    		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    
    		if (sw >= 0) {
    			System.out.print("   出力先は(0:出力なし,n:画面にn個づつ,-1:ファイル)? ");
    			pr = Integer.parseInt(in.readLine());
    		}
    		else
    			pr = -1;
    
    		if (pr != 0) {
    
    			if (pr > 0)
    				out = System.out;
    			else {
    				Date newtime = new Date();   // 現在時刻の獲得
    				now = newtime.toString();    // 文字列への変換
    				out = new PrintStream(new FileOutputStream(o_file, true));
    				out.println("***試行回数 " + n_tri + " 距離 " + (-range) + " 時間 " + now);
    			}
    
    			if (out_m == 0) {
    				for (i1 = 0; i1 < n_city; i1++) {
    					n = seq[i1];
    					out.println("  " + n + " " + city[n][0] + " " + city[n][1]);
    					if (pr > 0) {
    						k++;
    						if (k == pr) {
    							in.readLine();
    							k = 0;
    						}
    					}
    				}
    			}
    
    			if (pr <= 0)
    				out.close();
    		}
    	}
    
    	/**************************************/
    	/* エッジの入れ替え                   */
    	/*      return : =0 : 改善がなかった  */
    	/*               =1 : 改善があった    */
    	/**************************************/
    	int Change()
    	{
    		int ch = 0, i1, i2, i3, i4, k, k1, k2, max, n1, n2, n3, nn, r, sw = 0;
    
    		max = range;
    
    		n3  = (int)(rn.nextDouble() * (n_city - 2));
    		if (n3 > n_city-3)
    			n3 = n_city - 3;
                             // 2近傍
    		for (i1 = 0; i1 <= n_city-3 && ch == 0; i1++) {
    
    			if (n3 == 0)
    				n1 = n_city - 2;
    			else
    				n1 = n_city - 1;
    
    			for (i2 = n3+2; i2 <= n1 && ch == 0; i2++) {
                                  // 枝の場所((n3,n3+1), (k1,k2))
    				k1 = i2;
    				if (i2 == n_city-1)
    					k2 = 0;
    				else
    					k2 = i2 + 1;
                                  // 枝の入れ替え
    				seq_w1[0] = seq[n3];
    				k         = 1;
    				for (i3 = k1; i3 >= n3+1; i3--) {
    					seq_w1[k] = seq[i3];
    					k++;
    				}
    
    				nn = k2;
    				while (nn != n3) {
    					seq_w1[k] = seq[nn];
    					k++;
    					nn++;
    					if (nn > n_city-1)
    						nn = 0;
    				}
                                  // 評価
    				r = kyori(n_city, seq_w1, rg);
    
    				if (r > max) {
    					max = r;
    					sw  = 1;
    					for (i3 = 0; i3 < n_city; i3++)
    						seq_w2[i3] = seq_w1[i3];
    					if (sel > 0)
    						ch = 1;
    					n_eg  = 2;
    					eg[0] = seq[n3];
    					eg[1] = seq[n3+1];
    					eg[2] = seq[k1];
    					eg[3] = seq[k2];
    				}
    			}
    
    			n3++;
    			if (n3 > n_city-3)
    				n3 = 0;
    		}
                             // 3近傍
    		if (neib == 3 && ch == 0) {
    
    			for (i1 = 0; i1 <= n_city-3 && ch == 0; i1++) {
    
    				n1 = n_city - 2;
    				n2 = n_city - 1;
    
    				for (i2 = n3+1; i2 <= n1 && ch == 0; i2++) {
    
    					for (i3 = i2+1; i3 <= n2 && ch == 0; i3++) {
                                  // 枝の場所((n3,n3+1), (i2,i2+1), (k1,k2))
    						k1 = i3;
    						if (i3 == n_city-1)
    							k2 = 0;
    						else
    							k2 = i3 + 1;
                                  // 枝の入れ替えと評価
                                       // 入れ替え(その1)
    						seq_w1[0] = seq[n3];
    						k         = 1;
    						for (i4 = i2; i4 >= n3+1; i4--) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						for (i4 = k1; i4 >= i2+1; i4--) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						nn = k2;
    						while (nn != n3) {
    							seq_w1[k] = seq[nn];
    							k++;
    							nn++;
    							if (nn > n_city-1)
    								nn = 0;
    						}
                                       // 評価(その1)
    						r = kyori(n_city, seq_w1, rg);
    
    						if (r > max) {
    							max = r;
    							sw  = 1;
    							for (i3 = 0; i3 < n_city; i3++)
    								seq_w2[i3] = seq_w1[i3];
    							if (sel > 0)
    								ch = 1;
    							n_eg  = 3;
    							eg[0] = seq[n3];
    							eg[1] = seq[n3+1];
    							eg[2] = seq[i2];
    							eg[3] = seq[i2+1];
    							eg[4] = seq[k1];
    							eg[5] = seq[k2];
    						}
                                       // 入れ替え(その2)
    						seq_w1[0] = seq[n3];
    						k         = 1;
    						for (i4 = k1; i4 >= i2+1; i4--) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						for (i4 = n3+1; i4 <= i2; i4++) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						nn = k2;
    						while (nn != n3) {
    							seq_w1[k] = seq[nn];
    							k++;
    							nn++;
    							if (nn > n_city-1)
    								nn = 0;
    						}
                                       // 評価(その2)
    						r = kyori(n_city, seq_w1, rg);
    
    						if (r > max) {
    							max = r;
    							sw  = 1;
    							for (i3 = 0; i3 < n_city; i3++)
    								seq_w2[i3] = seq_w1[i3];
    							if (sel > 0)
    								ch = 1;
    							n_eg  = 3;
    							eg[0] = seq[n3];
    							eg[1] = seq[n3+1];
    							eg[2] = seq[i2];
    							eg[3] = seq[i2+1];
    							eg[4] = seq[k1];
    							eg[5] = seq[k2];
    						}
                                       // 入れ替え(その3)
    						seq_w1[0] = seq[n3];
    						k         = 1;
    						for (i4 = i2+1; i4 <= k1; i4++) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						for (i4 = i2; i4 >= n3+1; i4--) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						nn = k2;
    						while (nn != n3) {
    							seq_w1[k] = seq[nn];
    							k++;
    							nn++;
    							if (nn > n_city-1)
    								nn = 0;
    						}
                                       // 評価(その3)
    						r = kyori(n_city, seq_w1, rg);
    
    						if (r > max) {
    							max = r;
    							sw  = 1;
    							for (i3 = 0; i3 < n_city; i3++)
    								seq_w2[i3] = seq_w1[i3];
    							if (sel > 0)
    								ch = 1;
    							n_eg  = 3;
    							eg[0] = seq[n3];
    							eg[1] = seq[n3+1];
    							eg[2] = seq[i2];
    							eg[3] = seq[i2+1];
    							eg[4] = seq[k1];
    							eg[5] = seq[k2];
    						}
                                       // 入れ替え(その4)
    						seq_w1[0] = seq[n3];
    						k         = 1;
    						for (i4 = i2+1; i4 <= k1; i4++) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						for (i4 = n3+1; i4 <= i2; i4++) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						nn = k2;
    						while (nn != n3) {
    							seq_w1[k] = seq[nn];
    							k++;
    							nn++;
    							if (nn > n_city-1)
    								nn = 0;
    						}
                                       // 評価(その4)
    						r = kyori(n_city, seq_w1, rg);
    
    						if (r > max) {
    							max = r;
    							sw  = 1;
    							for (i3 = 0; i3 < n_city; i3++)
    								seq_w2[i3] = seq_w1[i3];
    							if (sel > 0)
    								ch = 1;
    							n_eg  = 3;
    							eg[0] = seq[n3];
    							eg[1] = seq[n3+1];
    							eg[2] = seq[i2];
    							eg[3] = seq[i2+1];
    							eg[4] = seq[k1];
    							eg[5] = seq[k2];
    						}
    					}
    				}
    
    				n3++;
    				if (n3 > n_city-3)
    					n3 = 0;
    			}
    		}
                             // 設定
    		if (sw > 0) {
    			range = max;
    			for (i1 = 0; i1 < n_city; i1++)
    				seq[i1] = seq_w2[i1];
    		}
    
    		return sw;
    	}
    
    	/*********************************/
    	/* 距離の計算                    */
    	/*      n_c : 都市の数           */
    	/*      p : 都市番号             */
    	/*      rg : 都市間の距離        */
    	/*      return : 距離(負)      */
    	/*********************************/
    	static int kyori(int n_c, int [] p, int [][] rg)
    	{
    		int i1, n1, n2, range = 0;
    
    		n1 = p[0];
    
    		for (i1 = 1; i1 < n_c; i1++) {
    			n2     = p[i1];
    			range -= rg[n1][n2];
    			n1     = n2;
    		}
    
    		n2     = p[0];
    		range -= rg[n1][n2];
    
    		return range;
    	}
    }
    
    /**********************/
    /* クラスWin_itの定義 */
    /**********************/
    class Win_it extends Frame {
    
    	double ritu;   // 表示倍率
    	private int font;   // フォントサイズ
    	private int min_x, max_x, min_y, max_y;   // 都市の存在範囲
    	private int next, yoyu_x, yoyu_y;   // 表示位置
    	private Iteration it;
    
    	/***************************************/
    	/* コンストラクタ                      */
    	/*      it_i : Iterationのオブジェクト */
    	/*      font_i : フォントサイズ        */
    	/*      width,height : 表示範囲        */
    	/***************************************/
    	Win_it (Iteration it_i, int font_i, int width, int height)
    	{
    					// Frameクラスのコンストラクタの呼び出し
    		super("巡回セールスマン問題");
    					// 値の設定と領域の確保
    		double k1, k2;
    		int i1;
    
    		it      = it_i;
    		font    = font_i;
    		next    = 70;
    		yoyu_x  = 30;
    		yoyu_y  = 80;
    					// 描画領域の計算
    		min_x = it.city[0][0];
    		max_x = it.city[0][0];
    		min_y = it.city[0][1];
    		max_y = it.city[0][1];
    
    		for (i1 = 1; i1 < it.n_city; i1++) {
    			if (it.city[i1][0] < min_x)
    				min_x = it.city[i1][0];
    			else {
    				if (it.city[i1][0] > max_x)
    					max_x = it.city[i1][0];
    			}
    			if (it.city[i1][1] < min_y)
    				min_y = it.city[i1][1];
    			else {
    				if (it.city[i1][1] > max_y)
    					max_y = it.city[i1][1];
    			}
    		}
    
    		k1 = (double)(width - 2 * yoyu_x) / (max_x - min_x);
    		if (it.display == 3)
    			k2 = (double)(height - yoyu_y - next) / (max_y - min_y);
    		else
    			k2 = (double)(height - yoyu_y - yoyu_x) / (max_y - min_y);
    		ritu = (k1 < k2) ? k1 : k2;
    					// ボタンの設定とWindowサイズ
    		if (it.display == 3) {
    						// パネルクラスの定義
    			Panel pnl = new Panel();
    						// Next ボタンの設定
    			Button bt = new Button("Next");
    			bt.addMouseListener(new ClickMouse());
    			pnl.add(bt);
    			add("South", pnl);
    						// ウィンドウの構成要素をパック
    			pack();
    						// 指定された大きさにWindowサイズを変更
    			width  = 2 * yoyu_x + (int)(ritu * (max_x - min_x));
    			height = yoyu_y + next + (int)(ritu * (max_y - min_y));
    		}
    		else {
    						// 指定された大きさにWindowサイズを変更
    			width  = 2 * yoyu_x + (int)(ritu * (max_x - min_x));
    			height = yoyu_y + yoyu_x + (int)(ritu * (max_y - min_y));
    		}
    
    		setSize(width, height);
    					// ウィンドウを表示
    		setVisible(true);
    					// イベントアダプタ
    		addWindowListener(new WinEnd());
    	}
    
    	/************/
    	/* 描画指示 */
    	/************/
    	void Draw()
    	{
    		repaint();
    	}
    
    	/********/
    	/* 描画 */
    	/********/
    	public void paint (Graphics g)
    	{
    		int i1, k, n1, n2, size = 6, x1, x2, y1, y2;
    		Font f;
    						// 距離の表示
    		f = new Font("TimesRoman", Font.BOLD, 25);
    		g.setFont(f);
    		g.drawString("Length : "+Integer.toString(-it.range), yoyu_x, yoyu_y-30);
    						// 都市番号のフォントサイズ
    		if (font > 0) {
    			f = new Font("TimesRoman", Font.PLAIN, font);
    			g.setFont(f);
    		}
    					// 点と直線のプロット
    		k = size / 2;
    
    		for (i1 = 0; i1 < it.n_city; i1++) {
    
    			n2 = it.seq[i1];
    			x2 = yoyu_x + (int)(ritu * (it.city[n2][0] - min_x));
    			y2 = yoyu_y + (int)(ritu * (max_y - it.city[n2][1]));
    
    			g.fillOval(x2, y2, size, size);
    
    			if (font > 0)
    				g.drawString(Integer.toString(n2), x2+k, y2-k);
    
    			if (i1 > 0) {
    				n1 = it.seq[i1-1];
    				x1 = yoyu_x + (int)(ritu * (it.city[n1][0] - min_x));
    				y1 = yoyu_y + (int)(ritu * (max_y - it.city[n1][1]));
    				g.drawLine(x1+k, y1+k, x2+k, y2+k);
    				if (i1 == it.n_city-1) {
    					n1 = it.seq[0];
    					x1 = yoyu_x + (int)(ritu * (it.city[n1][0] - min_x));
    					y1 = yoyu_y + (int)(ritu * (max_y - it.city[n1][1]));
    					g.drawLine(x1+k, y1+k, x2+k, y2+k);
    				}
    			}
    		}
    					// 交換した元の枝を赤く描く
    		if (it.display == 3 && it.n_eg > 0) {
    			g.setColor(Color.red);
    			for (i1 = 0; i1 < it.n_eg; i1++ ) {
    				n1 = it.eg[2*i1];
    				x1 = yoyu_x + (int)(ritu * (it.city[n1][0] - min_x));
    				y1 = yoyu_y + (int)(ritu * (max_y - it.city[n1][1]));
    				n2 = it.eg[2*i1+1];
    				x2 = yoyu_x + (int)(ritu * (it.city[n2][0] - min_x));
    				y2 = yoyu_y + (int)(ritu * (max_y - it.city[n2][1]));
    				g.drawLine(x1+k, y1+k, x2+k, y2+k);
    			}
    		}
    	}
    
    	/**********************************/
    	/* nextボタンが押されたときの処理 */
    	/**********************************/
    	class ClickMouse extends MouseAdapter
    	{
    		/************************************/
    		/* マウスがクリックされたときの処理 */
    		/************************************/
    		public void mouseClicked(MouseEvent e)
    		{
    			int sw = it.Change();
    			if (sw > 0)
    				it.n_tri++;
    			else
    				it.n_eg = 0;
    			repaint();
    		}
    	}
    
    	/************/
    	/* 終了処理 */
    	/************/
    	class WinEnd extends WindowAdapter
    	{
    		public void windowClosing(WindowEvent e) {
    			System.exit(0);
    		}
    	}
    }
    
    /****************/
    /* main program */
    /****************/
    public class Test {
    
    	public static void main(String args[]) throws IOException, FileNotFoundException
    	{
    		int i1, n;
    		String i_file[];
    		Iteration it;
    		BufferedReader in = new BufferedReader(new FileReader(args[0]));
    						// 入力ミス
    		if (args.length == 0) {
    			System.out.print("***error  ファイル名を入力して下さい\n");
    			System.exit(1);
    		}
    						// 入力OK
    		else {
    							// 入力データファイル名の入力
    			n      = Integer.parseInt(in.readLine());
    			i_file = new String [n];
    
    			for (i1 = 0; i1 < n; i1++)
    				i_file[i1] = in.readLine();
    
    			in.close();
    							// 実行(乱数の初期値を変える)
    			for (i1 = 0; i1 < n; i1++) {
    				System.out.print("\n+++++ケース " + (i1+1) + "+++++\n");
    								// 入力と初期設定
    				it = new Iteration (1000 * i1 + 1234567, i_file[i1]);
    								// 最適化
    				it.Optimize();
    			}
    		}
    	}
    }
    
    //------------------------ケーススタディデータ(data_j.txt)------
    
    /*
    2
    data1_j.txt
    data2_j.txt
    */
    //---------------------データファイル(data1_j.txt)------------
    /*
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    図示(0:しない,1:結果,2:初期状態と結果,3:ステップ) 3
    都市番号 20 図の大きさ(幅,高さ) 1000 750
    -58 37
    55 -19
    6 -79
    27 -30
    44 -94
    33 -58
    -94 87
    -9 3
    33 69
    43 -57
    */
    
    //---------------------データファイル(data2_j.txt)------------
    /*
    都市の数 50 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    図示(0:しない,1:結果,2:初期状態と結果,3:ステップ) 1
    都市番号 20 図の大きさ(幅,高さ) 1000 750
    86 27
    82 16
    29 37
    27  1
    90 88
    40 92
    87 53
    24 99
    11 80
    61  8
    30 93
     4 81
    86 90
    84 52
    96 45
     4 34
    53  6
    45 12
    23 97
    61 46
    49 16
    82 74
    48 36
    13  5
    12  6
    33 26
     8 50
    98 98
    79 65
    36 56
    42 25
    52 12
    88 79
    27 51
    86 51
    14 35
    77 37
    44  0
    78 13
    21 55
    82 26
    25 88
    55  0
    10 59
    41 33
     7  4
    56 99
    19 34
    92 46
    27 35
    */
    			

  3. PHP

    <?php
    
    /****************************/
    /* 巡回セールスマン問題     */
    /*      反復改善法          */
    /*      coded by Y.Suganuma */
    /****************************/
    
    /*************************/
    /* クラスIterationの定義 */
    /*************************/
    class Iteration {
    	private $city;   //都市の位置データ
    	private $max_try;   // 最大試行回数
    	private $n_city;   // 都市の数
    	private $out_d;   // 表示間隔
    	private $rg;   // 都市間の距離
    	private $seq_w1;   // 都市を訪れる順序(ワーク)
    	private $seq_w2;   // 都市を訪れる順序(ワーク)
    	private $neib;   // 近傍(2 or 3)
    	private $out_lvl;   // 出力レベル
                            //   =0 : 最終出力だけ
                            //   n>0 : n回毎に出力(負の時はファイル)
    	private $out_m;   // 出力方法
                          //   =-1 : 出力しない
                          //   =0 : すべてを出力
                          //   =1 : 評価値だけを出力(最終結果だけはすべてを出力)
    	private $sel;   // エッジの選択方法
                        //   =0 : 最良のものを選択
                        //   =1 : 最初のものを選択
    	private $o_file;   // 出力ファイル名
    
    	public $seq;   // 都市を訪れる順序
    
    	/****************************/
    	/* コンストラクタ           */
    	/*      seed : 乱数の初期値 */
    	/*      name : ファイル名   */
    	/****************************/
    	function Iteration ($seed, $name)
    	{
    						// 乱数の初期設定
    		mt_srand($seed);
        					// ファイルのオープン
        	$in = fopen($name, "rb");
    		if ($in == NULL)
        		exit("***error  データファイル名が不適当\n");
    						// 基本データ
        	fscanf($in, "%*s %d %*s %d %*s %d %*s %d", $this->n_city, $this->max_try, $this->sel, $this->neib);
        	fscanf($in, "%*s %d %*s %d", $this->out_lvl, $this->out_m);
    		fscanf($in, "%*s %s %*s %d", $this->o_file, $this->out_d);
    						// 都市の位置データ
    		$this->city = array($this->n_city);
    		for ($i1 = 0; $i1 < $this->n_city; $i1++) {
    			$this->city[$i1] = array(2);
    			fscanf($in, "%d %d", $this->city[$i1][0], $this->city[$i1][1]);
    		}
    						// ファイルのクローズ
    		fclose($in);
    						// 距離テーブルの作成
    		$this->rg = array($this->n_city);
    	
    		for ($i1 = 0; $i1 < $this->n_city; $i1++) {
    			$this->rg[$i1] = array($this->n_city);
    			for ($i2 = $i1+1; $i2 < $this->n_city; $i2++) {
    				$x = $this->city[$i2][0] - $this->city[$i1][0];
    				$y = $this->city[$i2][1] - $this->city[$i1][1];
    				$this->rg[$i1][$i2] = round(sqrt($x * $x + $y * $y));
    			}
        	}
        
    		for ($i1 = 1; $i1 < $this->n_city; $i1++) {
        		for ($i2 = 0; $i2 < $i1; $i2++)
        			$this->rg[$i1][$i2] = $this->rg[$i2][$i1];
        	}
    						// 都市を訪れる順序(初期設定)
        	$this->seq    = array($this->n_city);
        	$this->seq_w1 = array($this->n_city);
    		$this->seq_w2 = array($this->n_city);
    	
    		for ($i1 = 0; $i1 < $this->n_city; $i1++) {
    			$sw = 0;
    			while ($sw == 0) {
    				$ct = intval((mt_rand() / mt_getrandmax()) * $this->n_city);
    				if ($ct >= $this->n_city)
    					$ct = $this->n_city - 1;
    				$this->seq[$i1] = $ct;
    				$sw             = 1;
    				for ($i2 = 0; $i2 < $i1 && $sw > 0; $i2++) {
    					if ($ct == $this->seq[$i2])
    						$sw = 0;
    				}
    			}
    		}
    	}
    	
    	/****************/
        /* 最適化の実行 */
        /****************/
    	function Optimize ()
        {
        					// 初期設定
    		$n_tri = 0;
        	$max   = kyori($this->n_city, $this->seq, $this->rg);
        
    		if ($this->out_m >= 0 && abs($this->out_lvl) > 0) {
    			printf("***試行回数 %d 距離 %d\n", $n_tri, -$max);
    			$this->Output($this->out_lvl, $n_tri, $max);
    		}
    						// 実行
    		$sw = 1;
    		for ($n_tri = 1; $n_tri <= $this->max_try && $sw > 0; $n_tri++) {
    							// 改善
    			$sw = $this->Change($max);
    							// 出力
    			if ($this->out_d > 0 && $n_tri%$this->out_d == 0)
    				printf("***試行回数 %d 距離 %d\n", $n_tri, -$max);
    	
    			if ($this->out_m >= 0 && abs($this->out_lvl) > 0) {
    				if ($n_tri%abs($this->out_lvl) == 0)
    					$this->Output($this->out_lvl, $n_tri, $max);
    			}
    		}
    						// 最終出力
        	if ($this->out_m >= 0) {
        		$n_tri--;
    			$k1           = $this->out_m;
        		$this->out_m = 0;
        		printf("***試行回数 %d 距離 %d\n", $n_tri, -$max);
        		$this->Output($this->out_lvl, $n_tri, $max);
    			$this->out_m = $k1;
        	}
        
    		return $n_tri;
    	}
    	
    	/*******************************/
    	/* 出力                        */
    	/*      sw : >=0 : 出力先未定  */
    	/*           < 0 : ファイル    */
    	/*      n_tri : 現在の試行回数 */
    	/*      r : 距離の負値         */
    	/*******************************/
    	function Output($sw, $n_tri, $r)
    	{
    		$k = 0;
    
    		if ($sw >= 0) {
    			printf("   出力先は(0:出力なし,n:画面にn個づつ,-1:ファイル)? ");
    			fscanf(STDIN, "%d", $pr);
    		}
    		else
    			$pr = -1;
    	
        	if ($pr != 0) {
        
    			if ($pr > 0) {
        			$out = STDOUT;
        			fgets(STDIN);
        		}
    			else {
    				$x   = getdate();
    				$now = $x["hours"]."時".$x["minutes"]."分".$x["seconds"]."秒";
    				$out = fopen($this->o_file, "ab");
    				fwrite($out, "***試行回数 ".$n_tri." 距離 ".(-$r)." 時間 ".$now."%s\n");
    			}
    	
    			if ($this->out_m == 0) {
    				for ($i1 = 0; $i1 < $this->n_city; $i1++) {
    					$n = $this->seq[$i1];
    					fwrite($out, "  ".$n." ".$this->city[$n][0]." ".$this->city[$n][1]."\n");
    					if ($pr > 0) {
    						$k++;
    						if ($k == $pr) {
    							fgets(STDIN);
    							$k = 0;
    						}
    					}
    				}
    			}
    	
    			if ($pr <= 0)
        			fclose($out);
        	}
    	}
        
        /**************************************/
        /* エッジの入れ替え                   */
    	/*      r_m : 距離の負値              */
        /*      return : =0 : 改善がなかった  */
        /*               =1 : 改善があった    */
    	/**************************************/
    	function Change(int &$r_m)
    	{
    		$ch  = 0;
    		$sw  = 0;
    		$max = $r_m;
    	
    		$n3  = intval((mt_rand() / mt_getrandmax()) * ($this->n_city - 2));
    		if ($n3 > $this->n_city-3)
    			$n3 = $this->n_city - 3;
    	                         // 2近傍
    		for ($i1 = 0; $i1 <= $this->n_city-3 && $ch == 0; $i1++) {
    	
    			if ($n3 == 0)
    				$n1 = $this->n_city - 2;
    			else
    				$n1 = $this->n_city - 1;
    	
    			for ($i2 = $n3+2; $i2 <= $n1 && $ch == 0; $i2++) {
                                      // 枝の場所((n3,n3+1), (k1,k2))
        			$k1 = $i2;
    				if ($i2 == $this->n_city-1)
        				$k2 = 0;
        			else
        				$k2 = $i2 + 1;
    	                              // 枝の入れ替え
        			$this->seq_w1[0] = $this->seq[$n3];
        			$k               = 1;
    				for ($i3 = $k1; $i3 >= $n3+1; $i3--) {
    					$this->seq_w1[$k] = $this->seq[$i3];
    					$k++;
    				}
    	
    				$nn = $k2;
    				while ($nn != $n3) {
    					$this->seq_w1[$k] = $this->seq[$nn];
    					$k++;
    					$nn++;
    					if ($nn > $this->n_city-1)
    						$nn = 0;
    				}
    	                              // 評価
    				$r = kyori($this->n_city, $this->seq_w1, $this->rg);
    	
    				if ($r > $max) {
    					$max = $r;
    					$sw  = 1;
        				for ($i3 = 0; $i3 < $this->n_city; $i3++)
        					$this->seq_w2[$i3] = $this->seq_w1[$i3];
    					if ($this->sel > 0)
        					$ch = 1;
        			}
        		}
    	
        		$n3++;
        		if ($n3 > $this->n_city-3)
    				$n3 = 0;
    		}
    	                         // 3近傍
    		if ($this->neib == 3 && $ch == 0) {
    	
    			for ($i1 = 0; $i1 <= $this->n_city-3 && $ch == 0; $i1++) {
    	
    				$n1 = $this->n_city - 2;
    				$n2 = $this->n_city - 1;
    	
    				for ($i2 = $n3+1; $i2 <= $n1 && $ch == 0; $i2++) {
    	
    					for ($i3 = $i2+1; $i3 <= $n2 && $ch == 0; $i3++) {
    	                              // 枝の場所((n3,n3+1), (i2,i2+1), (k1,k2))
    						$k1 = $i3;
    						if ($i3 == $this->n_city-1)
    							$k2 = 0;
    						else
    							$k2 = $i3 + 1;
                                      // 枝の入れ替えと評価
                                           // 入れ替え(その1)
    						$this->seq_w1[0] = $this->seq[$n3];
        					$k               = 1;
        					for ($i4 = $i2; $i4 >= $n3+1; $i4--) {
        						$this->seq_w1[$k] = $this->seq[$i4];
    							$k++;
        					}
        
    						for ($i4 = $k1; $i4 >= $i2+1; $i4--) {
    							$this->seq_w1[$k] = $this->seq[$i4];
    							$k++;
    						}
    	
    						$nn = $k2;
    						while ($nn != $n3) {
    							$this->seq_w1[$k] = $this->seq[$nn];
    							$k++;
    							$nn++;
    							if ($nn > $this->n_city-1)
    								$nn = 0;
    						}
    	                                   // 評価(その1)
    						$r = kyori($this->n_city, $this->seq_w1, $this->rg);
    	
    						if ($r > $max) {
    							$max = $r;
    							$sw  = 1;
        						for ($i3 = 0; $i3 < $this->n_city; $i3++)
        							$this->seq_w2[$i3] = $this->seq_w1[$i3];
    							if ($this->sel > 0)
        							$ch = 1;
        					}
                                           // 入れ替え(その2)
    						$this->seq_w1[0] = $this->seq[$n3];
        					$k               = 1;
        					for ($i4 = $k1; $i4 >= $i2+1; $i4--) {
    							$this->seq_w1[$k] = $this->seq[$i4];
    							$k++;
    						}
    	
    						for ($i4 = $n3+1; $i4 <= $i2; $i4++) {
    							$this->seq_w1[$k] = $this->seq[$i4];
    							$k++;
    						}
    	
    						$nn = $k2;
    						while ($nn != $n3) {
    							$this->seq_w1[$k] = $this->seq[$nn];
    							$k++;
    							$nn++;
    							if ($nn > $this->n_city-1)
    								$nn = 0;
    						}
    	                                   // 評価(その2)
    						$r = kyori($this->n_city, $this->seq_w1, $this->rg);
        
        					if ($r > $max) {
    							$max = $r;
        						$sw  = 1;
        						for ($i3 = 0; $i3 < $this->n_city; $i3++)
        							$this->seq_w2[$i3] = $this->seq_w1[$i3];
    							if ($this->sel > 0)
        							$ch = 1;
        					}
    	                                   // 入れ替え(その3)
    						$this->seq_w1[0] = $this->seq[$n3];
    						$k               = 1;
    						for ($i4 = $i2+1; $i4 <= $k1; $i4++) {
    							$this->seq_w1[$k] = $this->seq[$i4];
    							$k++;
    						}
    	
    						for ($i4 = $i2; $i4 >= $n3+1; $i4--) {
    							$this->seq_w1[$k] = $this->seq[$i4];
    							$k++;
    						}
    	
    						$nn = $k2;
    						while ($nn != $n3) {
    							$this->seq_w1[$k] = $this->seq[$nn];
    							$k++;
    							$nn++;
    							if ($nn > $this->n_city-1)
        							$nn = 0;
        					}
    	                                   // 評価(その3)
        					$r = kyori($this->n_city, $this->seq_w1, $this->rg);
        
        					if ($r > $max) {
    							$max = $r;
        						$sw  = 1;
        						for ($i3 = 0; $i3 < $this->n_city; $i3++)
    								$this->seq_w2[$i3] = $this->seq_w1[$i3];
    							if ($this->sel > 0)
    								$ch = 1;
    						}
    	                                   // 入れ替え(その4)
    						$this->seq_w1[0] = $this->seq[$n3];
    						$k               = 1;
    						for ($i4 = $i2+1; $i4 <= $k1; $i4++) {
    							$this->seq_w1[$k] = $this->seq[$i4];
    							$k++;
    						}
    	
    						for ($i4 = $n3+1; $i4 <= $i2; $i4++) {
    							$this->seq_w1[$k] = $this->seq[$i4];
    							$k++;
    						}
    	
    						$nn = $k2;
    						while ($nn != $n3) {
        						$this->seq_w1[$k] = $this->seq[$nn];
        						$k++;
    							$nn++;
        						if ($nn > $this->n_city-1)
        							$nn = 0;
        					}
    	                                   // 評価(その4)
        					$r = kyori($this->n_city, $this->seq_w1, $this->rg);
        
    						if ($r > $max) {
    							$max = $r;
    							$sw  = 1;
    							for ($i3 = 0; $i3 < $this->n_city; $i3++)
    								$this->seq_w2[$i3] = $this->seq_w1[$i3];
    							if ($this->sel > 0)
    								$ch = 1;
    						}
    					}
    				}
    	
    				$n3++;
    				if ($n3 > $this->n_city-3)
    					$n3 = 0;
    			}
    		}
    	                         // 設定
    		if ($sw > 0) {
    			$r_m = $max;
        		for ($i1 = 0; $i1 < $this->n_city; $i1++)
        			$this->seq[$i1] = $this->seq_w2[$i1];
    		}
        
        	return $sw;
        }
    }
        
    /*********************************/
    /* 距離の計算                    */
    /*      n_c : 都市の数           */
    /*      p : 都市番号             */
    /*      rg : 都市間の距離        */
    /*      return : 距離(負)      */
    /*********************************/
    function kyori($n_c, $p, $rg)
    {
    	$range = 0;
    	$n1    = $p[0];
    
    	for ($i1 = 1; $i1 < $n_c; $i1++) {
    		$n2     = $p[$i1];
    		$range -= $rg[$n1][$n2];
    		$n1     = $n2;
    	}
    
    	$n2     = $p[0];
    	$range -= $rg[$n1][$n2];
    
    	return $range;
    }
    
    /****************/
    /* main program */
    /****************/
    					// 入力ミス
    	if (count($argv) <= 1)
    		exit("***error  ファイル名を入力して下さい\n");
    					// 入力OK
    	else {
    						// ファイルのオープン
    		$in = fopen($argv[1], "rb");
    		if ($in == NULL)
    			exit("***error  ファイル名が不適当です\n");
    						// 入力データファイル名の入力
    		fscanf($in, "%d", $n);
    
    		$seed   = array($n);
    		$i_file = array($n);
    
    		for ($i1 = 0; $i1 < $n; $i1++) {
    			fscanf($in, "%s", $i_file[$i1]);
    			$seed[$i1] = 1000 * $i1 + 1234567;
    		}
    
    		fclose($in);
    						// 実行(乱数の初期値を変える)
    		for ($i1 = 0; $i1 < $n; $i1++) {
    			printf("\n+++++ケース %d+++++\n", $i1+1);
    							// 入力と初期設定
    			$it = new Iteration($seed[$i1], $i_file[$i1]);
    							// 最適化
    			$it->Optimize();
    		}
    	}
    
    //------------------------ケーススタディデータ(data.txt)------
    /*
    3
    data1.txt
    data1.txt
    data2.txt
    */
    //---------------------データファイル(data1.txt)------------
    /*
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    -58 37
    55 -19
    6 -79
    27 -30
    44 -94
    33 -58
    -94 87
    -9 3
    33 69
    43 -57
    */
    
    //---------------------データファイル(data2.txt)------------
    /*
    都市の数 50 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    86 27
    82 16
    29 37
    27  1
    90 88
    40 92
    87 53
    24 99
    11 80
    61  8
    30 93
     4 81
    86 90
    84 52
    96 45
     4 34
    53  6
    45 12
    23 97
    61 46
    49 16
    82 74
    48 36
    13  5
    12  6
    33 26
     8 50
    98 98
    79 65
    36 56
    42 25
    52 12
    88 79
    27 51
    86 51
    14 35
    77 37
    44  0
    78 13
    21 55
    82 26
    25 88
    55  0
    10 59
    41 33
     7  4
    56 99
    19 34
    92 46
    27 35
    */
    
    ?>
    			

  4. Ruby

    ####################################
    # 巡回セールスマン問題(反復改善法)
    #      coded by Y.Suganuma
    ####################################
    
    #################################
    # 距離の計算
    #      n_c : 都市の数
    #      p : 都市番号
    #      rg : 都市間の距離
    #      return : 距離
    #################################
    
    def kyori(n_c, p, rg)
    
    	r  = 0.0
    	n1 = p[0]
    
    	for i1 in 1 ... n_c
    		n2  = p[i1]
    		r  -= rg[n1][n2]
    		n1  = n2
    	end
    
    	n2  = p[0]
    	r  -= rg[n1][n2]
    
    	return r
    end
    
    #########################
    # クラスIterationの定義
    #########################
    
    class Iteration
    
    	############################
    	# コンストラクタ
    	#      name ファイル名
    	############################
    
    	def initialize(name)
    						# ファイルのオープン
    		inn = open(name, "r")
    						# 基本データ
    		s         = inn.gets().split(" ")
    		@_n_city  = Integer(s[1])   # 都市の数
    		@_max_try = Integer(s[3])   # 最大試行回数
    		@_sel     = Integer(s[5])   # エッジの選択方法
    		                            #   =0 最良のものを選択
    		                            #   =1 最初のものを選択
    		@_neib    = Integer(s[7])   # 近傍(2 or 3)
    		s         = inn.gets().split(" ")
    		@_out_lvl = Integer(s[1])   # 出力レベル
    		                            #   =0 最終出力だけ
    		                            #   n>0 n回毎に出力(負の時はファイル)
    		@_out_m   = Integer(s[3])   # 出力方法
    		                            #   =-1 出力しない
    		                            #   =0 すべてを出力
    		                            #   =1 評価値だけを出力(最終結果だけはすべてを出力)
    		s         = inn.gets().split(" ")
    		@_o_file  = s[1]   # 出力ファイル名
    		@_out_d   = Integer(s[3])   # 表示間隔
    						# 都市の位置データ
    		@_city    = Array.new(@_n_city)
    		for i1 in 0 ... @_n_city
    			@_city[i1]    = Array.new(2)
    			s             = inn.gets().split(" ")
    			@_city[i1][0] = Integer(s[0])
    			@_city[i1][1] = Integer(s[1])
    		end
    						# ファイルのクローズ
    		inn.close()
    						# 距離テーブルの作成
    		@_rg = Array.new(@_n_city)   # 都市間の距離
    		for i1 in 0 ... @_n_city
    			@_rg[i1] = Array.new(@_n_city)
    		end
    
    		for i1 in 0 ... @_n_city
    			for i2 in i1+1 ... @_n_city
    				x            = @_city[i2][0] - @_city[i1][0]
    				y            = @_city[i2][1] - @_city[i1][1]
    				@_rg[i1][i2] = (Math.sqrt(x * x + y * y)).round()
    			end
    		end
    	
    		for i1 in 0 ... @_n_city
    			for i2 in 0 ... i1
    				@_rg[i1][i2] = @_rg[i2][i1]
    			end
    		end
    						# 都市を訪れる順序(初期設定)
    		@_seq    = Array.new(@_n_city)   # 都市を訪れる順序
    		@_seq_w1 = Array.new(@_n_city)   # 都市を訪れる順序(ワーク)
    		@_seq_w2 = Array.new(@_n_city)   # 都市を訪れる順序(ワーク)
    	
    		for i1 in 0 ... @_n_city
    			sw = 0
    			while sw == 0
    				ct = Integer(rand(0) * @_n_city)
    				if ct >= @_n_city
    					ct = @_n_city - 1
    				end
    				@_seq[i1] = ct
    				sw        = 1
    				for i2 in 0 ... i1
    					if ct == @_seq[i2]
    						sw = 0
    						break
    					end
    				end
    			end
    		end
    	end
    
    	#################
    	# 最適化の実行
    	#################
    	
    	def Optimize()
    	
    						# 初期設定
    		n_tri  = 0
    		max    = Array.new(1)
    		max[0] = kyori(@_n_city, @_seq, @_rg)
    	
    		if @_out_m >= 0 and @_out_lvl.abs() > 0
    			print("***試行回数 " + String(n_tri) + " 距離 " + String(-max[0]) + "\n")
    			Output(@_out_lvl, n_tri, max[0])
    		end
    						# 実行
    		sw = 1
    		for n_tri in 1 ... @_max_try+1
    							# 改善
    			sw = Change(max)
    							# 出力
    			if @_out_d > 0 and n_tri%@_out_d == 0
    				print("***試行回数 " + String(n_tri) + " 距離 " + String(-max[0]) + "\n")
    			end
    	
    			if @_out_m >= 0 and @_out_lvl.abs() > 0
    				if n_tri%@_out_lvl.abs() == 0
    					Output(@_out_lvl, n_tri, max[0])
    				end
    			end
    			if sw <= 0
    				break
    			end
    		end
    						# 最終出力
    		if @_out_m >= 0
    			n_tri   -= 1
    			k1       = @_out_m
    			@_out_m  = 0
    			print("***試行回数 " + String(n_tri) + " 距離 " + String(-max[0]) + "\n")
    			Output(@_out_lvl, n_tri, max[0])
    			@_out_m = k1
    		end
    	
    		return n_tri
    	end
    	
    	###############################
    	# 出力
    	#      sw >= 0 出力先未定
    	#           < 0 ファイル
    	#      n_tri 現在の試行回数
    	#      r 距離の負値
    	###############################
    
    	def Output(sw, n_tri, r)
    	
    		k  = 0
    		pr = -1
    
    		if sw >= 0
    			print("   出力先は(0:出力なし,n:画面にn個づつ,-1:ファイル)? ")
    			pr = Integer($stdin.gets())
    		end
    	
    		if pr != 0
    	
    			if pr > 0
    				out = $stdout
    				$stdin.gets()
    			else
    				now = String(Time.now)
    				out = open(@_o_file, "a")
    				out.print("***試行回数 " + String(n_tri) + " 距離 " + String(-r) + " 時間 " + now + "\n")
    			end
    	
    			if @_out_m == 0
    				for i1 in 0 ... @_n_city
    					n = @_seq[i1]
    					out.print("  " + String(n) + " " + String(@_city[n][0]) + " " + String(@_city[n][1]) + "\n")
    					if pr > 0
    						k += 1
    						if k == pr
    							$stdin.gets()
    							k = 0
    						end
    					end
    				end
    			end
    	
    			if pr <= 0
    				out.close()
    			end
    		end
    	end
    	
    	######################################
    	# エッジの入れ替え
    	#      r_m 距離の負値
    	#      return =0 改善がなかった
    	#               =1 改善があった
    	######################################
    
    	def Change(r_m)
    	
    		ch  = 0
    		sw  = 0
    		max = r_m[0]
    	
    		n3  = Integer(rand(0) * (@_n_city - 2))
    		if n3 > @_n_city-3
    			n3 = @_n_city - 3
    		end
    							# 2近傍
    		i1 = 0
    		while i1 <= @_n_city-3 and ch == 0
    	
    			n1 = @_n_city - 1
    			if n3 == 0
    				n1 = @_n_city - 2
    			end
    	
    			i2 = n3 + 2
    			while i2 <= n1 and ch == 0
    								# 枝の場所((n3,n3+1), (k1,k2))
    				k1 = i2
    				k2 = i2 + 1
    				if i2 == @_n_city-1
    					k2 = 0
    				end
    								# 枝の入れ替え
    				@_seq_w1[0] = @_seq[n3]
    				k           = 1
    				i3          = k1
    				while i3 > n3
    					@_seq_w1[k] = @_seq[i3]
    					k  += 1
    					i3 -= 1
    				end
    	
    				nn = k2
    				while nn != n3
    					@_seq_w1[k] = @_seq[nn]
    					k  += 1
    					nn += 1
    					if nn > @_n_city-1
    						nn = 0
    					end
    				end
    								# 評価
    				r = kyori(@_n_city, @_seq_w1, @_rg)
    	
    				if r > max
    					max = r
    					sw  = 1
    					for i3 in 0 ... @_n_city
    						@_seq_w2[i3] = @_seq_w1[i3]
    					end
    					if @_sel > 0
    						ch = 1
    					end
    				end
    				i2 += 1
    			end
    	
    			n3 += 1
    			if n3 > @_n_city-3
    				n3 = 0
    			end
    			i1 += 1
    		end
    							# 3近傍
    		if @_neib == 3 and ch == 0
    	
    			i1 = 0
    			while i1 <= @_n_city-3 and ch == 0
    	
    				n1 = @_n_city - 2
    				n2 = @_n_city - 1
    	
    				i2 = n3 + 1
    				while i2 <= n1 and ch == 0
    	
    					i3 = i2 + 1
    					while i3 <= n2 and ch == 0
    								# 枝の場所((n3,n3+1), (i2,i2+1), (k1,k2))
    						k1 = i3
    						k2 = i3 + 1
    						if i3 == @_n_city-1
    							k2 = 0
    						end
    								# 枝の入れ替えと評価
    									# 入れ替え(その1)
    						@_seq_w1[0] = @_seq[n3]
    						k           = 1
    						i4          = i2
    						while i4 > n3
    							@_seq_w1[k] = @_seq[i4]
    							k  += 1
    							i4 -= 1
    						end
    	
    						i4 = k1
    						while i4 > i2
    							@_seq_w1[k] = @_seq[i4]
    							k  += 1
    							i4 -= 1
    						end
    	
    						nn = k2
    						while nn != n3
    							@_seq_w1[k] = @_seq[nn]
    							k  += 1
    							nn += 1
    							if nn > @_n_city-1
    								nn = 0
    							end
    						end
    									# 評価(その1)
    						r = kyori(@_n_city, @_seq_w1, @_rg)
    	
    						if r > max
    							max = r
    							sw  = 1
    							for i3 in 0 ... @_n_city
    								@_seq_w2[i3] = @_seq_w1[i3]
    							end
    							if @_sel > 0
    								ch = 1
    							end
    						end
    									# 入れ替え(その2)
    						@_seq_w1[0] = @_seq[n3]
    						k              = 1
    						i4             = k1
    						while i4 > i2
    							@_seq_w1[k] = @_seq[i4]
    							k  += 1
    							i4 -= 1
    						end
    	
    						for i4 in n3+1 ... i2+1
    							@_seq_w1[k] = @_seq[i4]
    							k += 1
    						end
    	
    						nn = k2
    						while nn != n3
    							@_seq_w1[k] = @_seq[nn]
    							k  += 1
    							nn += 1
    							if nn > @_n_city-1
    								nn = 0
    							end
    						end
    									# 評価(その2)
    						r = kyori(@_n_city, @_seq_w1, @_rg)
    	
    						if r > max
    							max = r
    							sw  = 1
    							for i3 in 0 ... @_n_city
    								@_seq_w2[i3] = @_seq_w1[i3]
    							end
    							if @_sel > 0
    								ch = 1
    							end
    						end
    									# 入れ替え(その3)
    						@_seq_w1[0] = @_seq[n3]
    						k              = 1
    						for i4 in i2+1 ... k1+1
    							@_seq_w1[k] = @_seq[i4]
    							k += 1
    						end
    	
    						i4 = i2
    						while i4 >n3
    							@_seq_w1[k] = @_seq[i4]
    							k  += 1
    							i4 -= 1
    						end
    	
    						nn = k2
    						while nn != n3
    							@_seq_w1[k] = @_seq[nn]
    							k  += 1
    							nn += 1
    							if nn > @_n_city-1
    								nn = 0
    							end
    						end
    									# 評価(その3)
    						r = kyori(@_n_city, @_seq_w1, @_rg)
    	
    						if r > max
    							max = r
    							sw  = 1
    							for i3 in 0 ... @_n_city
    								@_seq_w2[i3] = @_seq_w1[i3]
    							end
    							if @_sel > 0
    								ch = 1
    							end
    						end
    									# 入れ替え(その4)
    						@_seq_w1[0] = @_seq[n3]
    						k           = 1
    						for i4 in i2+1 ... k1+1
    							@_seq_w1[k] = @_seq[i4]
    							k += 1
    						end
    	
    						for i4 in n3+1 ... i2+1
    							@_seq_w1[k] = @_seq[i4]
    							k += 1
    						end
    	
    						nn = k2
    						while nn != n3
    							@_seq_w1[k] = @_seq[nn]
    							k  += 1
    							nn += 1
    							if nn > @_n_city-1
    								nn = 0
    							end
    						end
    									# 評価(その4)
    						r = kyori(@_n_city, @_seq_w1, @_rg)
    	
    						if r > max
    							max = r
    							sw  = 1
    							for i3 in 0 ... @_n_city
    								@_seq_w2[i3] = @_seq_w1[i3]
    							end
    							if @_sel > 0
    								ch = 1
    							end
    						end
    						i3 += 1
    					end
    					i2 += 1
    				end
    	
    				n3 += 1
    				if n3 > @_n_city-3
    					n3 = 0
    				end
    				i1 += 1
    			end
    		end
    							# 設定
    		if sw > 0
    			r_m[0] = max
    			for i1 in 0 ... @_n_city
    				@_seq[i1] = @_seq_w2[i1]
    			end
    		end
    	
    		return sw
    	end
    end
    
    				# 入力ミス
    if ARGV[0] == nil
    	print("***error  ファイル名を入力して下さい\n")
    			# 入力OK
    else
    					# データの数と入力データファイル名の入力
    	line   = gets()
    	n      = Integer(line)   # データの数
    	i_file = Array.new(n)
    
    	for i1 in 0 ... n
    		line       = gets()
    		a          = line.split(" ")
    		i_file[i1] = a[0]
    	end
    					# 実行
    	for i1 in 0 ... n
    		print("\n+++++ケース " + String(i1+1) + "+++++\n")
    		srand(1000 * i1 + 1234567);
    						# 入力と初期設定
    		it = Iteration.new(i_file[i1])
    						# 最適化
    		it.Optimize()
    	end
    end
    
    =begin
    ------------------ケーススタディデータ(data.txt)------
    3
    data1.txt
    data1.txt
    data2.txt
    
    ------------------データファイル(data1.txt)------------
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    -58 37
    55 -19
    6 -79
    27 -30
    44 -94
    33 -58
    -94 87
    -9 3
    33 69
    43 -57
    
    ------------------データファイル(data2.txt)------------
    都市の数 50 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    86 27
    82 16
    29 37
    27  1
    90 88
    40 92
    87 53
    24 99
    11 80
    61  8
    30 93
     4 81
    86 90
    84 52
    96 45
     4 34
    53  6
    45 12
    23 97
    61 46
    49 16
    82 74
    48 36
    13  5
    12  6
    33 26
     8 50
    98 98
    79 65
    36 56
    42 25
    52 12
    88 79
    27 51
    86 51
    14 35
    77 37
    44  0
    78 13
    21 55
    82 26
    25 88
    55  0
    10 59
    41 33
     7  4
    56 99
    19 34
    92 46
    27 35
    =end
    			

  5. Python

    # -*- coding: UTF-8 -*-
    import numpy as np
    import sys
    from math import *
    from random import *
    from datetime import *
    
    ##########################
    # 距離の計算
    #      n_c : 都市の数
    #      p : 都市番号
    #      rg : 都市間の距離
    #      return : 距離(負)
    ##########################
    
    def kyori(n_c, p, rg) :
    	
    	r  = 0
    	n1 = p[0]
    	
    	for i1 in range(1, n_c) :
    		n2  = p[i1]
    		r  -= rg[n1][n2]
    		n1  = n2
    	
    	n2  = p[0]
    	r  -= rg[n1][n2]
    	
    	return r
    	
    #########################
    # クラスIterationの定義
    #########################
    
    class Iteration :
    
    	############################
    	# コンストラクタ
    	#      name : ファイル名
    	############################
    
    	def __init__(self, name) :
    						# ファイルのオープン
    		inn = open(name, "r")
    						# 基本データ
    		s            = inn.readline().split()
    		self.n_city  = int(s[1])   # 都市の数
    		self.max_try = int(s[3])   # 最大試行回数
    		self.sel     = int(s[5])   # エッジの選択方法
    		                           #   =0 : 最良のものを選択
    		                           #   =1 : 最初のものを選択
    		self.neib    = int(s[7])   # 近傍(2 or 3)
    		s            = inn.readline().split()
    		self.out_lvl = int(s[1])   # 出力レベル
    		                           #   =0 : 最終出力だけ
    		                           #   n>0 : n回毎に出力(負の時はファイル)
    		self.out_m   = int(s[3])   # 出力方法
    		                           #   =-1 : 出力しない
    		                           #   =0 : すべてを出力
    		                           #   =1 : 評価値だけを出力(最終結果だけはすべてを出力)
    		s            = inn.readline().split()
    		self.o_file  = s[1]   # 出力ファイル名
    		self.out_d   = int(s[3])   # 表示間隔
    						# 都市の位置データ
    		self.city    = np.empty((self.n_city, 2), np.int)
    		for i1 in range(0, self.n_city) :
    			s                = inn.readline().split()
    			self.city[i1][0] = int(s[0])
    			self.city[i1][1] = int(s[1])
    						# ファイルのクローズ
    		inn.close()
    						# 距離テーブルの作成
    		self.rg = np.empty((self.n_city, self.n_city), np.int)   # 都市間の距離
    
    		for i1 in range(0, self.n_city) :
    			for i2 in range(i1+1, self.n_city) :
    				x               = self.city[i2][0] - self.city[i1][0]
    				y               = self.city[i2][1] - self.city[i1][1]
    				self.rg[i1][i2] = int(sqrt(x * x + y * y) + 0.5)
    	
    		for i1 in range(0, self.n_city) :
    			for i2 in range(0, i1) :
    				self.rg[i1][i2] = self.rg[i2][i1]
    						# 都市を訪れる順序(初期設定)
    		self.seq    = np.empty(self.n_city, np.int)   # 都市を訪れる順序
    		self.seq_w1 = np.empty(self.n_city, np.int)   # 都市を訪れる順序(ワーク)
    		self.seq_w2 = np.empty(self.n_city, np.int)   # 都市を訪れる順序(ワーク)
    	
    		for i1 in range(0, self.n_city) :
    			sw = 0
    			while sw == 0 :
    				ct = int(random() * self.n_city)
    				if ct >= self.n_city :
    					ct = self.n_city - 1
    				self.seq[i1] = ct
    				sw           = 1
    				for i2 in range(0, i1) :
    					if ct == self.seq[i2] :
    						sw = 0
    						break
    
    	#################
    	# 最適化の実行
    	#################
    	
    	def Optimize(self) :
    	
    						# 初期設定
    		n_tri  = 0
    		max    = np.empty(1, np.int)
    		max[0] = kyori(self.n_city, self.seq, self.rg)
    	
    		if self.out_m >= 0 and abs(self.out_lvl) > 0 :
    			print("***試行回数 " + str(n_tri) + " 距離 " + str(-max[0]))
    			self.Output(self.out_lvl, n_tri, max[0])
    						# 実行
    		sw = 1
    		for n_tri in range(1, self.max_try+1) :
    							# 改善
    			sw = self.Change(max)
    							# 出力
    			if self.out_d > 0 and n_tri%self.out_d == 0 :
    				print("***試行回数 " + str(n_tri) + " 距離 " + str(-max[0]))
    	
    			if self.out_m >= 0 and abs(self.out_lvl) > 0 :
    				if n_tri%abs(self.out_lvl) == 0 :
    					self.Output(self.out_lvl, n_tri, max[0])
    			if sw <= 0 :
    				break
    						# 最終出力
    		if self.out_m >= 0 :
    			n_tri      -= 1
    			k1          = self.out_m
    			self.out_m  = 0
    			print("***試行回数 " + str(n_tri) + " 距離 " + str(-max[0]))
    			self.Output(self.out_lvl, n_tri, max[0])
    			self.out_m = k1
    	
    		return n_tri
    	
    	###############################
    	# 出力
    	#      sw : >= 0 : 出力先未定
    	#           < 0 : ファイル
    	#      n_tri : 現在の試行回数
    	#      r : 距離の負値
    	###############################
    
    	def Output(self, sw, n_tri, r) :
    	
    		k  = 0
    		pr = -1
    
    		if sw >= 0 :
    			print("   出力先は(0:出力なし,n:画面にn個づつ,-1:ファイル)? ", end=" ")
    			pr = int(input())
    	
    		if pr != 0 :
    	
    			if pr > 0 :
    				out = sys.stdout
    				input("")
    			else :
    				now = datetime.today().time().isoformat()
    				out = open(self.o_file, "a")
    				out.write("***試行回数 " + str(n_tri) + " 距離 " + str(-r) + " 時間 " + now + "\n")
    	
    			if self.out_m == 0 :
    				for i1 in range(0, self.n_city) :
    					n = self.seq[i1]
    					out.write("  " + str(n) + " " + str(self.city[n][0]) + " " + str(self.city[n][1]) + "\n")
    					if pr > 0 :
    						k += 1
    						if k == pr :
    							input("")
    							k = 0
    	
    			if pr <= 0 :
    				out.close()
    	
    	######################################
    	# エッジの入れ替え
    	#      r_m : 距離の負値
    	#      return : =0 : 改善がなかった
    	#               =1 : 改善があった
    	######################################
    
    	def Change(self, r_m) :
    	
    		ch  = 0
    		sw  = 0
    		max = r_m[0]
    	
    		n3  = int(random() * (self.n_city - 2))
    		if n3 > self.n_city-3 :
    			n3 = self.n_city - 3
    							# 2近傍
    		i1 = 0
    		while i1 <= self.n_city-3 and ch == 0 :
    	
    			n1 = self.n_city - 1
    			if n3 == 0 :
    				n1 = self.n_city - 2
    	
    			i2 = n3 + 2
    			while i2 <= n1 and ch == 0 :
    								# 枝の場所((n3,n3+1), (k1,k2))
    				k1 = i2
    				k2 = i2 + 1
    				if i2 == self.n_city-1 :
    					k2 = 0
    								# 枝の入れ替え
    				self.seq_w1[0] = self.seq[n3]
    				k              = 1
    				for i3 in range(k1, n3, -1) :
    					self.seq_w1[k] = self.seq[i3]
    					k += 1
    	
    				nn = k2
    				while nn != n3 :
    					self.seq_w1[k] = self.seq[nn]
    					k  += 1
    					nn += 1
    					if nn > self.n_city-1 :
    						nn = 0
    								# 評価
    				r = kyori(self.n_city, self.seq_w1, self.rg)
    	
    				if r > max :
    					max = r
    					sw  = 1
    					for i3 in range(0, self.n_city) :
    						self.seq_w2[i3] = self.seq_w1[i3]
    					if self.sel > 0 :
    						ch = 1
    				i2 += 1
    	
    			n3 += 1
    			if n3 > self.n_city-3 :
    				n3 = 0
    			i1 += 1
    							# 3近傍
    		if self.neib == 3 and ch == 0 :
    	
    			i1 = 0
    			while i1 <= self.n_city-3 and ch == 0 :
    	
    				n1 = self.n_city - 2
    				n2 = self.n_city - 1
    	
    				i2 = n3 + 1
    				while i2 <= n1 and ch == 0 :
    	
    					i3 = i2 + 1
    					while i3 <= n2 and ch == 0 :
    								# 枝の場所((n3,n3+1), (i2,i2+1), (k1,k2))
    						k1 = i3
    						k2 = i3 + 1
    						if i3 == self.n_city-1 :
    							k2 = 0
    								# 枝の入れ替えと評価
    									# 入れ替え(その1)
    						self.seq_w1[0] = self.seq[n3]
    						k              = 1
    						for i4 in range(i2, n3, -1) :
    							self.seq_w1[k] = self.seq[i4]
    							k += 1
    	
    						for i4 in range(k1, i2, -1) :
    							self.seq_w1[k] = self.seq[i4]
    							k += 1
    	
    						nn = k2
    						while nn != n3 :
    							self.seq_w1[k] = self.seq[nn]
    							k  += 1
    							nn += 1
    							if nn > self.n_city-1 :
    								nn = 0
    									# 評価(その1)
    						r = kyori(self.n_city, self.seq_w1, self.rg)
    	
    						if r > max :
    							max = r
    							sw  = 1
    							for i3 in range(0, self.n_city) :
    								self.seq_w2[i3] = self.seq_w1[i3]
    							if self.sel > 0 :
    								ch = 1
    									# 入れ替え(その2)
    						self.seq_w1[0] = self.seq[n3]
    						k              = 1
    						for i4 in range(k1, i2, -1) :
    							self.seq_w1[k] = self.seq[i4]
    							k += 1
    	
    						for i4 in range(n3+1, i2+1) :
    							self.seq_w1[k] = self.seq[i4]
    							k += 1
    	
    						nn = k2
    						while nn != n3 :
    							self.seq_w1[k] = self.seq[nn]
    							k  += 1
    							nn += 1
    							if nn > self.n_city-1 :
    								nn = 0
    									# 評価(その2)
    						r = kyori(self.n_city, self.seq_w1, self.rg)
    	
    						if r > max :
    							max = r
    							sw  = 1
    							for i3 in range(0, self.n_city) :
    								self.seq_w2[i3] = self.seq_w1[i3]
    							if self.sel > 0 :
    								ch = 1
    									# 入れ替え(その3)
    						self.seq_w1[0] = self.seq[n3]
    						k              = 1
    						for i4 in range(i2+1, k1+1) :
    							self.seq_w1[k] = self.seq[i4]
    							k += 1
    	
    						for i4 in range(i2, n3, -1) :
    							self.seq_w1[k] = self.seq[i4]
    							k += 1
    	
    						nn = k2
    						while nn != n3 :
    							self.seq_w1[k] = self.seq[nn]
    							k  += 1
    							nn += 1
    							if nn > self.n_city-1 :
    								nn = 0
    									# 評価(その3)
    						r = kyori(self.n_city, self.seq_w1, self.rg)
    	
    						if r > max :
    							max = r
    							sw  = 1
    							for i3 in range(0, self.n_city) :
    								self.seq_w2[i3] = self.seq_w1[i3]
    							if self.sel > 0 :
    								ch = 1
    									# 入れ替え(その4)
    						self.seq_w1[0] = self.seq[n3]
    						k              = 1
    						for i4 in range(i2+1, k1+1) :
    							self.seq_w1[k] = self.seq[i4]
    							k += 1
    	
    						for i4 in range(n3+1, i2+1) :
    							self.seq_w1[k] = self.seq[i4]
    							k += 1
    	
    						nn = k2
    						while nn != n3 :
    							self.seq_w1[k] = self.seq[nn]
    							k  += 1
    							nn += 1
    							if nn > self.n_city-1 :
    								nn = 0
    									# 評価(その4)
    						r = kyori(self.n_city, self.seq_w1, self.rg)
    	
    						if r > max :
    							max = r
    							sw  = 1
    							for i3 in range(0, self.n_city) :
    								self.seq_w2[i3] = self.seq_w1[i3]
    							if self.sel > 0 :
    								ch = 1
    						i3 += 1
    					i2 += 1
    	
    				n3 += 1
    				if n3 > self.n_city-3 :
    					n3 = 0
    				i1 += 1
    							# 設定
    		if sw > 0 :
    			r_m[0] = max
    			for i1 in range(0, self.n_city) :
    				self.seq[i1] = self.seq_w2[i1]
    	
    		return sw
    
    ####################################
    # 巡回セールスマン問題(反復改善法)
    #      coded by Y.Suganuma
    ####################################
    
    				# 入力ミス
    if len(sys.argv) <= 1 :
    	print("***error  ファイル名を入力して下さい")
    				# 入力OK
    else :
    					# データの数と入力データファイル名の入力
    	inn    = open(sys.argv[1], "r")
    
    	ss     = inn.readline()
    	n      = int(ss)   # データの数
    	i_file = []
    
    	for i1 in range(0, n) :
    		i_file.append(inn.readline().strip(" \n"))
    
    	inn.close()
    					# 実行
    	for i1 in range(0, n) :
    		print("\n+++++ケース " + str(i1+1) + "+++++")
    		seed(1000 * i1 + 1234567);
    						# 入力と初期設定
    		it = Iteration (i_file[i1])
    						# 最適化
    		it.Optimize()
    
    """
    ------------------ケーススタディデータ(data.txt)------
    3
    data1.txt
    data1.txt
    data2.txt
    
    ------------------データファイル(data1.txt)------------
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    -58 37
    55 -19
    6 -79
    27 -30
    44 -94
    33 -58
    -94 87
    -9 3
    33 69
    43 -57
    
    ------------------データファイル(data2.txt)------------
    都市の数 50 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    86 27
    82 16
    29 37
    27  1
    90 88
    40 92
    87 53
    24 99
    11 80
    61  8
    30 93
     4 81
    86 90
    84 52
    96 45
     4 34
    53  6
    45 12
    23 97
    61 46
    49 16
    82 74
    48 36
    13  5
    12  6
    33 26
     8 50
    98 98
    79 65
    36 56
    42 25
    52 12
    88 79
    27 51
    86 51
    14 35
    77 37
    44  0
    78 13
    21 55
    82 26
    25 88
    55  0
    10 59
    41 33
     7  4
    56 99
    19 34
    92 46
    27 35
    """
    			

  6. C#

    /****************************/
    /* 巡回セールスマン問題     */
    /*      反復改善法          */
    /*      coded by Y.Suganuma */
    /****************************/
    using System;
    using System.IO;
    
    /*************************/
    /* クラスIterationの定義 */
    /*************************/
    class Iteration {
    	int max_try;   // 最大試行回数
    	int neib;   // 近傍(2 or 3)
    	int out_d;   // 表示間隔
    	int [][] rg;   // 都市間の距離
    	int [] seq_w1;   // 都市を訪れる順序(ワーク)
    	int [] seq_w2;   // 都市を訪れる順序(ワーク)
    	int out_lvl;   // 出力レベル
                       //   =0 : 最終出力だけ
                       //   n>0 : n回毎に出力(負の時はファイル)
    	int out_m;   // 出力方法
                     //   =-1 : 出力しない
                     //   =0 : すべてを出力
                     //   =1 : 評価値だけを出力(最終結果だけはすべてを出力)
    	int sel;   // エッジの選択方法
                   //   =0 : 最良のものを選択
                   //   =1 : 最初のものを選択
    	String o_file;   // 出力ファイル名
    	Random rn;   // 乱数
    
    	int [][] city;   //都市の位置データ
    	int n_city;   // 都市の数
    	int n_tri;   // 試行回数
    	int [] seq;   // 都市を訪れる順序
    	int range;   // 現在の評価値
    
    	/****************************/
    	/* コンストラクタ           */
    	/*      seed : 乱数の初期値 */
    	/*      name : ファイル名   */
    	/****************************/
    	public Iteration (int seed, String name)
    	{
    		n_tri          = 0;
    		string[] lines = File.ReadAllLines(name);
    		char[] charSep = new char[] {' '};
    						// 乱数の初期設定
    		rn  = new Random(seed);
    						// 基本データ
    						// 1行目
    		string[] str = lines[0].Split(charSep, StringSplitOptions.RemoveEmptyEntries);
    		n_city       = int.Parse(str[1]);
    		max_try      = int.Parse(str[3]);
    		sel          = int.Parse(str[5]);
    		neib         = int.Parse(str[7]);
    						// 2行目
    		str     = lines[1].Split(charSep, StringSplitOptions.RemoveEmptyEntries);
    		out_lvl = int.Parse(str[1]);
    		out_m   = int.Parse(str[3]);
    						// 3行目
    		str    = lines[2].Split(charSep, StringSplitOptions.RemoveEmptyEntries);
    		o_file = str[1];
    		out_d  = int.Parse(str[3]);
    						// 都市の位置データ
    		city = new int [n_city][];
    		for (int i1 = 0; i1 < n_city; i1++) {
    			city[i1]    = new int [2];
    			str         = lines[i1+3].Split(charSep, StringSplitOptions.RemoveEmptyEntries);
    			city[i1][0] = int.Parse(str[0]);
    			city[i1][1] = int.Parse(str[1]);
    		}
    						// 距離テーブルの作成
    		rg = new int [n_city][];
    
    		for (int i1 = 0; i1 < n_city; i1++) {
    			rg[i1] = new int [n_city];
    			for (int i2 = i1+1; i2 < n_city; i2++) {
    				double x   = city[i2][0] - city[i1][0];
    				double y   = city[i2][1] - city[i1][1];
    				rg[i1][i2] = (int)(Math.Sqrt(x * x + y * y) + 0.5);
    			}
    		}
    
    		for (int i1 = 1; i1 < n_city; i1++) {
    			for (int i2 = 0; i2 < i1; i2++)
    				rg[i1][i2] = rg[i2][i1];
    		}
    						// 都市を訪れる順序(初期設定)
    		seq    = new int [n_city];
    		seq_w1 = new int [n_city];
    		seq_w2 = new int [n_city];
    
    		for (int i1 = 0; i1 < n_city; i1++) {
    			int sw = 0;
    			while (sw == 0) {
    				int ct = (int)(rn.NextDouble() * n_city);
    				if (ct >= n_city)
    					ct = n_city - 1;
    				seq[i1] = ct;
    				sw      = 1;
    				for (int i2 = 0; i2 < i1 && sw > 0; i2++) {
    					if (ct == seq[i2])
    						sw = 0;
    				}
    			}
    		}
    	}
    
    	/****************/
    	/* 最適化の実行 */
    	/****************/
    	public int Optimize ()
    	{
    				// 初期設定
    		range = kyori(n_city, seq, rg);
    				// 初期状態の出力(文字)
    		if (out_m >= 0 && Math.Abs(out_lvl) > 0) {
    			Console.WriteLine("***試行回数 " + n_tri + " 距離 " + (-range));
    			Output(out_lvl);
    		}
    				// 実行
    		int sw = 1;
    		for (n_tri = 1; n_tri <= max_try && sw > 0; n_tri++) {
    					// 改善
    			sw = Change();
    					// 出力(文字)
    			if (out_d > 0 && n_tri%out_d == 0)
    				Console.WriteLine("***試行回数 " + n_tri + " 距離 " + (-range));
    			if (out_m >= 0 && Math.Abs(out_lvl) > 0) {
    				if (n_tri%Math.Abs(out_lvl) == 0)
    					Output(out_lvl);
    			}
    		}
    				// 最終出力(文字)
    		if (out_m >= 0) {
    			n_tri--;
    			int k1 = out_m;
    			out_m  = 0;
    			Console.WriteLine("***試行回数 " + n_tri + " 距離 " + (-range));
    			Output(out_lvl);
    			out_m = k1;
    		}
    
    		return n_tri;
    	}
    
    	/*******************************/
    	/* 出力                        */
    	/*      sw : >= 0 : 出力先未定 */
    	/*           < 0 : ファイル    */
    	/*******************************/
    	void Output(int sw)
    	{
    		int pr = -1;
    		if (sw >= 0) {
    			Console.Write("   出力先は(0:出力なし,n:画面にn個づつ,-1:ファイル)? ");
    			pr = int.Parse(Console.ReadLine());
    		}
    
    		if (pr != 0) {
    
    			StreamWriter OUT = new StreamWriter(o_file, true);
    
    			if (pr < 0) {
    				DateTime now = DateTime.Now;   // 現在時刻の獲得
    				OUT.WriteLine("***試行回数 " + n_tri + " 距離 " + (-range) + " 時間 " + now);
    			}
    
    			if (out_m == 0) {
    				int k = 0;
    				for (int i1 = 0; i1 < n_city; i1++) {
    					int n = seq[i1];
    					if (pr < 0)
    						OUT.WriteLine("  " + n + " " + city[n][0] + " " + city[n][1]);
    					else
    						Console.WriteLine("  " + n + " " + city[n][0] + " " + city[n][1]);
    					if (pr > 0) {
    						k++;
    						if (k == pr) {
    							Console.ReadLine();
    							k = 0;
    						}
    					}
    				}
    			}
    
    			OUT.Close();
    		}
    	}
    
    	/**************************************/
    	/* エッジの入れ替え                   */
    	/*      return : =0 : 改善がなかった  */
    	/*               =1 : 改善があった    */
    	/**************************************/
    	int Change()
    	{
    		int ch = 0, i1, i2, i3, i4, k, k1, k2, max, n1, n2, n3, nn, r, sw = 0;
    
    		max = range;
    
    		n3  = (int)(rn.NextDouble() * (n_city - 2));
    		if (n3 > n_city-3)
    			n3 = n_city - 3;
                             // 2近傍
    		for (i1 = 0; i1 <= n_city-3 && ch == 0; i1++) {
    
    			if (n3 == 0)
    				n1 = n_city - 2;
    			else
    				n1 = n_city - 1;
    
    			for (i2 = n3+2; i2 <= n1 && ch == 0; i2++) {
                                  // 枝の場所((n3,n3+1), (k1,k2))
    				k1 = i2;
    				if (i2 == n_city-1)
    					k2 = 0;
    				else
    					k2 = i2 + 1;
                                  // 枝の入れ替え
    				seq_w1[0] = seq[n3];
    				k         = 1;
    				for (i3 = k1; i3 >= n3+1; i3--) {
    					seq_w1[k] = seq[i3];
    					k++;
    				}
    
    				nn = k2;
    				while (nn != n3) {
    					seq_w1[k] = seq[nn];
    					k++;
    					nn++;
    					if (nn > n_city-1)
    						nn = 0;
    				}
                                  // 評価
    				r = kyori(n_city, seq_w1, rg);
    
    				if (r > max) {
    					max = r;
    					sw  = 1;
    					for (i3 = 0; i3 < n_city; i3++)
    						seq_w2[i3] = seq_w1[i3];
    					if (sel > 0)
    						ch = 1;
    				}
    			}
    
    			n3++;
    			if (n3 > n_city-3)
    				n3 = 0;
    		}
                             // 3近傍
    		if (neib == 3 && ch == 0) {
    
    			for (i1 = 0; i1 <= n_city-3 && ch == 0; i1++) {
    
    				n1 = n_city - 2;
    				n2 = n_city - 1;
    
    				for (i2 = n3+1; i2 <= n1 && ch == 0; i2++) {
    
    					for (i3 = i2+1; i3 <= n2 && ch == 0; i3++) {
                                  // 枝の場所((n3,n3+1), (i2,i2+1), (k1,k2))
    						k1 = i3;
    						if (i3 == n_city-1)
    							k2 = 0;
    						else
    							k2 = i3 + 1;
                                  // 枝の入れ替えと評価
                                       // 入れ替え(その1)
    						seq_w1[0] = seq[n3];
    						k         = 1;
    						for (i4 = i2; i4 >= n3+1; i4--) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						for (i4 = k1; i4 >= i2+1; i4--) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						nn = k2;
    						while (nn != n3) {
    							seq_w1[k] = seq[nn];
    							k++;
    							nn++;
    							if (nn > n_city-1)
    								nn = 0;
    						}
                                       // 評価(その1)
    						r = kyori(n_city, seq_w1, rg);
    
    						if (r > max) {
    							max = r;
    							sw  = 1;
    							for (i3 = 0; i3 < n_city; i3++)
    								seq_w2[i3] = seq_w1[i3];
    							if (sel > 0)
    								ch = 1;
    						}
                                       // 入れ替え(その2)
    						seq_w1[0] = seq[n3];
    						k         = 1;
    						for (i4 = k1; i4 >= i2+1; i4--) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						for (i4 = n3+1; i4 <= i2; i4++) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						nn = k2;
    						while (nn != n3) {
    							seq_w1[k] = seq[nn];
    							k++;
    							nn++;
    							if (nn > n_city-1)
    								nn = 0;
    						}
                                       // 評価(その2)
    						r = kyori(n_city, seq_w1, rg);
    
    						if (r > max) {
    							max = r;
    							sw  = 1;
    							for (i3 = 0; i3 < n_city; i3++)
    								seq_w2[i3] = seq_w1[i3];
    							if (sel > 0)
    								ch = 1;
    						}
                                       // 入れ替え(その3)
    						seq_w1[0] = seq[n3];
    						k         = 1;
    						for (i4 = i2+1; i4 <= k1; i4++) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						for (i4 = i2; i4 >= n3+1; i4--) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						nn = k2;
    						while (nn != n3) {
    							seq_w1[k] = seq[nn];
    							k++;
    							nn++;
    							if (nn > n_city-1)
    								nn = 0;
    						}
                                       // 評価(その3)
    						r = kyori(n_city, seq_w1, rg);
    
    						if (r > max) {
    							max = r;
    							sw  = 1;
    							for (i3 = 0; i3 < n_city; i3++)
    								seq_w2[i3] = seq_w1[i3];
    							if (sel > 0)
    								ch = 1;
    						}
                                       // 入れ替え(その4)
    						seq_w1[0] = seq[n3];
    						k         = 1;
    						for (i4 = i2+1; i4 <= k1; i4++) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						for (i4 = n3+1; i4 <= i2; i4++) {
    							seq_w1[k] = seq[i4];
    							k++;
    						}
    
    						nn = k2;
    						while (nn != n3) {
    							seq_w1[k] = seq[nn];
    							k++;
    							nn++;
    							if (nn > n_city-1)
    								nn = 0;
    						}
                                       // 評価(その4)
    						r = kyori(n_city, seq_w1, rg);
    
    						if (r > max) {
    							max = r;
    							sw  = 1;
    							for (i3 = 0; i3 < n_city; i3++)
    								seq_w2[i3] = seq_w1[i3];
    							if (sel > 0)
    								ch = 1;
    						}
    					}
    				}
    
    				n3++;
    				if (n3 > n_city-3)
    					n3 = 0;
    			}
    		}
                             // 設定
    		if (sw > 0) {
    			range = max;
    			for (i1 = 0; i1 < n_city; i1++)
    				seq[i1] = seq_w2[i1];
    		}
    
    		return sw;
    	}
    
    	/*********************************/
    	/* 距離の計算                    */
    	/*      n_c : 都市の数           */
    	/*      p : 都市番号             */
    	/*      rg : 都市間の距離        */
    	/*      return : 距離(負)      */
    	/*********************************/
    	static int kyori(int n_c, int [] p, int [][] rg)
    	{
    		int n1 = p[0];
    		int n2;
    		int range = 0;
    
    		for (int i1 = 1; i1 < n_c; i1++) {
    			n2     = p[i1];
    			range -= rg[n1][n2];
    			n1     = n2;
    		}
    
    		n2     = p[0];
    		range -= rg[n1][n2];
    
    		return range;
    	}
    }
    
    /****************/
    /* main program */
    /****************/
    class Program
    {
    	static void Main(String[] args)
    	{
    						// 入力ミス
    		if (args.Length == 0)
    			Console.WriteLine("***error  ケーススタディファイル名を入力して下さい");
    						// 入力OK
    		else {
    							// 入力データファイル名の入力
    			String[] lines  = File.ReadAllLines(args[0]);
    			int n           = int.Parse(lines[0]);   // 問題の数
    			String[] i_file = new String [n];
    
    			for (int i1 = 0; i1 < n; i1++)
    				i_file[i1] = lines[i1+1];
    							// 実行(乱数の初期値を変える)
    			for (int i1 = 0; i1 < n; i1++) {
    				Console.WriteLine();
    				Console.WriteLine("+++++ケース " + (i1+1) + "+++++");
    								// 入力と初期設定
    				Iteration it = new Iteration (1000 * i1 + 1234567, i_file[i1]);
    								// 最適化
    				it.Optimize();
    			}
    		}
    	}
    }
    
    //------------------------ケーススタディデータ(data.txt)------
    /*
    3
    data1.txt
    data1.txt
    data2.txt
    */
    //---------------------データファイル(data1.txt)------------
    /*
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    -58 37
    55 -19
    6 -79
    27 -30
    44 -94
    33 -58
    -94 87
    -9 3
    33 69
    43 -57
    */
    
    //---------------------データファイル(data2.txt)------------
    /*
    都市の数 50 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    86 27
    82 16
    29 37
    27  1
    90 88
    40 92
    87 53
    24 99
    11 80
    61  8
    30 93
     4 81
    86 90
    84 52
    96 45
     4 34
    53  6
    45 12
    23 97
    61 46
    49 16
    82 74
    48 36
    13  5
    12  6
    33 26
     8 50
    98 98
    79 65
    36 56
    42 25
    52 12
    88 79
    27 51
    86 51
    14 35
    77 37
    44  0
    78 13
    21 55
    82 26
    25 88
    55  0
    10 59
    41 33
     7  4
    56 99
    19 34
    92 46
    27 35
    */
    			

  7. VB

    '**************************'
    ' 巡回セールスマン問題     '
    '      反復改善法          '
    '      coded by Y.Suganuma '
    '**************************'
    Imports System.IO
    Imports System.Text.RegularExpressions
    
    Module Test
    
    	Sub Main(args() As String)
    						' 入力ミス
    		If args.Length = 0
    			Console.WriteLine("***error  ケーススタディファイル名を入力して下さい")
    						' 入力OK
    		Else
    							' 入力データファイル名の入力
    			Dim inp As StreamReader = New StreamReader(args(0))
    			Dim n As Integer        = Integer.Parse(inp.ReadLine())   ' 問題の数
    
    			Dim i_file(n) As String
    			For i1 As Integer = 0 To n-1
    				i_file(i1) = inp.ReadLine()
    			Next
    			inp.Close()
    							' 実行(乱数の初期値を変える)
    			For i1 As Integer = 0 To n-1
    				Console.WriteLine()
    				Console.WriteLine("+++++ケース " & (i1+1) & "+++++")
    								' 入力と初期設定
    				Dim it As Iteration = new Iteration (1000 * i1 + 1234567, i_file(i1))
    								' 最適化
    				it.Optimize()
    			Next
    		End If
    
    	End Sub
    
    	'*******************************'
    	' 距離の計算                    '
    	'      n_c : 都市の数           '
    	'      p : 都市番号             '
    	'      rg : 都市間の距離        '
    	'      return : 距離            '
    	'*******************************'
    	Function kyori(n_c As Integer, p() As Integer, rg(,) As Integer)
    
    		Dim range As Double = 0
    		Dim n1 As Integer   = p(0)
    		Dim n2 As Integer
    	
    		For i1 As Integer = 1 To n_c-1
    			n2     = p(i1)
    			range -= rg(n1,n2)
    			n1     = n2
    		Next
    	
    		n2     = p(0)
    		range -= rg(n1,n2)
    	
    		Return range
    
    	End Function
    
    	'***********************'
    	' クラスIterationの定義 '
    	'***********************'
    	Class Iteration
    
    		Private max_try As Integer   ' 最大試行回数
    		Private neib As Integer   ' 近傍(2 or 3)
    		Private out_d As Integer   ' 表示間隔
    		Private rg(,) As Integer   ' 都市間の距離
    		Private seq_w1() As Integer   ' 都市を訪れる順序(ワーク)
    		Private seq_w2() As Integer   ' 都市を訪れる順序(ワーク)
    		Private out_lvl As Integer   ' 出力レベル
    	                                 '   =0 : 最終出力だけ
    	                                 '   n>0 : n回毎に出力(負の時はファイル)
    		Private out_m As Integer   ' 出力方法
    	                               '   =-1 : 出力しない
    	                               '   =0 : すべてを出力
    	                               '   =1 : 評価値だけを出力(最終結果だけはすべてを出力)
    		Private sel As Integer   ' エッジの選択方法
    	                             '   =0 : 最良のものを選択
    	                             '   =1 : 最初のものを選択
    		Private o_file As String   ' 出力ファイル名
    		Private rn As Random   ' 乱数
    	
    		Private city(,) As Integer   '都市の位置データ
    		Private n_city As Integer   ' 都市の数
    		Private n_tri As Integer   ' 試行回数
    		Public seq() As Integer   ' 都市を訪れる順序
    		Private range As Integer   ' 現在の評価値
    	
    		'**************************'
    		' コンストラクタ           '
    		'      seed : 乱数の初期値 '
    		'      name : ファイル名   '
    		'**************************'
    		Public Sub New (seed As Integer, name As String)
    
    			n_tri = 0
    			Dim MS As Regex         = New Regex("\s+") 
    			Dim inp As StreamReader = New StreamReader(name)
    							' 乱数の初期設定
    			rn  = new Random(seed)
    							' 基本データ
    							' 1行目
    			Dim str() As String = MS.Split(inp.ReadLine().Trim())
    			n_city              = Integer.Parse(str(1))
    			max_try             = Integer.Parse(str(3))
    			sel                 = Integer.Parse(str(5))
    			neib                = Integer.Parse(str(7))
    							' 2行目
    			str     = MS.Split(inp.ReadLine().Trim())
    			out_lvl = Integer.Parse(str(1))
    			out_m   = Integer.Parse(str(3))
    							' 3行目
    			str    = MS.Split(inp.ReadLine().Trim())
    			o_file = str(1)
    			out_d  = Integer.Parse(str(3))
    							' 都市の位置データ
    			ReDim city(n_city, 2)
    			For i1 As Integer = 0 To n_city-1
    				str        = MS.Split(inp.ReadLine().Trim())
    				city(i1,0) = Integer.Parse(str(0))
    				city(i1,1) = Integer.Parse(str(1))
     			Next
     			inp.Close()
     						' 距離テーブルの作成
    			ReDim rg(n_city, n_city)
    	
    			For i1 As Integer = 0 To n_city-1
     				For i2 As Integer = i1+1 To n_city-1
    					Dim x As Double = city(i2,0) - city(i1,0)
    					Dim y As Double = city(i2,1) - city(i1,1)
    					rg(i1,i2) = Math.Floor(Math.Sqrt(x * x + y * y) + 0.5)
    				Next
    			Next
    	
    			For i1 As Integer = 1 To n_city-1
    				For i2 As Integer = 0 To i1-1
    					rg(i1,i2) = rg(i2,i1)
    				Next
    			Next
    							' 都市を訪れる順序(初期設定)
    			ReDim seq(n_city)
    			ReDim seq_w1(n_city)
    			ReDim seq_w2(n_city)
    	
    			For i1 As Integer = 0 To n_city-1
    				Dim sw As Integer = 0
    				Do While sw = 0
    					Dim ct As Integer = Math.Floor(rn.NextDouble() * n_city)
    					If ct >= n_city
    						ct = n_city - 1
    					End If
    					seq(i1) = ct
    					sw      = 1
    					Dim i2 As Integer = 0
    					Do While i2 < i1 and sw > 0
    						If ct = seq(i2)
    							sw = 0
     						End If
    						i2 += 1
    	 				Loop
    				Loop
    			Next
    		End Sub
    
    		'**************'
    		' 最適化の実行 '
    		'**************'
    		Public Function Optimize ()
    
    					' 初期設定
    			range = kyori(n_city, seq, rg)
    					' 初期状態の出力(文字)
    			If out_m >= 0 and Math.Abs(out_lvl) > 0
    				Console.WriteLine("***試行回数 " & n_tri & " 距離 " & (-range))
    				Output(out_lvl)
    			End If
    					' 実行
    			Dim sw As Integer = 1
    			n_tri = 1
    			Do While n_tri <= max_try and sw > 0
    						' 改善
    	   			sw = Change()
    						' 出力(文字)
    				If out_d > 0
    					If (n_tri Mod out_d) = 0
    						Console.WriteLine("***試行回数 " + n_tri + " 距離 " + (-range))
    					End If
    					If out_m >= 0
    						If Math.Abs(out_lvl) > 0
    							If (n_tri Mod Math.Abs(out_lvl)) = 0
    								Output(out_lvl)
    							End If
    						End If
    					End If
    				End If
    				n_tri += 1
    			Loop
    					' 最終出力(文字)
    			If out_m >= 0
    				n_tri -= 1
    				Dim k1 As Integer = out_m
    				out_m = 0
    				Console.WriteLine("***試行回数 " & n_tri & " 距離 " & (-range))
    				Output(out_lvl)
    				out_m = k1
    			End If
    	
    			Return n_tri
    
    		End Function
    
    	   	'*****************************'
    		' 出力                        '
    		'      sw : >= 0 : 出力先未定 '
    		'           < 0 : ファイル    '
    		'*****************************'
    		Sub Output(sw As Integer)
    
    			Dim pr As Integer = -1
    			If sw >= 0
    				Console.Write("   出力先は(0:出力なし,n:画面にn個づつ,-1:ファイル)? ")
    				pr = Integer.Parse(Console.ReadLine())
    			End If
    	
    			If pr <> 0
    	
    				Dim OUT As StreamWriter = new StreamWriter(o_file, true)
    	
    				If pr < 0
    					Dim now1 As DateTime = DateTime.Now   ' 現在時刻の獲得
    					OUT.WriteLine("***試行回数 " & n_tri & " 距離 " & (-range) & " 時間 " & now1)
    				End If
    	
    				If out_m = 0
    					Dim k As Integer = 0
    					For i1 As Integer = 0 To n_city-1
    						Dim n As Integer = seq(i1)
    						If pr < 0
    							OUT.WriteLine("  " & n & " " & city(n,0) & " " & city(n,1))
    						Else
    							Console.WriteLine("  " & n & " " & city(n,0) & " " & city(n,1))
    						End If
    						If pr > 0
    							k += 1
    							If k = pr
    								Console.ReadLine()
    								k = 0
    							End If
    						End If
    					Next
    				End If
    	
    				OUT.Close()
    
    			End If
    
    		End Sub
    
    		'************************************'
    		' エッジの入れ替え                   '
    		'      return : =0 : 改善がなかった  '
    		'               =1 : 改善があった    '
    		'************************************'
    		Function Change()
    
    			Dim ch As Integer = 0
    			Dim i1 As Integer
    			Dim i2 As Integer
    			Dim i3 As Integer
    			Dim i4 As Integer
    			Dim k As Integer
    			Dim k1 As Integer
    			Dim k2 As Integer
    			Dim max As Integer
    			Dim n1 As Integer
    			Dim n2 As Integer
    			Dim n3 As Integer
    			Dim nn As Integer
    			Dim r As Integer
    			Dim sw As Integer = 0
    	
    			max = range
    	
    			n3  = Math.Floor(rn.NextDouble() * (n_city - 2))
    			If n3 > n_city-3
    				n3 = n_city - 3
    			End If
    	                         ' 2近傍
    			i1 = 0
    			Do While i1 <= n_city-3 and ch = 0
    	
    				If n3 = 0
    					n1 = n_city - 2
    				Else
    					n1 = n_city - 1
    				End If
    	
    				i2 = n3 + 2
    				Do While i2 <= n1 and ch = 0
    	                              ' 枝の場所((n3,n3+1), (k1,k2))
    					k1 = i2
    					If i2 = n_city-1
    						k2 = 0
    					Else
    						k2 = i2 + 1
    					End If
    	                              ' 枝の入れ替え
    					seq_w1(0) = seq(n3)
    					k         = 1
    					For i3 = k1 To n3+1 Step -1
    						seq_w1(k) = seq(i3)
    						k        += 1
    					Next
    	
    					nn = k2
    					Do While nn <> n3
    						seq_w1(k) = seq(nn)
    						k        += 1
    						nn       += 1
    						If nn > n_city-1
    							nn = 0
    						End If
    					Loop
    	                              ' 評価
    					r = kyori(n_city, seq_w1, rg)
    	
    					If r > max
    						max = r
    						sw  = 1
    						For i3 = 0 To n_city-1
    							seq_w2(i3) = seq_w1(i3)
    						Next
    						If sel > 0
    							ch = 1
    						End If
    					End If
    					i2 += 1
    				Loop
    	
    				n3 += 1
    				If n3 > n_city-3
    					n3 = 0
    				End If
    				i1 += 1
    			Loop
    	                         ' 3近傍
    			If neib = 3 and ch = 0
    	
    				i1 = 0
    				Do While i1 <= n_city-3 and ch = 0
    	
    					n1 = n_city - 2
    					n2 = n_city - 1
    	
    					i2 = n3 + 1
    					Do While i2 <= n1 and ch = 0
    	
    						i3 = i2 + 1
    						Do While i3 <= n2 and ch = 0
    	                              ' 枝の場所((n3,n3+1), (i2,i2+1), (k1,k2))
    							k1 = i3
    							If i3 = n_city-1
    								k2 = 0
    							Else
    								k2 = i3 + 1
    							End If
    	                              ' 枝の入れ替えと評価
    	                                   ' 入れ替え(その1)
    							seq_w1(0) = seq(n3)
    							k         = 1
    							For i4 = i2 To n3+1 Step -1
    								seq_w1(k) = seq(i4)
    								k        += 1
    							Next
    	
    							For i4 = k1 To i2+1 Step -1
    								seq_w1(k) = seq(i4)
    								k        += 1
    							Next
    	
    							nn = k2
    							Do While nn <> n3
    								seq_w1(k) = seq(nn)
    								k        += 1
    								nn       += 1
    								If nn > n_city-1
    									nn = 0
    								End If
    							Loop
    	                                   ' 評価(その1)
    							r = kyori(n_city, seq_w1, rg)
    	
    							If r > max
    								max = r
    								sw  = 1
    								For i3 = 0 To n_city-1
    									seq_w2(i3) = seq_w1(i3)
    								Next
    								If sel > 0
    									ch = 1
    								End If
    							End If
    	                                   ' 入れ替え(その2)
    							seq_w1(0) = seq(n3)
    							k         = 1
    							For i4 = k1 To i2+1 Step -1
    								seq_w1(k) = seq(i4)
    								k        += 1
    							Next
    	
    							For i4 = n3+1 To i2
    								seq_w1(k) = seq(i4)
    								k        += 1
    							Next
    	
    							nn = k2
    							Do While nn <> n3
    								seq_w1(k) = seq(nn)
    								k        += 1
    								nn       += 1
    								If nn > n_city-1
    									nn = 0
    								End If
    							Loop
    	                                   ' 評価(その2)
    							r = kyori(n_city, seq_w1, rg)
    	
    							If r > max
    								max = r
    								sw  = 1
    								For i3 = 0 To n_city-1
    									seq_w2(i3) = seq_w1(i3)
    								Next
    								If sel > 0
    									ch = 1
    								End If
    							End If
    
    	                                   ' 入れ替え(その3)
    							seq_w1(0) = seq(n3)
    							k         = 1
    							For i4 = i2+1 To k1
    								seq_w1(k) = seq(i4)
    								k        += 1
    							Next
    	
    							For i4 = i2 To n3+1 Step -1
    								seq_w1(k) = seq(i4)
    								k        += 1
    							Next
    	
    							nn = k2
    							Do While nn <> n3
    								seq_w1(k) = seq(nn)
    								k        += 1
    								nn       += 1
    								If nn > n_city-1
    									nn = 0
    								End If
    							Loop
    	                                   ' 評価(その3)
    							r = kyori(n_city, seq_w1, rg)
    	
    							If r > max
    								max = r
    								sw  = 1
    								For i3 = 0 To n_city-1
    									seq_w2(i3) = seq_w1(i3)
    								Next
    								If sel > 0
    									ch = 1
    								End If
    							End If
    	                                   ' 入れ替え(その4)
    							seq_w1(0) = seq(n3)
    							k         = 1
    							For i4 = i2+1 To k1
    								seq_w1(k) = seq(i4)
    								k        += 1
    							Next
    	
    							For i4 = n3+1 To i2
    								seq_w1(k) = seq(i4)
    								k        += 1
    							Next
    	
    							nn = k2
    							Do While nn <> n3
    								seq_w1(k) = seq(nn)
    								k        += 1
    								nn       += 1
    								If nn > n_city-1
    									nn = 0
    								End If
    							Loop
    	                                   ' 評価(その4)
    							r = kyori(n_city, seq_w1, rg)
    	
    							If r > max
    								max = r
    								sw  = 1
    								For i3 = 0 To n_city-1
    									seq_w2(i3) = seq_w1(i3)
    								Next
    								If sel > 0
    									ch = 1
    								End If
    							End If
    							i3 += 1
    						Loop
    						i2 += 1
    					Loop
    	
    					n3 += 1
    					If n3 > n_city-3
    						n3 = 0
    					End If
    					i1 += 1
    				Loop
    			End If
    	                         ' 設定
    			If sw > 0
    				range = max
    				For i1 = 0 To n_city-1
    					seq(i1) = seq_w2(i1)
    				Next
    			End If
    	
    			Return sw
    
    		End Function
    
    	End Class
    	
    End Module
    
    //------------------------ケーススタディデータ(data.txt)------
    /*
    3
    data1.txt
    data1.txt
    data2.txt
    */
    //---------------------データファイル(data1.txt)------------
    /*
    都市の数 10 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    -58 37
    55 -19
    6 -79
    27 -30
    44 -94
    33 -58
    -94 87
    -9 3
    33 69
    43 -57
    */
    
    //---------------------データファイル(data2.txt)------------
    /*
    都市の数 50 最大試行回数 3000 選択方法(0:最良,1:最初) 1 近傍(2or3) 3
    出力レベル(負はファイル) 0 出力方法(-1:なし,0:すべて,1:評価値) 1
    出力ファイル名 out1.txt 表示間隔 0
    86 27
    82 16
    29 37
    27  1
    90 88
    40 92
    87 53
    24 99
    11 80
    61  8
    30 93
     4 81
    86 90
    84 52
    96 45
     4 34
    53  6
    45 12
    23 97
    61 46
    49 16
    82 74
    48 36
    13  5
    12  6
    33 26
     8 50
    98 98
    79 65
    36 56
    42 25
    52 12
    88 79
    27 51
    86 51
    14 35
    77 37
    44  0
    78 13
    21 55
    82 26
    25 88
    55  0
    10 59
    41 33
     7  4
    56 99
    19 34
    92 46
    27 35
    */
    			

静岡理工科大学 菅沼ホーム 目次 索引