<?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
*/
?>