巡回セールスマン問題（逐次改善法）

データ例とプログラム

　　以下，複数のファイル構成になっています．ファイル間の区切りを「---･･･」で示します．

------------------------ケーススタディデータ------
3
1 data/data10
12 data/data10
123 data/data10

------------------------データファイル------------
都市の数 10 最大試行回数 3000 選択方法(0:最良，1:最初) 1 近傍（2or3） 3
出力レベル(負はファイル) 0 出力方法(-1:なし，0:すべて，1:評価値) 1
出力ファイル名 result/kekka1 表示間隔 0
図示(0:しない，1:結果，2:初期状態と結果，3:ステップ) 1
都市番号 20 図の大きさ（幅，高さ） 1000 750
-58 37
55 -19
6 -79
27 -30
44 -94
33 -58
-94 87
-9 3
33 69
43 -57

------------------------クラスIteration-----------
/*************************/
/* クラスIterationの定義 */
/*************************/
import java.io.*;
import java.util.Random;
import java.util.Date;
import java.util.StringTokenizer;

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 : ｎ回毎に出力（負の時はファイル）
	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:画面にｎ個づつ，-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;
                         // ２近傍
		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;
		}
                         // ３近傍
		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;
                              // 枝の入れ替えと評価
                                   // 入れ替え（その１）
						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;
						}
                                   // 評価（その１）
						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];
						}
                                   // 入れ替え（その２）
						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;
						}
                                   // 評価（その２）
						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];
						}
                                   // 入れ替え（その３）
						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;
						}
                                   // 評価（その３）
						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];
						}
                                   // 入れ替え（その４）
						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;
						}
                                   // 評価（その４）
						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--------------
/**********************/
/* クラスWin_itの定義 */
/**********************/
import java.awt.*;
import java.awt.event.*;

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(クラスTSP)-----------
/****************************/
/* 巡回セールスマン問題     */
/*      反復改善法          */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.StringTokenizer;

public class TSP {

	/****************/
	/* main program */
	/****************/
	public static void main(String args[]) throws IOException, FileNotFoundException
	{
		int i1, n, seed[];
		String i_file[], line;
		Iteration it;
		StringTokenizer dt;
		BufferedReader in = new BufferedReader(new FileReader(args[0]));
						// 入力ミス
		if (args.length == 0) {
			System.out.print("***error  ファイル名を入力して下さい\n");
			System.exit(1);
		}
						// 入力ＯＫ
		else {
							// 乱数の初期値と入力データファイル名の入力
			n      = Integer.parseInt(in.readLine());

			seed   = new int [n];
			i_file = new String [n];

			for (i1 = 0; i1 < n; i1++) {
				line = in.readLine();
				dt   = new StringTokenizer(line, " ");
				seed[i1] = Integer.parseInt(dt.nextToken());
				i_file[i1] = dt.nextToken();
			}

			in.close();
							// 実行（乱数の初期値を変える）
			for (i1 = 0; i1 < n; i1++) {
				System.out.print("\n+++++ケース " + (i1+1) + "+++++\n");
								// 入力と初期設定
				it = new Iteration (seed[i1], i_file[i1]);
								// 最適化
				it.Optimize();
			}
		}
	}
}
		

　　コンパイルした後，

java TSP　ケーススタディファイル名

と入力してやれば実行できます．ケーススタディファイルは，たとえば，同じ問題を乱数の初期値を変えて実行したいような場合や複数の問題を解く場合に効果的であり，以下のような形式で作成します．

3
1 data/data10
12 data/data10
123 data/data10		

　　最初の行に問題の数を入力し，以下，その数だけ，乱数の初期値とデータファイル名をペアーで入力します．データファイルは，問題自身とその解法の詳細を記述するためのファイルであり，たとえば以下のように記述します．なお，このプログラムでは，計算結果を画面に図示することが可能になっています．

都市の数 10 最大試行回数 3000 選択方法(0:最良，1:最初) 1 近傍（2or3） 3
出力レベル(負はファイル) 0 出力方法(-1:なし，0:すべて，1:評価値) 1
出力ファイル名 result/data10 表示間隔 0
図示(0:しない，1:結果，2:初期状態と結果，3:ステップ) 1
都市番号 20 図の大きさ（幅，高さ） 1000 750
-58 37
55 -19
・・・		

