| 情報学部 | 菅沼ホーム | 目次 | 索引 |
/****************************/
/* 巡回セールスマン問題 */
/* 反復改善法 */
/* 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 : ｎ回毎に出力（負の時はファイル）
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:画面にｎ個づつ，-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;
// ２近傍
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;
}
// ３近傍
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;
}
// 入れ替え（その２）
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;
}
// 入れ替え（その３）
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;
}
// 入れ替え（その４）
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;
}
}
}
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);
}
// 入力ＯＫ
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
*/
/****************************/
/* 巡回セールスマン問題 */
/* 反復改善法 */
/* 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 : ｎ回毎に出力（負の時はファイル）
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の定義 */
/**********************/
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);
}
// 入力ＯＫ
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
*/
<?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 : ｎ回毎に出力（負の時はファイル）
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:画面にｎ個づつ，-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;
// ２近傍
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;
}
// ３近傍
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;
// 枝の入れ替えと評価
// 入れ替え（その１）
$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;
}
// 評価（その１）
$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;
}
// 入れ替え（その２）
$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;
}
// 評価（その２）
$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;
}
// 入れ替え（その３）
$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;
}
// 評価（その３）
$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;
}
// 入れ替え（その４）
$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;
}
// 評価（その４）
$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");
// 入力ＯＫ
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
*/
?>
####################################
# 巡回セールスマン問題（反復改善法）
# 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 ｎ回毎に出力（負の時はファイル）
@_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:画面にｎ個づつ，-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
# ２近傍
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
# ３近傍
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
# 枝の入れ替えと評価
# 入れ替え（その１）
@_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
# 評価（その１）
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
# 入れ替え（その２）
@_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
# 評価（その２）
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
# 入れ替え（その３）
@_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
# 評価（その３）
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
# 入れ替え（その４）
@_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
# 評価（その４）
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")
# 入力ＯＫ
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
# -*- 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 : ｎ回毎に出力（負の時はファイル）
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:画面にｎ個づつ，-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
# ２近傍
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
# ３近傍
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
# 枝の入れ替えと評価
# 入れ替え（その１）
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
# 評価（その１）
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
# 入れ替え（その２）
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
# 評価（その２）
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
# 入れ替え（その３）
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
# 評価（その３）
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
# 入れ替え（その４）
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
# 評価（その４）
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 ファイル名を入力して下さい")
# 入力ＯＫ
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
"""
/****************************/
/* 巡回セールスマン問題 */
/* 反復改善法 */
/* 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 : ｎ回毎に出力（負の時はファイル）
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:画面にｎ個づつ，-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;
// ２近傍
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;
}
// ３近傍
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;
}
// 入れ替え（その２）
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;
}
// 入れ替え（その３）
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;
}
// 入れ替え（その４）
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;
}
}
}
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 ケーススタディファイル名を入力して下さい");
// 入力ＯＫ
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
*/
'**************************'
' 巡回セールスマン問題 '
' 反復改善法 '
' 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 ケーススタディファイル名を入力して下さい")
' 入力ＯＫ
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 : ｎ回毎に出力（負の時はファイル）
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:画面にｎ個づつ，-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
' ２近傍
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
' ３近傍
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
' 枝の入れ替えと評価
' 入れ替え（その１）
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
' 評価（その１）
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
' 入れ替え（その２）
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
' 評価（その２）
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
' 入れ替え（その３）
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
' 評価（その３）
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
' 入れ替え（その４）
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
' 評価（その４）
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
*/
| 情報学部 | 菅沼ホーム | 目次 | 索引 |