データ例とプログラム
------------------------ケーススタディデータ------
問題の数 2
問題 data/pr439.tsp 乱数の数 10
乱数 1
乱数 12
乱数 123
乱数 1234
乱数 12345
乱数 54321
乱数 5432
乱数 543
乱数 54
乱数 5
問題 data/kroA100.tsp 乱数の数 10
乱数 1
乱数 12
乱数 123
乱数 1234
乱数 12345
乱数 54321
乱数 5432
乱数 543
乱数 54
乱数 5
------------------------データファイル------------
都市の数 439 選択方法(0:最良，1:最初) 1 近傍（2or3） 3 整数 1
出力(0:ディスプレイ，1:ファイル) -1 出力ファイル名 result/pr439
分割数 Ｘ 4 Ｙ 3 最大試行回数 1000
図示(0:しない，1:結果，2:初期状態と結果，3:ステップ) 3
都市番号 0 図の大きさ（幅，高さ） 1000 750
7125 11300
7225 11050
･････
1775 5375
2075 6475
------------------------クラスPartition-----------
/*************************/
/* クラスPartitionの定義 */
/*************************/
import java.io.*;
import java.util.Random;
import java.util.Date;
import java.util.StringTokenizer;
class Partition {
private float [][] rg; // 都市間の距離
private float [] p_x; // ｘ軸の分割点
private float [] p_y; // ｙ軸の分割点
private int fix; // =1 : 近傍を固定
// =0 : 近傍を可変
private int max_try; // 最大試行回数
private int [] seq_w1; // 作業領域
private int [] seq_w2; // 作業領域
private int neib; // 近傍（2 or 3）
int seisu; // 位置データの表現方法
// =1 : 整数
// =-1 : 実数（距離を整数計算）
// =-2 : 実数（距離を実数計算）
private int sel; // エッジの選択方法
// =0 : 最良のものを選択
// =1 : 最初のものを選択
private String i_file; // 入力ファイル名
private Win_pt wn; // Win_itオブジェクト
private Random rn; // 乱数
float [][] city; //都市の位置データ
float [][] city_i; //都市の位置データ（作業領域）
int Max; // 最適経路の長さ
int n_city; // 都市の数
int [][] n_seq; // 各領域の都市数
int [][] n_seq1; // 各領域の都市数（ワーク）
int n_p_x; // ｘ軸方向の分割数
int n_p_y; // ｙ軸方向の分割数
int out_m; // 出力方法
// =-1 : ディスプレイ（経路長だけ）
// =0 : ディスプレイ
// =1 : ファイル
// =2 : ファイル（経路長だけ）
int range; // 現在の評価値
int seed; // 乱数の初期値
int [][][] seq; // 経路
int [][][] seq1; // 経路（ワーク）
int [][] state; // 領域結合用ワーク
int display; // 画面表示
// =0 : 画面表示を行わない
// =1 : 結果だけを表示
// =2 : 初期状態と結果を表示
// =3 : １領域の最適化終了毎に表示
String o_file; // 出力ファイル名
/**************************/
/* コンストラクタ */
/* name : ファイル名 */
/**************************/
Partition(String name) throws IOException, FileNotFoundException
{
double x, y;
float max_x, max_y, min_x, min_y, s_x, s_y;
int i1, i2, i3, max = 0, n;
String line;
StringTokenizer dt;
BufferedReader in = new BufferedReader(new FileReader(name));
// 基本データ
i_file = name;
line = in.readLine();
dt = new StringTokenizer(line, " ");
dt.nextToken();
n_city = Integer.parseInt(dt.nextToken());
dt.nextToken();
sel = Integer.parseInt(dt.nextToken());
dt.nextToken();
neib = Integer.parseInt(dt.nextToken());
dt.nextToken();
seisu = Integer.parseInt(dt.nextToken());
if (neib < 0) {
neib = -neib;
fix = 0;
}
else
fix = 1;
line = in.readLine();
dt = new StringTokenizer(line, " ");
dt.nextToken();
out_m = Integer.parseInt(dt.nextToken());
dt.nextToken();
o_file = dt.nextToken();
line = in.readLine();
dt = new StringTokenizer(line, " ");
dt.nextToken();
dt.nextToken();
n_p_x = Integer.parseInt(dt.nextToken());
dt.nextToken();
n_p_y = Integer.parseInt(dt.nextToken());
dt.nextToken();
max_try = 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 float [n_city][2];
for (i1 = 0; i1 < n_city; i1++) {
line = in.readLine();
dt = new StringTokenizer(line, " ");
city[i1][0] = Float.parseFloat(dt.nextToken());
city[i1][1] = Float.parseFloat(dt.nextToken());
}
// ファイルのクローズ
in.close();
// 距離テーブルの作成
rg = new float [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] = (float)Math.sqrt(x * x + y * y);
if (seisu > -2)
rg[i1][i2] = (int)(rg[i1][i2] + 0.5);
}
}
for (i1 = 1; i1 < n_city; i1++) {
for (i2 = 0; i2 < i1; i2++)
rg[i1][i2] = rg[i2][i1];
}
// 作業領域
state = new int [n_p_y][n_p_x];
n_seq = new int [n_p_y][n_p_x];
n_seq1 = new int [n_p_y][n_p_x];
seq = new int [n_p_y][n_p_x][n_city];
seq1 = new int [n_p_y][n_p_x][n_city];
seq_w1 = new int [n_city];
seq_w2 = new int [n_city];
p_x = new float [n_p_x];
p_y = new float [n_p_y];
// 都市の分割
for (i1 = 0; i1 < n_city; i1++)
seq_w1[i1] = 0;
min_x = city[0][0];
max_x = city[0][0];
min_y = city[0][1];
max_y = city[0][1];
for (i1 = 1; i1 < n_city; i1++) {
if (city[i1][0] < min_x)
min_x = city[i1][0];
else {
if (city[i1][0] > max_x)
max_x = city[i1][0];
}
if (city[i1][1] < min_y)
min_y = city[i1][1];
else {
if (city[i1][1] > max_y)
max_y = city[i1][1];
}
}
s_x = (max_x - min_x) / n_p_x;
p_x[0] = min_x + s_x;
p_x[n_p_x-1] = max_x;
for (i1 = 1; i1 < n_p_x-1; i1++)
p_x[i1] = p_x[0] + i1 * s_x;
s_y = (max_y - min_y) / n_p_y;
p_y[0] = min_y + s_y;
p_y[n_p_y-1] = max_y;
for (i1 = 1; i1 < n_p_y-1; i1++)
p_y[i1] = p_y[0] + i1 * s_y;
for (i1 = 0; i1 < n_p_y; i1++) {
for (i2 = 0; i2 < n_p_x; i2++) {
n = 0;
for (i3 = 0; i3 < n_city; i3++) {
if (seq_w1[i3] == 0) {
if (city[i3][0] <= p_x[i2] && city[i3][1] <= p_y[i1]) {
seq_w1[i3] = 1;
seq_w2[n] = i3;
n++;
}
}
}
n_seq1[i1][i2] = n;
if (n > 0) {
for (i3 = 0; i3 < n; i3++)
seq1[i1][i2][i3] = seq_w2[i3];
if (n > max)
max = n;
}
}
}
for (i1 = 0; i1 < n_p_y; i1++) {
for (i2 = 0; i2 < n_p_x; i2++)
state[i1][i2] = (n_seq1[i1][i2] > 0) ? 0 : 1;
}
// 作業領域
System.out.println("max " + max);
city_i = new float [max][2];
// Windowの生成
if (display > 0)
wn = new Win_pt (this, font, width, height);
}
/******************************/
/* 最適化の実行 */
/* seed_i : 乱数の初期値 */
/******************************/
void Optimize(int seed_i) throws IOException, FileNotFoundException
{
int i1, i2, i3, k, max, nb, r;
Iteration it;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// 乱数の初期設定
seed = seed_i;
rn = new Random (seed);
for (i1 = 0; i1 < n_p_y; i1++) {
for (i2 = 0; i2 < n_p_x; i2++) {
n_seq[i1][i2] = n_seq1[i1][i2];
state[i1][i2] = (n_seq1[i1][i2] > 0) ? 0 : 1;
for (i3 = 0; i3 < n_seq1[i1][i2]; i3++)
seq[i1][i2][i3] = seq1[i1][i2][i3];
}
}
// 初期状態の出力（図）
if (display >= 2) {
wn.Draw(0, -1, -1);
System.out.println(" 図を確認したらreturnキーを押してください");
in.readLine();
}
// 分割数と開始時間の出力（ファイルへ出力する場合）
if (out_m > 0)
Output(0);
// 分割毎の最適化
for (i1 = 0; i1 < n_p_y; i1++) {
for (i2 = 0; i2 < n_p_x; i2++) {
if (n_seq[i1][i2] > 3) {
// 近傍の大きさ
nb = (n_seq[i1][i2] > 3) ? neib : 2;
// 都市位置データの設定
for (i3 = 0; i3 < n_seq[i1][i2]; i3++) {
k = seq[i1][i2][i3];
city_i[i3][0] = city[k][0];
city_i[i3][1] = city[k][1];
}
// 最適化
it = new Iteration (n_seq[i1][i2], max_try, seisu, sel, nb, fix,
0, -1, 0, o_file, city_i, 0, rn);
max = it.Optimize();
// 結果の保存
for (i3 = 0; i3 < n_seq[i1][i2]; i3++) {
k = it.seq[i3];
seq_w1[i3] = seq[i1][i2][k];
}
for (i3 = 0; i3 < n_seq[i1][i2]; i3++)
seq[i1][i2][i3] = seq_w1[i3];
// 出力（文字）
r = (seisu > -2) ? (int)Iteration.kyori(n_seq[i1][i2], seq[i1][i2], rg) :
(int)(Iteration.kyori(n_seq[i1][i2], seq[i1][i2], rg) + 0.5);
System.out.print(" y " + (i1+1) + " x " + (i2+1) +
" n_city " + n_seq[i1][i2] +
" range " + r + " (trial " + max + ")\n");
// 区分毎最適化結果の出力（図）
if (display == 3) {
wn.Draw(0, i1, i2);
System.out.println(" 図を確認したらreturnキーを押してください");
in.readLine();
}
}
}
}
// 経路の接続
range = Connect();
Max = range;
// 出力（図）
if (display > 0) {
wn.Draw(1, -1, -1);
System.out.println(" 図を確認したらreturnキーを押してください");
in.readLine();
}
// 出力（文字）
Output(n_city);
}
/***********************/
/* 出力 */
/* n_c : 都市の数 */
/***********************/
void Output(int n_c) throws IOException, FileNotFoundException
{
int i1, k = 0, n;
String now;
PrintStream out = null;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
if (out_m <= 0) {
out = System.out;
out.println("距離 " + range);
in.readLine();
}
else {
Date newtime = new Date(); // 現在時刻の獲得
now = newtime.toString(); // 文字列への変換
out = new PrintStream(new FileOutputStream(o_file, true));
if (n_c > 0) {
System.out.println("距離 " + range);
out.println(" 距離 " + range + " 時間 " + now);
}
else
out.println("問題 " + i_file + " 乱数 " + seed + " 分割 " + n_p_x +
" " + n_p_y + " 時間 " + now);
}
if (n_c > 0 && (out_m == 0 || out_m == 1)) {
for (i1 = 0; i1 < n_c; i1++) {
n = seq_w1[i1];
if (seisu > 0)
out.println(" " + n + " " + (int)city[n][0] + " " + (int)city[n][1]);
else
out.println(" " + n + " " + city[n][0] + " " + city[n][1]);
if (out_m == 0) {
k++;
if (k == 10) {
in.readLine();
k = 0;
}
}
}
}
if (out_m > 0)
out.close();
}
/************************/
/* 分割された領域の接続 */
/************************/
int Connect() throws IOException
{
double wd, wd1, wa1, wa2, min = 0;
int i1, i2, i3, i4, k, k1 = 0, k2 = 0, k3 = 0, k4 = 0, min_c = 0, n, r,
r1 = 0, r2 = 0, r3 = 0, r4 = 0, s1 = 0, s2 = 0, sw = 1;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
/*
領域が１つの場合
*/
if (n_p_x == 1 && n_p_y == 1) {
for (i1 = 0; i1 < n_seq[0][0]; i1++)
seq_w1[i1] = seq[0][0][i1];
}
/*
領域が複数の場合
*/
else {
while (sw > 0) {
// 最小節点領域
min_c = n_city;
sw = 0;
for (i1 = 0; i1 < n_p_y; i1++) {
for (i2 = 0; i2 < n_p_x; i2++) {
if (state[i1][i2] == 0 && n_seq[i1][i2] < min_c) {
sw = 1;
r1 = i1;
r2 = i2;
min_c = n_seq[i1][i2];
}
}
}
// 結合する対象領域の決定
if (sw > 0) {
sw = 0;
for (i1 = 0; i1 < n_p_y; i1++) {
for (i2 = 0; i2 < n_p_x; i2++) {
if (state[i1][i2] == 0 && (i1 != r1 || i2 !=r2)) {
// 節点の数＞２
if (n_seq[r1][r2] > 1) {
for (i3 = 0; i3 < n_seq[r1][r2]; i3++) {
k1 = seq[r1][r2][i3];
k2 = (i3 == n_seq[r1][r2]-1) ? seq[r1][r2][0] :
seq[r1][r2][i3+1];
wd1 = rg[k1][k2];
for (i4 = 0; i4 < n_seq[i1][i2]; i4++) {
k3 = seq[i1][i2][i4];
k4 = (i4 == n_seq[i1][i2]-1) ? seq[i1][i2][0] :
seq[i1][i2][i4+1];
wd = wd1 + rg[k3][k4];
wa1 = rg[k1][k3] + rg[k2][k4];
wa2 = rg[k1][k4] + rg[k2][k3];
if (sw == 0 || wa1-wd < min) {
min = wa1 - wd;
r3 = i1;
r4 = i2;
s1 = (i3 == n_seq[r1][r2]-1) ? 0 : i3 + 1;
s2 = (i4 == n_seq[i1][i2]-1) ? 0 : i4 + 1;
sw = -1;
}
if (sw == 0 || wa2-wd < min) {
min = wa2 - wd;
r3 = i1;
r4 = i2;
s1 = i3;
s2 = (i4 == n_seq[i1][i2]-1) ? 0 : i4 + 1;
sw = 1;
}
}
}
}
// 節点の数＝１
else {
k1 = seq[r1][r2][0];
if (n_seq[i1][i2] > 1) {
for (i4 = 0; i4 < n_seq[i1][i2]; i4++) {
k3 = seq[i1][i2][i4];
k4 = (i4 == n_seq[i1][i2]-1) ? seq[i1][i2][0] :
seq[i1][i2][i4+1];
wd = rg[k3][k4];
wa1 = rg[k1][k3] + rg[k1][k4];
if (sw == 0 || wa1-wd < min) {
min = wa1 - wd;
r3 = i1;
r4 = i2;
s1 = 0;
s2 = (i4 == n_seq[i1][i2]-1) ? 0 : i4 + 1;
sw = 1;
}
}
}
else {
k3 = seq[i1][i2][0];
wa1 = rg[k1][k3];
if (sw == 0 || wa1 < min) {
min = wa1;
r3 = i1;
r4 = i2;
s1 = 0;
s2 = 0;
sw = 1;
}
}
}
}
}
}
// 領域の結合
seq_w1[0] = seq[r1][r2][s1];
k = 1;
n = s2;
for (i1 = 0; i1 < n_seq[r3][r4]; i1++) {
seq_w1[k] = seq[r3][r4][n];
k++;
n++;
if (n > n_seq[r3][r4]-1)
n = 0;
}
if (sw > 0) {
n = s1 + 1;
for (i1 = 0; i1 < n_seq[r1][r2]-1; i1++) {
if (n > n_seq[r1][r2]-1)
n = 0;
seq_w1[k] = seq[r1][r2][n];
k++;
n++;
}
}
else {
n = s1 - 1;
for (i1 = 0; i1 < n_seq[r1][r2]-1; i1++) {
if (n < 0)
n = n_seq[r1][r2] - 1;
seq_w1[k] = seq[r1][r2][n];
k++;
n--;
}
}
// 状態の変更
n_seq[r1][r2] += n_seq[r3][r4];
state[r3][r4] = 1;
for (i1 = 0; i1 < n_seq[r1][r2]; i1++)
seq[r1][r2][i1] = seq_w1[i1];
sw = 1;
// 結果の図示
if (display == 3) {
wn.Draw(0, r1, r2);
System.out.println(" 図を確認したらreturnキーを押してください");
in.readLine();
}
}
}
}
r = (seisu > -2) ? (int)Iteration.kyori(n_city, seq_w1, rg) :
(int)(Iteration.kyori(n_city, seq_w1, rg) + 0.5);
return r;
}
}
------------------------クラスIteration-----------
/*************************/
/* クラスIterationの定義 */
/*************************/
import java.io.*;
import java.util.Random;
import java.util.Date;
class Iteration {
private float [][] rg; // 都市間の距離
private int fix; // =1 : 近傍を固定
// =0 : 近傍を可変
private int max_try; // 最大試行回数
private int neib; // 近傍（2 or 3）
private int out_d; // 表示間隔
private int [] seq_w1; // 都市を訪れる順序（ワーク）
private int [] seq_w2; // 都市を訪れる順序（ワーク）
private int [] seq_w3; // 都市を訪れる順序（ワーク）
private int [] seq_w4; // 都市を訪れる順序（ワーク）
private int [] seq_w5; // 都市を訪れる順序（ワーク）
private int out_lvl; // 出力レベル
// =0 : 最終出力だけ
// n>0 : ｎ世代毎に出力（負の時はファイル）
private int out_m; // 出力方法
// =-1 : 出力しない
// =0 : すべてを出力
// =1 : 評価値だけを出力（最終結果だけはすべてを出力）
int seisu; // 位置データの表現方法
// =1 : 整数
// =-1 : 実数（距離を整数計算）
// =-2 : 実数（距離を実数計算）
private int sel; // エッジの選択方法
// =0 : 最良のものを選択
// =1 : 最初のものを選択
private String o_file; // 出力ファイル名
private Win_it wn; // Win_itオブジェクト
private Random rn; // 乱数
double range; // 現在の評価値
float [][] city; //都市の位置データ
int n_city; // 都市の数
int n_tri; // 試行回数
int [] seq; // 都市を訪れる順序
int n_eg; // 交換した枝の数
int [] eg; // 交換した枝
int display; // 画面表示
// =0 : 画面表示を行わない
// =1 : 結果だけを表示
// =2 : 初期状態と結果を表示
// =3 : ワンステップ毎表示
/**********************************/
/* コンストラクタ */
/* n_city_i : 都市の数 */
/* max_try_i : 最大試行回数 */
/* sei_i : 整数 or 実数 */
/* sel_i : エッジの選択方法 */
/* neib_i : 近傍（2 or 3） */
/* fix_i : 近傍の扱い方 */
/* out_lvl_i : 出力レベル */
/* out_m_i : 出力方法 */
/* out_d_i : 表示間隔 */
/* o_file_i : 出力ファイル名 */
/* city_i : 都市の位置データ */
/* display_i : 画面表示 */
/* rn_i : 乱数 */
/**********************************/
Iteration (int n_city_i, int max_tri_i, int sei_i, int sel_i, int neib_i,
int fix_i, int out_lvl_i, int out_m_i, int out_d_i, String o_file_i,
float [][] city_i, int display_i, Random rn_i)
{
double x, y;
int ct, i1, i2, sw;
// 値の設定
n_city = n_city_i;
max_try = max_tri_i;
seisu = sei_i;
sel = sel_i;
neib = neib_i;
fix = fix_i;
out_lvl = out_lvl_i;
out_m = out_m_i;
out_d = out_d_i;
o_file = o_file_i;
display = display_i;
rn = rn_i;
n_tri = 0;
n_eg = 0;
eg = new int [6];
// 都市の位置データ
city = new float [n_city][2];
for (i1 = 0; i1 < n_city; i1++) {
city[i1][0] = city_i[i1][0];
city[i1][1] = city_i[i1][1];
}
// 距離テーブルの作成
rg = new float [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] = (float)Math.sqrt(x * x + y * y);
if (seisu > -2)
rg[i1][i2] = (int)(rg[i1][i2] + 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];
seq_w3 = new int [n_city];
seq_w4 = new int [n_city];
seq_w5 = 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;
}
}
}
}
/****************/
/* 最適化の実行 */
/****************/
int Optimize () throws IOException, FileNotFoundException
{
int 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) {
if (seisu > -2)
System.out.println("***試行回数 " + n_tri + " 距離 " + (int)range);
else
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) {
if (seisu > -2)
System.out.println("***試行回数 " + n_tri + " 距離 " + (int)range);
else
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--;
if (seisu > -2)
System.out.println("***試行回数 " + n_tri + " 距離 " + (int)range);
else
System.out.println("***試行回数 " + n_tri + " 距離 " + (int)(range+0.5));
Output(out_lvl);
}
}
// ワンステップづつ実行する場合
else {
// 初期設定
range = kyori(n_city, seq, rg);
// 初期状態の出力（図）
wn.Draw();
System.out.println(" 図を確認したらreturnキーを押してください");
in.readLine();
// 初期状態の出力（文字）
if (out_m >= 0 && Math.abs(out_lvl) > 0) {
if (seisu > -2)
System.out.println("***試行回数 " + n_tri + " 距離 " + (int)range);
else
System.out.println("***試行回数 " + n_tri + " 距離 " + range);
Output(out_lvl);
}
// マウスによる実行
System.out.print("\n終了したらreturnキーを押してください\n");
in.readLine();
// 最終出力（文字）
if (out_m >= 0) {
if (seisu > -2)
System.out.println("***試行回数 " + n_tri + " 距離 " + (int)range);
else
System.out.println("***試行回数 " + n_tri + " 距離 " + (int)(range+0.5));
Output(out_lvl);
}
}
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));
if (seisu > -2)
out.println("***試行回数 " + n_tri + " 距離 " + (int)range + " 時間 " + now);
else
out.println("***試行回数 " + n_tri + " 距離 " + (int)(range+0.5) +
" 時間 " + now);
}
if (out_m == 0) {
for (i1 = 0; i1 < n_city; i1++) {
n = seq[i1];
if (seisu > 0)
out.println(" " + n + " " + (int)city[n][0] + " " + (int)city[n][1]);
else
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()
{
double max, max1 = 0.0, r;
int ch = 0, i0, i1, i2, i3, i4, k, k1 = 0, k2 = 0, k3, k4,
n, nn, n1 = 0, n2 = 0, n3, n4, sw = 0, sw1 = 0, sw2;
max = range;
/*
近傍を可変
*/
if (fix == 0) {
// 初期設定（ｋ＝２）
k = 2;
for (i1 = 0; i1 < n_city; i1++) {
seq_w4[i1] = seq[i1];
seq_w3[i1] = 0;
}
// 評価
sw2 = 0;
for (i0 = 0; i0 < n_city-2 && sw2 < 2; i0++) {
n = (i0 == 0) ? n_city-1 : n_city;
for (i1 = i0+2; i1 < n && sw2 < 2; i1++) {
// 相手の場所
k3 = i1;
k4 = k3 + 1;
if (k4 > n_city-1)
k4 = 0;
// 順番の入れ替え
n3 = -1;
for (i2 = 0; i2 < n_city && n3 < 0; i2++) {
if (seq_w4[i2] == seq[i0+1])
n3 = i2 + 1;
}
nn = n3;
n4 = -1;
for (i2 = 0; i2 < n_city && n4 < 0; i2++) {
if (nn > n_city-1)
nn = 0;
if (seq_w4[nn] == seq[k3] || seq_w4[nn] == seq[k4])
n4 = seq_w4[nn];
else
nn++;
}
if (n4 == seq[k4]) {
n4 = k3;
k3 = k4;
k4 = n4;
}
// 評価
seq_w1[0] = seq[k4];
seq_w1[1] = seq[i0+1];
n4 = -1;
nn = 2;
while (n4 < 0) {
if (n3 > n_city-1)
n3 = 0;
seq_w1[nn] = seq_w4[n3];
if (seq_w4[n3] == seq[k3])
n4 = 1;
nn++;
n3++;
}
seq_w1[nn] = seq[i0];
nn++;
n3 = -1;
n4 = -1;
for (i2 = 0; i2 < n_city && n3 < 0; i2++) {
if (seq_w4[i2] == seq[i0]) {
n3 = i2 - 1;
if (n3 < 0)
n3 = n_city - 1;
}
}
while (n4 < 0) {
if (seq_w4[n3] == seq[k4])
n4 = 1;
else {
seq_w1[nn] = seq_w4[n3];
nn++;
n3--;
if (n3 < 0)
n3 = n_city - 1;
}
}
r = kyori(n_city, seq_w1, rg);
// 最適値の保存
if (sw2 == 0 || r < max1) {
sw2 = 1;
max1 = r;
n1 = k3;
n2 = k4;
k1 = i0;
k2 = i0 + 1;
for (i2 = 0; i2 < n_city; i2++)
seq_w5[i2] = seq_w1[i2];
if (sel > 0 && max1 < max)
sw2 = 2;
}
}
}
// 最適値の保存と近傍の増加
if (sw2 > 0) {
if (max1 < max) {
sw = 1;
max = max1;
for (i1 = 0; i1 < n_city; i1++)
seq_w2[i1] = seq_w5[i1];
}
if (k < neib) {
for (i1 = 0; i1 < n_city; i1++)
seq_w4[i1] = seq_w5[i1];
seq_w3[k1] = 1;
seq_w3[k2] = 1;
seq_w3[n1] = 1;
seq_w3[n2] = 1;
k1 = n2;
k++;
}
else
sw1 = 1;
}
else
sw1 = 1;
// 実行（ｋ＞２）
while (sw1 == 0) {
// 評価
sw2 = 0;
for (i1 = 0; i1 < n_city; i1++) {
// 相手の場所
k3 = i1;
k4 = k3 + 1;
if (k4 > n_city-1)
k4 = 0;
if (seq_w3[k3] == 0 && seq_w3[k4] == 0) {
// 順番の入れ替え
n3 = -1;
for (i2 = 0; i2 < n_city && n3 < 0; i2++) {
if (seq_w4[i2] == seq[k2])
n3 = i2 + 1;
}
nn = n3;
n4 = -1;
for (i2 = 0; i2 < n_city && n4 < 0; i2++) {
if (nn > n_city-1)
nn = 0;
if (seq_w4[nn] == seq[k3] || seq_w4[nn] == seq[k4])
n4 = seq_w4[nn];
else
nn++;
}
if (n4 == seq[k4]) {
n4 = k3;
k3 = k4;
k4 = n4;
}
// 評価
seq_w1[0] = seq[k4];
seq_w1[1] = seq[k2];
n4 = -1;
nn = 2;
while (n4 < 0) {
if (n3 > n_city-1)
n3 = 0;
seq_w1[nn] = seq_w4[n3];
if (seq_w4[n3] == seq[k3])
n4 = 1;
nn++;
n3++;
}
seq_w1[nn] = seq[k1];
nn++;
n3 = -1;
n4 = -1;
for (i2 = 0; i2 < n_city && n3 < 0; i2++) {
if (seq_w4[i2] == seq[k1]) {
n3 = i2 - 1;
if (n3 < 0)
n3 = n_city - 1;
}
}
while (n4 < 0) {
if (seq_w4[n3] == seq[k4])
n4 = 1;
else {
seq_w1[nn] = seq_w4[n3];
nn++;
n3--;
if (n3 < 0)
n3 = n_city - 1;
}
}
r = kyori(n_city, seq_w1, rg);
// 最適値の保存
if (sw2 == 0 || r < max1) {
sw2 = 1;
max1 = r;
n1 = k3;
n2 = k4;
for (i2 = 0; i2 < n_city; i2++)
seq_w5[i2] = seq_w1[i2];
}
}
}
// 最適値の保存と近傍の増加
if (sw2 > 0) {
if (max1 < max) {
sw = 1;
max = max1;
for (i1 = 0; i1 < n_city; i1++)
seq_w2[i1] = seq_w5[i1];
}
if (k < neib) {
for (i1 = 0; i1 < n_city; i1++)
seq_w4[i1] = seq_w5[i1];
seq_w3[n1] = 1;
seq_w3[n2] = 1;
k1 = n2;
k++;
}
else
sw1 = 1;
}
else
sw1 = 1;
}
}
/*
近傍を固定
*/
else {
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 float kyori(int n_c, int [] p, float [][] rg)
{
float range = 0;
int i1, n1, n2;
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_pt--------------
/**********************/
/* クラスWin_ptの定義 */
/**********************/
import java.awt.*;
import java.awt.event.*;
class Win_pt extends Frame {
double ritu; // 表示倍率
private float min_x, max_x, min_y, max_y; // 都市の存在範囲
private int font; // フォントサイズ
private int next, yoyu_x, yoyu_y; // 表示位置
private int r_sw; // 距離表示の有無
private int c_x, c_y; // 現在の対象領域
private Partition pt;
/*************************************/
/* コンストラクタ */
/* pt : Partitionのオブジェクト */
/* city_i : 都市の位置データ */
/* font_i : フォントサイズ */
/* width,height : 表示範囲 */
/*************************************/
Win_pt (Partition pt_i, int font_i, int width, int height)
{
// Frameクラスのコンストラクタの呼び出し
super("巡回セールスマン問題");
// 値の設定と領域の確保
double k1, k2;
int i1;
pt = pt_i;
font = font_i;
next = 70;
yoyu_x = 30;
yoyu_y = 80;
// 描画領域の計算
min_x = pt.city[0][0];
max_x = pt.city[0][0];
min_y = pt.city[0][1];
max_y = pt.city[0][1];
for (i1 = 1; i1 < pt.n_city; i1++) {
if (pt.city[i1][0] < min_x)
min_x = pt.city[i1][0];
else {
if (pt.city[i1][0] > max_x)
max_x = pt.city[i1][0];
}
if (pt.city[i1][1] < min_y)
min_y = pt.city[i1][1];
else {
if (pt.city[i1][1] > max_y)
max_y = pt.city[i1][1];
}
}
k1 = (double)(width - 2 * yoyu_x) / (max_x - min_x);
if (pt.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サイズ
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());
}
/********************************/
/* 描画指示 */
/* sw : 距離表示の有無 */
/* c_y_i, c_x_i : 対象領域 */
/********************************/
void Draw(int sw, int c_y_i, int c_x_i)
{
r_sw = sw;
c_y = c_y_i;
c_x = c_x_i;
repaint();
}
/********/
/* 描画 */
/********/
public void paint (Graphics g)
{
int i1, i2, i3, k, n1, n2, size = 6, x1, x2, y1, y2;
Font f;
// 距離の表示
if (r_sw > 0) {
f = new Font("TimesRoman", Font.BOLD, 25);
g.setFont(f);
if (pt.seisu > -2)
g.drawString("Length : "+Integer.toString((int)pt.range), yoyu_x, yoyu_y-30);
else
g.drawString("Length : "+Integer.toString((int)(pt.range+0.5)), 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 < pt.n_p_y; i1++) {
for (i2 = 0; i2 < pt.n_p_x; i2++) {
if (pt.state[i1][i2] == 0) {
if (i1 == c_y && i2 == c_x)
g.setColor(Color.red);
else
g.setColor(Color.black);
for (i3 = 0; i3 < pt.n_seq[i1][i2]; i3++) {
n2 = pt.seq[i1][i2][i3];
x2 = yoyu_x + (int)(ritu * (pt.city[n2][0] - min_x));
y2 = yoyu_y + (int)(ritu * (max_y - pt.city[n2][1]));
g.fillOval(x2, y2, size, size);
if (font > 0)
g.drawString(Integer.toString(n2), x2+k, y2-k);
if (i3 > 0) {
n1 = pt.seq[i1][i2][i3-1];
x1 = yoyu_x + (int)(ritu * (pt.city[n1][0] - min_x));
y1 = yoyu_y + (int)(ritu * (max_y - pt.city[n1][1]));
g.drawLine(x1+k, y1+k, x2+k, y2+k);
if (i3 == pt.n_seq[i1][i2]-1) {
n1 = pt.seq[i1][i2][0];
x1 = yoyu_x + (int)(ritu * (pt.city[n1][0] - min_x));
y1 = yoyu_y + (int)(ritu * (max_y - pt.city[n1][1]));
g.drawLine(x1+k, y1+k, x2+k, y2+k);
}
}
}
}
}
}
}
/************/
/* 終了処理 */
/************/
class WinEnd extends WindowAdapter
{
public void windowClosing(WindowEvent e) {
System.exit(0);
}
}
}
------------------------クラスWin_it--------------
/**********************/
/* クラスWin_itの定義 */
/**********************/
import java.awt.*;
import java.awt.event.*;
class Win_it extends Frame {
double ritu; // 表示倍率
private float min_x, max_x, min_y, max_y; // 都市の存在範囲
private int font; // フォントサイズ
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);
if (it.seisu > -2)
g.drawString("Length : "+Integer.toString((int)it.range), yoyu_x, yoyu_y-30);
else
g.drawString("Length : "+Integer.toString((int)(it.range+0.5)), 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
{
double mean;
int i0, i1, n, nm, seed, max;
String i_file, line;
Partition pt;
StringTokenizer dt;
PrintStream out = null;
BufferedReader in = new BufferedReader(new FileReader(args[0]));
// 入力ミス
if (args.length == 0) {
System.out.print("***error ファイル名を入力して下さい\n");
System.exit(1);
}
// 入力ＯＫ
else {
// 入力データファイル名と問題数
line = in.readLine();
dt = new StringTokenizer(line, " ");
dt.nextToken();
nm = Integer.parseInt(dt.nextToken());
for (i0 = 0; i0 < nm; i0++) {
// 各問題の実行
line = in.readLine();
dt = new StringTokenizer(line, " ");
dt.nextToken();
i_file = dt.nextToken();
dt.nextToken();
n = Integer.parseInt(dt.nextToken());
pt = new Partition(i_file);
mean = 0.0;
max = -1;
// 乱数の初期値を変える
for (i1 = 0; i1 < n; i1++) {
line = in.readLine();
dt = new StringTokenizer(line, " ");
dt.nextToken();
seed = Integer.parseInt(dt.nextToken());
System.out.println("\n+++++問題 " + i_file + " 乱数 " + seed + "+++++");
// 最適化
pt.Optimize(seed);
// 最適値とその平均の計算
mean += pt.Max;
if (max < 0 || pt.Max < max)
max = pt.Max;
}
// 結果
if (pt.out_m <= 0)
System.out.println(" -----最小 " + max + " 平均 " + mean/n + "-----");
else {
out = new PrintStream(new FileOutputStream(pt.o_file, true));
out.println(" -----最小 " + max + " 平均 " + mean/n + "-----");
out.close();
}
}
in.close();
}
}
}
問題の数 2 問題 data/pr439.tsp 乱数の数 10 乱数 1 乱数 12 ・・・ 問題 data/kroA100.tsp 乱数の数 10 乱数 1 乱数 12 ・・・
都市の数 439 選択方法(0:最良，1:最初) 1 近傍（2or3） 3 整数 1
出力(0:ディスプレイ，1:ファイル) -1 出力ファイル名 result/pr439
分割数 Ｘ 4 Ｙ 3 最大試行回数 1000
図示(0:しない，1:結果，2:初期状態と結果，3:ステップ) 3
都市番号 0 図の大きさ（幅，高さ） 1000 750
7125 11300
7225 11050
･････