　　日本語で記述した部分（「都市の数」，「最大試行回数」等）は，次に続くデータの説明ですのでどのように修正しても構いませんが，削除したり，または，複数の文（間に半角のスペースを入れる）にするようなことはしないでください．各データの意味は以下に示す通りです．

都市の数

　　都市の数を入力します

最大試行回数

　　逐次改善法における最大試行回数です．もちろん，この回数より少ない回数で改善が不可能になればその時点で終了します．

選択方法(0:最良，1:最初)

　　最適値を逐次改善法を利用して求めます．逐次改善法においては，λ近傍に含まれる（λ本の）枝を入れ替えるという作業を距離の改善がなされなくなるまで続けることによって，解を求めます．各ステップにおいて，どのλ本の枝を入れ替えるかを探索していきますが，ここに 0 を入力すると，λ本の枝を入れ替えるすべての組み合わせの内，最も改善度が高いものを選択します．また，1 を入力すると，最初に見つかったλ本の枝をすぐ入れ替えます．通常，1 で良いと思います．

近傍（2or3）

　　λの値を入力してください，利用できるのは 2 または 3 だけです．

出力レベル(負はファイル)

　　結果の出力方法を入力します．

=0 : 最終結果だけを出力します．

=n : n 回毎に出力します．なお，n が負の場合は，-n 回毎に，ファイルに追加形式（ append ）で出力されます．n が正の場合は，出力するたびに，出力を行うか否か，および，どこに出力するかを聞いてきます．したがって，この段階において，出力先をファイルに変更することも可能です（ n = 0 の場合も同様）．

出力方法(-1:なし，0:すべて，1:評価値)

　　結果の出力方法を入力します．

=-1 : 出力を全く行いません．

=0 : 経路長と巡回する都市の順番を出力します．

=1 : 得られた経路長だけを出力します．ただし，最終結果だけは，都市の順番も出力します．

出力ファイル名

　　結果を保存するファイル名です．なお，画面に出力する場合も，この項目を必ず入力してください（利用はされません）．

表示間隔

　　計算がどこまで進んでいるのかを示すため，結果の概略を画面に表示しますが，それを何回毎に行うのかを入力します．

図示(0:しない，1:結果，2:初期状態と結果，3:ステップ)

結果を図示するか否かを入力します．

=0 : 図示しない

=1 : 最終結果だけを図示

=2 : 初期状態と最終結果を図示

=3 : 初期状態，最終結果，および，改善の過程を表示．改善過程の表示は，マウスで図中の 「 next 」 ボタンをクリックすることによって実行されます．したがって，初期状態を図示した後，この状態に入ると，

　　　　終了したらreturnキーを押してください

というメッセージが出力され，次に進まなくなりますので，マウスクリックによって最適解を達成した後，return キーを入力して継続してください．なお，マウスクリックによる表示の際，交換される前の枝が赤色で表示されますが，赤色の枝がなくなった時点が最適解となります．

都市番号

　　都市番号を表示する際，その字の大きさを入力します．0 を入力すると都市番号を表示しません．

図の大きさ（幅，高さ）

　　図の幅と高さの最大値を入力します．実際に表示される図の大きさは，これらの値と都市座標の分布状況によって，上下，左右の縮尺が等しくなるように決められます．

-58 37

55 -19

・・・

　　以下，各都市の x 座標と y 座標です（整数値）．都市の数だけ必要になります．この入力された順番が，その都市の都市番号になります（ 0 から始まる）．

　　結果を画面に出力する場合，各ケースが終了毎に入力待ちの状態になります．また，都市の順番も出力する場合は，指定された数の都市を出力する毎に入力待ちの状態になります．return キーを入力すれば継続されます．

　　なお，図示する場合，対応する図が表示される毎に（マウスクリックによる場合を除く），MS-DOSの画面に

　　図を確認したらreturnキーを押してください

のようなメッセージが出力されますので，メッセージに従い return を押して継続してください．