<?php
/****************************/
/* 巡回セールスマン問題 */
/* （分割法） */
/* coded by Y.Suganuma */
/****************************/
/*************************/
/* クラスPartitionの定義 */
/*************************/
class Partition {
private $city; //都市の位置データ
private $city_i; //都市の位置データ（作業領域）
private $p_x; // ｘ軸の分割点
private $p_y; // ｙ軸の分割点
private $rg; // 都市間の距離
private $seed; // 乱数の初期値
private $fix; // =1 : 近傍を固定
// =0 : 近傍を可変
private $max_try; // 最大試行回数
private $n_city; // 都市の数
private $n_seq; // 各領域の都市数
private $n_seq1; // 各領域の都市数（ワーク）
private $n_p_x; // ｘ軸方向の分割数
private $n_p_y; // ｙ軸方向の分割数
private $seq; // 経路
private $seq1; // 経路（ワーク）
private $seq_w1; // 作業領域
private $seq_w2; // 作業領域
private $neib; // 近傍（2 or 3）
private $seisu; // 位置データの表現方法
// =1 : 整数
// =-1 : 実数（距離を整数計算）
// =-2 : 実数（距離を実数計算）
private $sel; // エッジの選択方法
// =0 : 最良のものを選択
// =1 : 最初のものを選択
private $state; // 領域結合用ワーク
private $i_file; // 入力ファイル名
public $Max; // 最適経路の長さ
public $out_m; // 出力方法
// =-1 : ディスプレイ（経路長だけ）
// =0 : ディスプレイ
// =1 : ファイル
// =2 : ファイル（経路長だけ）
public $o_file; // 出力ファイル名
/**************************/
/* コンストラクタ */
/* name : ファイル名 */
/**************************/
function Partition($name)
{
$max = 0;
// ファイルのオープン
$this->i_file = $name;
$in = fopen($name, "r");
if ($in == NULL)
exit("***error データファイル名が不適当\n");
// 基本データ
fscanf($in, "%*s %d %*s %d %*s %d %*s %d", $this->n_city, $this->sel, $this->neib, $this->seisu);
fscanf($in, "%*s %d %*s %s", $this->out_m, $this->o_file);
fscanf($in, "%*s %*s %d %*s %d %*s %d", $this->n_p_x, $this->n_p_y, $this->max_try);
if ($this->neib < 0) {
$this->neib = -$this->neib;
$this->fix = 0;
}
else
$this->fix = 1;
// 都市の位置データ
$this->city = array($this->n_city);
for ($i1 = 0; $i1 < $this->n_city; $i1++) {
$this->city[$i1] = array(2);
fscanf($in, "%f %f", $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] = sqrt($x * $x + $y * $y);
if ($this->seisu > -2)
$this->rg[$i1][$i2] = round($this->rg[$i1][$i2]);
}
}
for ($i1 = 1; $i1 < $this->n_city; $i1++) {
for ($i2 = 0; $i2 < $i1; $i2++)
$this->rg[$i1][$i2] = $this->rg[$i2][$i1];
}
// 作業領域
$this->state = array($this->n_p_y);
$this->n_seq = array($this->n_p_y);
$this->n_seq1 = array($this->n_p_y);
for ($i1 = 0; $i1 < $this->n_p_y; $i1++) {
$this->n_seq[$i1] = array($this->n_p_x);
$this->n_seq1[$i1] = array($this->n_p_x);
$this->state[$i1] = array($this->n_p_x);
}
$this->seq = array($this->n_p_y);
$this->seq1 = array($this->n_p_y);
for ($i1 = 0; $i1 < $this->n_p_y; $i1++) {
$this->seq[$i1] = array($this->n_p_x);
$this->seq1[$i1] = array($this->n_p_x);
}
$this->seq_w1 = array($this->n_city);
$this->seq_w2 = array($this->n_city);
$this->p_x = array($this->n_p_x);
$this->p_y = array($this->n_p_y);
// 都市の分割
for ($i1 = 0; $i1 < $this->n_city; $i1++)
$this->seq_w1[$i1] = 0;
$min_x = $this->city[0][0];
$max_x = $this->city[0][0];
$min_y = $this->city[0][1];
$max_y = $this->city[0][1];
for ($i1 = 1; $i1 < $this->n_city; $i1++) {
if ($this->city[$i1][0] < $min_x)
$min_x = $this->city[$i1][0];
else {
if ($this->city[$i1][0] > $max_x)
$max_x = $this->city[$i1][0];
}
if ($this->city[$i1][1] < $min_y)
$min_y = $this->city[$i1][1];
else {
if ($this->city[$i1][1] > $max_y)
$max_y = $this->city[$i1][1];
}
}
$s_x = ($max_x - $min_x) / $this->n_p_x;
$this->p_x[0] = $min_x + $s_x;
$this->p_x[$this->n_p_x-1] = $max_x;
for ($i1 = 1; $i1 < $this->n_p_x-1; $i1++)
$this->p_x[$i1] = $this->p_x[0] + $i1 * $s_x;
$s_y = ($max_y - $min_y) / $this->n_p_y;
$this->p_y[0] = $min_y + $s_y;
$this->p_y[$this->n_p_y-1] = $max_y;
for ($i1 = 1; $i1 < $this->n_p_y-1; $i1++)
$this->p_y[$i1] = $this->p_y[0] + $i1 * $s_y;
for ($i1 = 0; $i1 < $this->n_p_y; $i1++) {
for ($i2 = 0; $i2 < $this->n_p_x; $i2++) {
$n = 0;
for ($i3 = 0; $i3 < $this->n_city; $i3++) {
if ($this->seq_w1[$i3] == 0) {
if ($this->city[$i3][0] <= $this->p_x[$i2] && $this->city[$i3][1] <= $this->p_y[$i1]) {
$this->seq_w1[$i3] = 1;
$this->seq_w2[$n] = $i3;
$n++;
}
}
}
$this->n_seq1[$i1][$i2] = $n;
if ($n > 0) {
$this->seq[$i1][$i2] = array($this->n_city);
$this->seq1[$i1][$i2] = array($this->n_city);
for ($i3 = 0; $i3 < $n; $i3++)
$this->seq1[$i1][$i2][$i3] = $this->seq_w2[$i3];
if ($n > $max)
$max = $n;
}
}
}
// 作業領域
printf("最大都市数 %d\n", $max);
$this->city_i = array($max);
for ($i1 = 0; $i1 < $max; $i1++)
$this->city_i[$i1] = array(2);
}
/******************************/
/* 最適化の実行 */
/* seed_i : 乱数の初期値 */
/******************************/
function Optimize($seed_i)
{
$r = 0;
// 初期設定
$this->seed = $seed_i;
mt_srand($seed_i);
// 分割数と開始時間の出力
if ($this->out_m > 0)
$this->Output(0, $r);
for ($i1 = 0; $i1 < $this->n_p_y; $i1++) {
for ($i2 = 0; $i2 < $this->n_p_x; $i2++) {
$this->n_seq[$i1][$i2] = $this->n_seq1[$i1][$i2];
for ($i3 = 0; $i3 < $this->n_seq1[$i1][$i2]; $i3++)
$this->seq[$i1][$i2][$i3] = $this->seq1[$i1][$i2][$i3];
}
}
// 分割毎の最適化
for ($i1 = 0; $i1 < $this->n_p_y; $i1++) {
for ($i2 = 0; $i2 < $this->n_p_x; $i2++) {
if ($this->n_seq[$i1][$i2] > 3) {
// 近傍の大きさ
$nb = ($this->n_seq[$i1][$i2] > 3) ? $this->neib : 2;
// 都市位置データの設定
for ($i3 = 0; $i3 < $this->n_seq[$i1][$i2]; $i3++) {
$k = $this->seq[$i1][$i2][$i3];
$this->city_i[$i3][0] = $this->city[$k][0];
$this->city_i[$i3][1] = $this->city[$k][1];
}
// 最適化
$it = new Iteration ($this->n_seq[$i1][$i2], $this->max_try, $this->seisu, $this->sel, $nb, $this->fix, 0, -1, 0, $this->o_file, $this->city_i);
$max = $it->Optimize();
// 結果の保存
for ($i3 = 0; $i3 < $this->n_seq[$i1][$i2]; $i3++) {
$k = $it->seq[$i3];
$this->seq_w1[$i3] = $this->seq[$i1][$i2][$k];
}
for ($i3 = 0; $i3 < $this->n_seq[$i1][$i2]; $i3++)
$this->seq[$i1][$i2][$i3] = $this->seq_w1[$i3];
// 出力
$r = ($this->seisu > -2) ? intval(kyori($this->n_seq[$i1][$i2], $this->seq[$i1][$i2], $this->rg)) : round((kyori($this->n_seq[$i1][$i2], $this->seq[$i1][$i2], $this->rg)));
printf(" y %d x %d $this->n_city %d range %d (trial %d)\n",
$i1+1, $i2+1, $this->n_seq[$i1][$i2], $r, $max);
}
}
}
// 経路の接続
$r = $this->Connect();
// 出力
$this->Output($this->n_city, $r);
}
/***********************/
/* 出力 */
/* n_c : 都市の数 */
/* r : 距離 */
/***********************/
function Output($n_c, $r)
{
$k = 0;
if ($this->out_m <= 0) {
$out = STDOUT;
fwrite($out, "距離 ".$r."\n");
fgets(STDIN);
}
else {
$x = getdate();
$now = $x["hours"]."時".$x["minutes"]."分".$x["seconds"]."秒";
$out = fopen($this->o_file, "ab");
if ($n_c > 0) {
printf("距離 %d\n", $r);
fwrite($out, " 距離 ".$r." 時間 ".$now."\n");
}
else
fwrite($out, "問題 ".$this->i_file." 乱数 ".$this->seed." 分割 ".$this->n_p_x." ".$this->n_p_y." 時間 ".$now."\n");
}
if ($n_c > 0 && ($this->out_m == 0 || $this->out_m == 1)) {
for ($i1 = 0; $i1 < $n_c; $i1++) {
$n = $this->seq_w1[$i1];
if ($this->seisu > 0)
fwrite($out, " ".$n." ".intval($this->city[$n][0])." ".intval($this->city[$n][1])."\n");
else
fwrite($out, " ".$n." ".$this->city[$n][0]." ".$this->city[$n][1]."\n");
if ($this->out_m == 0) {
$k++;
if ($k == 10) {
fgets(STDIN);
$k = 0;
}
}
}
}
if ($this->out_m > 0)
fclose($out);
}
/************************/
/* 分割された領域の接続 */
/************************/
function Connect()
{
$min = 0;
$k1 = 0;
$k2 = 0;
$k3 = 0;
$k4 = 0;
$min_c = 0;
$r1 = 0;
$r2 = 0;
$r3 = 0;
$r4 = 0;
$s1 = 0;
$s2 = 0;
$sw = 1;
/*
領域が１つの場合
*/
if ($this->n_p_x == 1 && $this->n_p_y == 1) {
for ($i1 = 0; $i1 < $this->n_seq[0][0]; $i1++)
$this->seq_w1[$i1] = $this->seq[0][0][$i1];
}
/*
初期設定
*/
else {
for ($i1 = 0; $i1 < $this->n_p_y; $i1++) {
for ($i2 = 0; $i2 < $this->n_p_x; $i2++)
$this->state[$i1][$i2] = ($this->n_seq[$i1][$i2] > 0) ? 0 : 1;
}
/*
実行
*/
while ($sw > 0) {
// 最小節点領域
$min_c = $this->n_city;
$sw = 0;
for ($i1 = 0; $i1 < $this->n_p_y; $i1++) {
for ($i2 = 0; $i2 < $this->n_p_x; $i2++) {
if ($this->state[$i1][$i2] == 0 && $this->n_seq[$i1][$i2] < $min_c) {
$sw = 1;
$r1 = $i1;
$r2 = $i2;
$min_c = $this->n_seq[$i1][$i2];
}
}
}
// 結合する対象領域の決定
if ($sw > 0) {
$sw = 0;
for ($i1 = 0; $i1 < $this->n_p_y; $i1++) {
for ($i2 = 0; $i2 < $this->n_p_x; $i2++) {
if ($this->state[$i1][$i2] == 0 && ($i1 != $r1 || $i2 != $r2)) {
// 節点の数＞２
if ($this->n_seq[$r1][$r2] > 1) {
for ($i3 = 0; $i3 < $this->n_seq[$r1][$r2]; $i3++) {
$k1 = $this->seq[$r1][$r2][$i3];
$k2 = ($i3 == $this->n_seq[$r1][$r2]-1) ? $this->seq[$r1][$r2][0] : $this->seq[$r1][$r2][$i3+1];
$wd1 = $this->rg[$k1][$k2];
for ($i4 = 0; $i4 < $this->n_seq[$i1][$i2]; $i4++) {
$k3 = $this->seq[$i1][$i2][$i4];
$k4 = ($i4 == $this->n_seq[$i1][$i2]-1) ? $this->seq[$i1][$i2][0] : $this->seq[$i1][$i2][$i4+1];
$wd = $wd1 + $this->rg[$k3][$k4];
$wa1 = $this->rg[$k1][$k3] + $this->rg[$k2][$k4];
$wa2 = $this->rg[$k1][$k4] + $this->rg[$k2][$k3];
if ($sw == 0 || $wa1-$wd < $min) {
$min = $wa1 - $wd;
$r3 = $i1;
$r4 = $i2;
$s1 = ($i3 == $this->n_seq[$r1][$r2]-1) ? 0 : $i3 + 1;
$s2 = ($i4 == $this->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 == $this->n_seq[$i1][$i2]-1) ? 0 : $i4 + 1;
$sw = 1;
}
}
}
}
// 節点の数＝１
else {
$k1 = $this->seq[$r1][$r2][0];
if ($this->n_seq[$i1][$i2] > 1) {
for ($i4 = 0; $i4 < $this->n_seq[$i1][$i2]; $i4++) {
$k3 = $this->seq[$i1][$i2][$i4];
$k4 = ($i4 == $this->n_seq[$i1][$i2]-1) ? $this->seq[$i1][$i2][0] : $this->seq[$i1][$i2][$i4+1];
$wd = $this->rg[$k3][$k4];
$wa1 = $this->rg[$k1][$k3] + $this->rg[$k1][$k4];
if ($sw == 0 || $wa1-$wd < $min) {
$min = $wa1 - $wd;
$r3 = $i1;
$r4 = $i2;
$s1 = 0;
$s2 = ($i4 == $this->n_seq[$i1][$i2]-1) ? 0 : $i4 + 1;
$sw = 1;
}
}
}
else {
$k3 = $this->seq[$i1][$i2][0];
$wa1 = $this->rg[$k1][$k3];
if ($sw == 0 || $wa1 < $min) {
$min = $wa1;
$r3 = $i1;
$r4 = $i2;
$s1 = 0;
$s2 = 0;
$sw = 1;
}
}
}
}
}
}
// 領域の結合
$this->seq_w1[0] = $this->seq[$r1][$r2][$s1];
$k = 1;
$n = $s2;
for ($i1 = 0; $i1 < $this->n_seq[$r3][$r4]; $i1++) {
$this->seq_w1[$k] = $this->seq[$r3][$r4][$n];
$k++;
$n++;
if ($n > $this->n_seq[$r3][$r4]-1)
$n = 0;
}
if ($sw > 0) {
$n = $s1 + 1;
for ($i1 = 0; $i1 < $this->n_seq[$r1][$r2]-1; $i1++) {
if ($n > $this->n_seq[$r1][$r2]-1)
$n = 0;
$this->seq_w1[$k] = $this->seq[$r1][$r2][$n];
$k++;
$n++;
}
}
else {
$n = $s1 - 1;
for ($i1 = 0; $i1 < $this->n_seq[$r1][$r2]-1; $i1++) {
if ($n < 0)
$n = $this->n_seq[$r1][$r2] - 1;
$this->seq_w1[$k] = $this->seq[$r1][$r2][$n];
$k++;
$n--;
}
}
// 状態の変更
$this->n_seq[$r1][$r2] += $this->n_seq[$r3][$r4];
$this->state[$r3][$r4] = 1;
for ($i1 = 0; $i1 < $this->n_seq[$r1][$r2]; $i1++)
$this->seq[$r1][$r2][$i1] = $this->seq_w1[$i1];
$sw = 1;
}
}
}
$r = ($this->seisu > -2) ? intval(kyori($this->n_city, $this->seq_w1, $this->rg)) : round(kyori($this->n_city, $this->seq_w1, $this->rg));
$this->Max = $r;
return $r;
}
}
/*************************/
/* クラスIterationの定義 */
/*************************/
class Iteration {
private $city; //都市の位置データ
private $rg; // 都市間の距離
private $fix; // =1 : 近傍を固定
// =0 : 近傍を可変
private $max_try; // 最大試行回数
private $n_city; // 都市の数
private $out_d; // 表示間隔
private $seq_w1; // 都市を訪れる順序（ワーク）
private $seq_w2; // 都市を訪れる順序（ワーク）
private $seq_w3; // 都市を訪れる順序（ワーク）
private $seq_w4; // 都市を訪れる順序（ワーク）
private $seq_w5; // 都市を訪れる順序（ワーク）
private $neib; // 近傍（2 or 3）
private $out_lvl; // 出力レベル
// =0 : 最終出力だけ
// n>0 : ｎ世代毎に出力（負の時はファイル）
private $out_m; // 出力方法
// =-1 : 出力しない
// =0 : すべてを出力
// =1 : 評価値だけを出力（最終結果だけはすべてを出力）
private $seisu; // 位置データの表現方法
// =1 : 整数
// =-1 : 実数（距離を整数計算）
// =-2 : 実数（距離を実数計算）
private $sel; // エッジの選択方法
// =0 : 最良のものを選択
// =1 : 最初のものを選択
private $o_file; // 出力ファイル名
public $seq; // 都市を訪れる順序
/**********************************/
/* コンストラクタ */
/* n_city_i : 都市の数 */
/* max_try_i : 最大試行回数 */
/* sei_i : 整数 or 実数 */
/* sel_i : エッジの選択方法 */
/* neib_i : 近傍 */
/* fix_i : 近傍の扱い方 */
/* out_lvl_i : 出力レベル */
/* out_m_i : 出力方法 */
/* out_d_i : 表示間隔 */
/* o_file_i : 出力ファイル名 */
/* city_i : 都市の位置データ */
/**********************************/
function Iteration ($n_city_i, $max_tri_i, $sei_i, $sel_i, $neib_i, $fix_i, $out_lvl_i, $out_m_i, $out_d_i, $o_file_i, $city_i)
{
// 値の設定
$this->n_city = $n_city_i;
$this->max_try = $max_tri_i;
$this->seisu = $sei_i;
$this->sel = $sel_i;
$this->neib = $neib_i;
$this->fix = $fix_i;
$this->out_lvl = $out_lvl_i;
$this->out_m = $out_m_i;
$this->out_d = $out_d_i;
$this->o_file = $o_file_i;
// 都市の位置データ
$this->city = array($this->n_city);
for ($i1 = 0; $i1 < $this->n_city; $i1++) {
$this->city[$i1] = array(2);
$this->city[$i1][0] = $city_i[$i1][0];
$this->city[$i1][1] = $city_i[$i1][1];
}
// 距離テーブルの作成
$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] = sqrt($x * $x + $y * $y);
if ($this->seisu > -2)
$this->rg[$i1][$i2] = round($this->rg[$i1][$i2]);
}
}
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);
$this->seq_w3 = array($this->n_city);
$this->seq_w4 = array($this->n_city);
$this->seq_w5 = 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) {
if ($this->seisu > -2)
printf("***試行回数 %d 距離 %d\n", $n_tri, intval($max));
else
printf("***試行回数 %d 距離 %f\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) {
if ($this->seisu > -2)
printf("***試行回数 %d 距離 %d\n", $n_tri, intval($max));
else
printf("***試行回数 %d 距離 %f\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--;
if ($this->seisu > -2)
printf("***試行回数 %d 距離 %d\n", $n_tri, intval($max));
else
printf("***試行回数 %d 距離 %f\n", $n_tri, $max);
$this->Output($this->out_lvl, $n_tri, $max);
}
return $n_tri;
}
/*******************************/
/* 出力 */
/* sw : >=0 : 出力先未定 */
/* < 0 : ファイル */
/* n_tri : 現在の試行回数 */
/* r : 距離 */
/*******************************/
function Output($sw, $n_tri, $r)
{
$k = 0;
if ($sw >= 0) {
printf(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ ");
scanf(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");
if ($this->seisu > -2)
fwrite($out, "***試行回数 ".$n_tri." 距離 ".intval($r)." 時間 ".$now."\n");
else
fwrite($out, "***試行回数 ".$n_tri." 距離 ".round($r)." 時間 ".$now."\n");
}
if ($this->out_m == 0) {
for ($i1 = 0; $i1 < $this->n_city; $i1++) {
$n = $this->seq[$i1];
if ($this->seisu > 0)
fwrite($out, " ".$n." ".intval($this->city[$n][0])." ".intval($this->city[$n][1])."\n");
else
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(&$r_m)
{
$max1 = 0.0;
$ch = 0;
$k1 = 0;
$k2 = 0;
$n1 = 0;
$n2 = 0;
$sw = 0;
$sw1 = 0;
$max = $r_m;
/*
近傍を可変
*/
if ($this->fix == 0) {
// 初期設定（ｋ＝２）
$k = 2;
for ($i1 = 0; $i1 < $this->n_city; $i1++) {
$this->seq_w4[$i1] = $this->seq[$i1];
$this->seq_w3[$i1] = 0;
}
// 評価
$sw2 = 0;
for ($i0 = 0; $i0 < $this->n_city-2 && $sw2 < 2; $i0++) {
$n = ($i0 == 0) ? $this->n_city-1 : $this->n_city;
for ($i1 = $i0+2; $i1 < $n && $sw2 < 2; $i1++) {
// 相手の場所
$k3 = $i1;
$k4 = $k3 + 1;
if ($k4 > $this->n_city-1)
$k4 = 0;
// 順番の入れ替え
$n3 = -1;
for ($i2 = 0; $i2 < $this->n_city && $n3 < 0; $i2++) {
if ($this->seq_w4[$i2] == $this->seq[$i0+1])
$n3 = $i2 + 1;
}
$nn = $n3;
$n4 = -1;
for ($i2 = 0; $i2 < $this->n_city && $n4 < 0; $i2++) {
if ($nn > $this->n_city-1)
$nn = 0;
if ($this->seq_w4[$nn] == $this->seq[$k3] || $this->seq_w4[$nn] == $this->seq[$k4])
$n4 = $this->seq_w4[$nn];
else
$nn++;
}
if ($n4 == $this->seq[$k4]) {
$n4 = $k3;
$k3 = $k4;
$k4 = $n4;
}
// 評価
$this->seq_w1[0] = $this->seq[$k4];
$this->seq_w1[1] = $this->seq[$i0+1];
$n4 = -1;
$nn = 2;
while ($n4 < 0) {
if ($n3 > $this->n_city-1)
$n3 = 0;
$this->seq_w1[$nn] = $this->seq_w4[$n3];
if ($this->seq_w4[$n3] == $this->seq[$k3])
$n4 = 1;
$nn++;
$n3++;
}
$this->seq_w1[$nn] = $this->seq[$i0];
$nn++;
$n3 = -1;
$n4 = -1;
for ($i2 = 0; $i2 < $this->n_city && $n3 < 0; $i2++) {
if ($this->seq_w4[$i2] == $this->seq[$i0]) {
$n3 = $i2 - 1;
if ($n3 < 0)
$n3 = $this->n_city - 1;
}
}
while ($n4 < 0) {
if ($this->seq_w4[$n3] == $this->seq[$k4])
$n4 = 1;
else {
$this->seq_w1[$nn] = $this->seq_w4[$n3];
$nn++;
$n3--;
if ($n3 < 0)
$n3 = $this->n_city - 1;
}
}
$r = kyori($this->n_city, $this->seq_w1, $this->rg);
// 最適値の保存
if ($sw2 == 0 || $r < $max1) {
$sw2 = 1;
$max1 = $r;
$n1 = $k3;
$n2 = $k4;
$k1 = $i0;
$k2 = $i0 + 1;
for ($i2 = 0; $i2 < $this->n_city; $i2++)
$this->seq_w5[$i2] = $this->seq_w1[$i2];
if ($this->sel > 0 && $max1 < $max)
$sw2 = 2;
}
}
}
// 最適値の保存と近傍の増加
if ($sw2 > 0) {
if ($max1 < $max) {
$sw = 1;
$max = $max1;
for ($i1 = 0; $i1 < $this->n_city; $i1++)
$this->seq_w2[$i1] = $this->seq_w5[$i1];
}
if ($k < $this->neib) {
for ($i1 = 0; $i1 < $this->n_city; $i1++)
$this->seq_w4[$i1] = $this->seq_w5[$i1];
$this->seq_w3[$k1] = 1;
$this->seq_w3[$k2] = 1;
$this->seq_w3[$n1] = 1;
$this->seq_w3[$n2] = 1;
$k1 = $n2;
$k++;
}
else
$sw1 = 1;
}
else
$sw1 = 1;
// 実行（ｋ＞２）
while ($sw1 == 0) {
// 評価
$sw2 = 0;
for ($i1 = 0; $i1 < $this->n_city; $i1++) {
// 相手の場所
$k3 = $i1;
$k4 = $k3 + 1;
if ($k4 > $this->n_city-1)
$k4 = 0;
if ($this->seq_w3[$k3] == 0 && $this->seq_w3[$k4] == 0) {
// 順番の入れ替え
$n3 = -1;
for ($i2 = 0; $i2 < $this->n_city && $n3 < 0; $i2++) {
if ($this->seq_w4[$i2] == $this->seq[$k2])
$n3 = $i2 + 1;
}
$nn = $n3;
$n4 = -1;
for ($i2 = 0; $i2 < $this->n_city && $n4 < 0; $i2++) {
if ($nn > $this->n_city-1)
$nn = 0;
if ($this->seq_w4[$nn] == $this->seq[$k3] || $this->seq_w4[$nn] == $this->seq[$k4])
$n4 = $this->seq_w4[$nn];
else
$nn++;
}
if ($n4 == $this->seq[$k4]) {
$n4 = $k3;
$k3 = $k4;
$k4 = $n4;
}
// 評価
$this->seq_w1[0] = $this->seq[$k4];
$this->seq_w1[1] = $this->seq[$k2];
$n4 = -1;
$nn = 2;
while ($n4 < 0) {
if ($n3 > $this->n_city-1)
$n3 = 0;
$this->seq_w1[$nn] = $this->seq_w4[$n3];
if ($this->seq_w4[$n3] == $this->seq[$k3])
$n4 = 1;
$nn++;
$n3++;
}
$this->seq_w1[$nn] = $this->seq[$k1];
$nn++;
$n3 = -1;
$n4 = -1;
for ($i2 = 0; $i2 < $this->n_city && $n3 < 0; $i2++) {
if ($this->seq_w4[$i2] == $this->seq[$k1]) {
$n3 = $i2 - 1;
if ($n3 < 0)
$n3 = $this->n_city - 1;
}
}
while ($n4 < 0) {
if ($this->seq_w4[$n3] == $this->seq[$k4])
$n4 = 1;
else {
$this->seq_w1[$nn] = $this->seq_w4[$n3];
$nn++;
$n3--;
if ($n3 < 0)
$n3 = $this->n_city - 1;
}
}
$r = kyori($this->n_city, $this->seq_w1, $this->rg);
// 最適値の保存
if ($sw2 == 0 || $r < $max1) {
$sw2 = 1;
$max1 = $r;
$n1 = $k3;
$n2 = $k4;
for ($i2 = 0; $i2 < $this->n_city; $i2++)
$this->seq_w5[$i2] = $this->seq_w1[$i2];
}
}
}
// 最適値の保存と近傍の増加
if ($sw2 > 0) {
if ($max1 < $max) {
$sw = 1;
$max = $max1;
for ($i1 = 0; $i1 < $this->n_city; $i1++)
$this->seq_w2[$i1] = $this->seq_w5[$i1];
}
if ($k < $this->neib) {
for ($i1 = 0; $i1 < $this->n_city; $i1++)
$this->seq_w4[$i1] = $this->seq_w5[$i1];
$this->seq_w3[$n1] = 1;
$this->seq_w3[$n2] = 1;
$k1 = $n2;
$k++;
}
else
$sw1 = 1;
}
else
$sw1 = 1;
}
}
/*
近傍を固定
*/
else {
$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, "%*s %d", $nm);
for ($i0 = 0; $i0 < $nm; $i0++) {
// 各問題の実行
fscanf($in, "%*s %s %*s %d", $i_file, $n);
$pt = new Partition($i_file);
$mean = 0.0;
$max = -1;
// 乱数の初期値を変える
for ($i1 = 0; $i1 < $n; $i1++) {
// 問題
printf("\n+++++問題 %s +++++\n", $i_file);
// 最適化
$pt->Optimize(1000 * $i1 + 1234567); // 引数は乱数の初期値
// 最適値とその平均の計算
$mean += $pt->Max;
if ($max < 0 || $pt->Max < $max)
$max = $pt->Max;
}
// 結果
if ($pt->out_m <= 0)
printf(" -----最小 %d 平均 %f-----\n", $max, $mean/$n);
else {
$out = fopen($pt->o_file, "ab");
$str = sprintf(" -----最小 %d 平均 %f-----\n", $max, $mean/$n);
fwrite($out, $str);
fclose($out);
}
}
fclose($in);
}
//------------------------ケーススタディデータ(data.txt)------
/*
問題の数 2
問題 data1.txt 繰り返し回数 2
問題 data2.txt 繰り返し回数 1
*/
//---------------------データファイル(data1.txt)------------
/*
都市の数 50 選択方法(0:最良，1:最初) 1 近傍（2or3） 2 整数 -2
出力(0:ディスプレイ，1:ファイル) -1 出力ファイル名 out1.txt
分割数 Ｘ 2 Ｙ 2 最大試行回数 1000
86.950684 27.711487
82.357788 16.148376
29.791260 37.959290
27.493286 1.542664
90.893555 88.734436
40.109253 92.308044
87.445068 53.474426
24.893188 99.382019
11.633301 80.616760
61.532593 8.702087
30.645752 93.598938
4.714966 81.205750
86.669922 90.858459
84.127808 52.830505
96.893311 45.832825
4.458618 34.513855
53.503418 6.959534
45.394897 12.193298
23.687744 97.676086
61.624146 46.806335
49.633789 16.419983
82.833862 74.290466
48.529053 36.628723
13.711548 5.583191
12.561035 6.739807
33.944702 26.622009
8.917236 50.190735
98.220825 98.344421
79.785156 65.419006
36.227417 56.687927
42.352295 25.862122
52.651978 12.590027
88.806152 79.957581
27.182007 51.988220
86.334229 51.142883
14.505005 35.820007
77.124023 37.855530
44.308472 0.022888
78.363037 13.533020
21.279907 55.534363
82.238770 26.612854
25.106812 88.291931
55.938721 0.532532
10.476685 59.233093
41.650391 33.729553
7.077026 4.295349
56.561279 99.641418
19.595337 34.416199
92.858887 46.705627
27.719116 35.533142
*/
//---------------------データファイル(data2.txt)------------
/*
都市の数 10 選択方法(0:最良，1:最初) 1 近傍（2or3） 2 整数 -2
出力(0:ディスプレイ，1:ファイル) -1 出力ファイル名 out1.txt
分割数 Ｘ 1 Ｙ 1 最大試行回数 1000
8.695068 2.771149
8.235779 1.614838
2.979126 3.795929
2.749329 0.154266
9.089355 8.873444
4.010925 9.230804
8.744507 5.347443
2.489319 9.938202
1.163330 8.061676
6.153259 0.870209
*/
?>