# -*- coding: UTF-8 -*-
import sys
from math import *
from random import *
from datetime import *
import numpy as np
#################################
# 距離の計算
# n_c : 都市の数
# p : 都市番号
# rg : 都市間の距離
# return : 距離
#################################
def kyori(n_c, p, rg) :
r = 0.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 :
###################################
# コンストラクタ
# 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 : 都市の位置データ
###################################
def __init__(self, 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) :
# 値の設定
self.n_city = n_city_i # 都市の数
self.max_try = max_tri_i # 最大試行回数
self.seisu = sei_i # 位置データの表現方法
# =1 : 整数
# =-1 : 実数（距離を整数計算）
# =-2 : 実数（距離を実数計算）
self.sel = sel_i # エッジの選択方法
# =0 : 最良のものを選択
# =1 : 最初のものを選択
self.neib = neib_i # 近傍（2 or 3）
self.fix = fix_i # =1 : 近傍を固定
# =0 : 近傍を可変
self.out_lvl = out_lvl_i # 出力レベル
# =0 : 最終出力だけ
# n>0 : ｎ世代毎に出力（負の時はファイル）
self.out_m = out_m_i # 出力方法
# =-1 : 出力しない
# =0 : すべてを出力
# =1 : 評価値だけを出力（最終結果だけはすべてを出力）
self.out_d = out_d_i # 表示間隔
self.o_file = o_file_i # 出力ファイル名
self.city = city_i # 都市の位置データ
# 距離テーブルの作成
self.rg = np.empty((self.n_city, self.n_city), np.float)
for i1 in range(0, self.n_city-1) :
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] = sqrt(x * x + y * y)
if self.seisu > -2 :
self.rg[i1][i2] = floor(self.rg[i1][i2] + 0.5)
for i1 in range(1, 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)
self.seq_w3 = np.empty(self.n_city, np.int)
self.seq_w4 = np.empty(self.n_city, np.int)
self.seq_w5 = 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.float)
max[0] = kyori(self.n_city, self.seq, self.rg)
if self.out_m >= 0 and abs(self.out_lvl) > 0 :
if self.seisu > -2 :
print("***試行回数 " + str(n_tri) + " 距離 " + str(int(max[0])))
else :
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 :
if self.seisu > -2 :
print("***試行回数 " + str(n_tri) + " 距離 " + str(int(max[0])))
else :
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
if self.seisu > -2 :
print("***試行回数 " + str(n_tri) + " 距離 " + str(int(max[0])))
else :
print("***試行回数 " + str(n_tri) + " 距離 " + str(max[0]))
self.Output(self.out_lvl, n_tri, max[0])
return n_tri
################################
# 出力
# sw : >=0 : 出力先未定
# <0 : ファイル
# n_tri : 現在の試行回数
# r : 距離
################################
def Output(self, sw, n_tri, r) :
k = 0
if sw >= 0 :
pr = int(input(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ "))
else :
pr = -1
if pr != 0 :
if pr > 0 :
out = sys.stdout
input("")
else :
now = datetime.today().time().isoformat()
out = open(self.o_file, "a")
if self.seisu > -2 :
out.write("***試行回数 " + str(n_tri) + " 距離 " + str(int(r)) + " 時間 " + now + "\n")
else :
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]
if self.seisu > 0 :
out.write(" " + str(n) + " " + str(int(self.city[n][0])) + " " + str(int(self.city[n][1])) + "\n")
else :
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) :
max = r_m[0]
max1 = 0.0
ch = 0
k1 = 0
k2 = 0
n1 = 0
n2 = 0
sw = 0
sw1 = 0
# 近傍を可変
if self.fix == 0 :
# 初期設定（ｋ＝２）
k = 2
for i1 in range(0, self.n_city) :
self.seq_w4[i1] = self.seq[i1]
self.seq_w3[i1] = 0
# 評価
sw2 = 0
i0 = 0
while i0 < self.n_city-2 and sw2 < 2 :
if i0 == 0 :
n = self.n_city - 1
else :
n = self.n_city
i1 = i0 + 2
while i1 < n and sw2 < 2 :
# 相手の場所
k3 = i1
k4 = k3 + 1
if k4 > self.n_city-1 :
k4 = 0
# 順番の入れ替え
n3 = -1
for i2 in range(0, self.n_city) :
if self.seq_w4[i2] == self.seq[i0+1] :
n3 = i2 + 1
break
nn = n3
n4 = -1
for i2 in range(0, self.n_city) :
if nn > self.n_city-1 :
nn = 0
if self.seq_w4[nn] == self.seq[k3] or self.seq_w4[nn] == self.seq[k4] :
n4 = self.seq_w4[nn]
break
else :
nn += 1
if n4 == self.seq[k4] :
n4 = k3
k3 = k4
k4 = n4
# 評価
self.seq_w1[0] = self.seq[k4]
self.seq_w1[1] = self.seq[i0+1]
n4 = -1
nn = 2
while n4 < 0 :
if n3 > self.n_city-1 :
n3 = 0
self.seq_w1[nn] = self.seq_w4[n3]
if self.seq_w4[n3] == self.seq[k3] :
n4 = 1
nn += 1
n3 += 1
self.seq_w1[nn] = self.seq[i0]
nn += 1
n3 = -1
n4 = -1
for i2 in range(0, self.n_city) :
if self.seq_w4[i2] == self.seq[i0] :
n3 = i2 - 1
if n3 < 0 :
n3 = self.n_city - 1
break
while n4 < 0 :
if self.seq_w4[n3] == self.seq[k4] :
n4 = 1
else :
self.seq_w1[nn] = self.seq_w4[n3]
nn += 1
n3 -= 1
if n3 < 0 :
n3 = self.n_city - 1
r = kyori(self.n_city, self.seq_w1, self.rg)
# 最適値の保存
if sw2 == 0 or r < max1 :
sw2 = 1
max1 = r
n1 = k3
n2 = k4
k1 = i0
k2 = i0 + 1
for i2 in range(0, self.n_city) :
self.seq_w5[i2] = self.seq_w1[i2]
if self.sel > 0 and max1 < max :
sw2 = 2
i1 += 1
i0 += 1
# 最適値の保存と近傍の増加
if sw2 > 0 :
if max1 < max :
sw = 1
max = max1
for i1 in range(0, self.n_city) :
self.seq_w2[i1] = self.seq_w5[i1]
if k < self.neib :
for i1 in range(0, self.n_city) :
self.seq_w4[i1] = self.seq_w5[i1]
self.seq_w3[k1] = 1
self.seq_w3[k2] = 1
self.seq_w3[n1] = 1
self.seq_w3[n2] = 1
k1 = n2
k += 1
else :
sw1 = 1
else :
sw1 = 1
# 実行（ｋ＞２）
while sw1 == 0 :
# 評価
sw2 = 0
for i1 in range(0, self.n_city) :
# 相手の場所
k3 = i1
k4 = k3 + 1
if k4 > self.n_city-1 :
k4 = 0
if self.seq_w3[k3] == 0 and self.seq_w3[k4] == 0 :
# 順番の入れ替え
n3 = -1
for i2 in range(0, self.n_city) :
if self.seq_w4[i2] == self.seq[k2] :
n3 = i2 + 1
break
nn = n3
n4 = -1
for i2 in range(0, self.n_city) :
if nn > self.n_city-1 :
nn = 0
if self.seq_w4[nn] == self.seq[k3] or self.seq_w4[nn] == self.seq[k4] :
n4 = self.seq_w4[nn]
break
else :
nn += 1
if n4 == self.seq[k4] :
n4 = k3
k3 = k4
k4 = n4
# 評価
self.seq_w1[0] = self.seq[k4]
self.seq_w1[1] = self.seq[k2]
n4 = -1
nn = 2
while n4 < 0 :
if n3 > self.n_city-1 :
n3 = 0
self.seq_w1[nn] = self.seq_w4[n3]
if self.seq_w4[n3] == self.seq[k3] :
n4 = 1
nn += 1
n3 += 1
self.seq_w1[nn] = self.seq[k1]
nn += 1
n3 = -1
n4 = -1
for i2 in range(0, self.n_city) :
if self.seq_w4[i2] == self.seq[k1] :
n3 = i2 - 1
if n3 < 0 :
n3 = self.n_city - 1
break
while n4 < 0 :
if self.seq_w4[n3] == self.seq[k4] :
n4 = 1
else :
self.seq_w1[nn] = self.seq_w4[n3]
nn += 1
n3 -= 1
if n3 < 0 :
n3 = self.n_city - 1
r = kyori(self.n_city, self.seq_w1, self.rg)
# 最適値の保存
if sw2 == 0 or r < max1 :
sw2 = 1
max1 = r
n1 = k3
n2 = k4
for i2 in range(0, self.n_city) :
self.seq_w5[i2] = self.seq_w1[i2]
# 最適値の保存と近傍の増加
if sw2 > 0 :
if max1 < max :
sw = 1
max = max1
for i1 in range(0, self.n_city) :
self.seq_w2[i1] = self.seq_w5[i1]
if k < self.neib :
for i1 in range(0, self.n_city) :
self.seq_w4[i1] = self.seq_w5[i1]
self.seq_w3[n1] = 1
self.seq_w3[n2] = 1
k1 = n2
k += 1
else :
sw1 = 1
else :
sw1 = 1
# 近傍を固定
else :
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 :
if n3 == 0 :
n1 = self.n_city - 2
else :
n1 = self.n_city - 1
i2 = n3 + 2
while i2 <= n1 and ch == 0 :
# 枝の場所（(n3,n3+1), (k1,k2)）
k1 = i2
if i2 == self.n_city-1 :
k2 = 0
else :
k2 = i2 + 1
# 枝の入れ替え
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
if i3 == self.n_city-1 :
k2 = 0
else :
k2 = i3 + 1
# 枝の入れ替えと評価
# 入れ替え（その１）
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
#########################
# クラスPartitionの定義
#########################
class Partition :
##########################
# コンストラクタ
# name : ファイル名
##########################
def __init__(self, name) :
max = 0
# ファイルのオープン
self.i_file = name # 入力ファイル名
inn = open(name, "r")
# 基本データ
s = inn.readline().split()
self.n_city = int(s[1]) # 都市の数
self.sel = int(s[3]) # エッジの選択方法
# =0 : 最良のものを選択
# =1 : 最初のものを選択
self.neib = int(s[5]) # 近傍（2 or 3）
self.seisu = int(s[7]) # 位置データの表現方法
# =1 : 整数
# =-1 : 実数（距離を整数計算）
# =-2 : 実数（距離を実数計算）
s = inn.readline().split()
self.out_m = int(s[1]) # 出力方法
# =-1 : ディスプレイ（経路長だけ）
# =0 : ディスプレイ
# =1 : ファイル
# =2 : ファイル（経路長だけ）
self.o_file = ""
if self.out_m > 0 :
self.o_file = s[3]
s = inn.readline().split()
self.n_p_x = int(s[2]) # ｘ軸方向の分割数
self.n_p_y = int(s[4]) # ｙ軸方向の分割数
self.max_try = int(s[6]) # 最大試行回数
self.fix = 1 # =1 : 近傍を固定
# =0 : 近傍を可変
if self.neib < 0 :
self.neib = -self.neib
self.fix = 0
# 都市の位置データ
self.city = np.empty((self.n_city, 2), np.float)
for i1 in range(0, self.n_city) :
s = inn.readline().split()
self.city[i1][0] = float(s[0])
self.city[i1][1] = float(s[1])
# ファイルのクローズ
inn.close()
# 距離テーブルの作成
self.rg = np.empty((self.n_city, self.n_city), np.float) # 都市間の距離
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] = sqrt(x * x + y * y)
if self.seisu > -2 :
self.rg[i1][i2] = floor(rg[i1][i2] + 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.state = np.empty((self.n_p_y, self.n_p_x), np.int) # 領域結合用ワーク
self.n_seq = np.empty((self.n_p_y, self.n_p_x), np.int) # 各領域の都市数
self.n_seq1 = np.empty((self.n_p_y, self.n_p_x), np.int) # 各領域の都市数（ワーク）
self.seq_w1 = np.zeros(self.n_city, np.int) # 作業領域
self.seq_w2 = np.empty(self.n_city, np.int) # 作業領域
self.p_x = np.empty(self.n_p_x, np.float) # ｘ軸の分割点
self.p_y = np.empty(self.n_p_y, np.float) # ｙ軸の分割点
# 都市の分割
min_x = self.city[0][0]
max_x = self.city[0][0]
min_y = self.city[0][1]
max_y = self.city[0][1]
for i1 in range(1, self.n_city) :
if self.city[i1][0] < min_x :
min_x = self.city[i1][0]
else :
if self.city[i1][0] > max_x :
max_x = self.city[i1][0]
if self.city[i1][1] < min_y :
min_y = self.city[i1][1]
else :
if self.city[i1][1] > max_y :
max_y = self.city[i1][1]
s_x = (max_x - min_x) / self.n_p_x
self.p_x[0] = min_x + s_x
self.p_x[self.n_p_x-1] = max_x
for i1 in range(1, self.n_p_x-1) :
self.p_x[i1] = self.p_x[0] + i1 * s_x
s_y = (max_y - min_y) / self.n_p_y
self.p_y[0] = min_y + s_y
self.p_y[self.n_p_y-1] = max_y
for i1 in range(1, self.n_p_y-1) :
self.p_y[i1] = self.p_y[0] + i1 * s_y
self.seq = np.empty((self.n_p_y, self.n_p_x, self.n_city), np.int) # 経路
self.seq1 = np.empty((self.n_p_y, self.n_p_x, self.n_city), np.int) # 経路（ワーク）
for i1 in range(0, self.n_p_y) :
for i2 in range(0, self.n_p_x) :
n = 0
for i3 in range(0, self.n_city) :
if self.seq_w1[i3] == 0 :
if self.city[i3][0] <= self.p_x[i2] and self.city[i3][1] <= self.p_y[i1] :
self.seq_w1[i3] = 1
self.seq_w2[n] = i3
n += 1
self.n_seq1[i1][i2] = n
if n > 0 :
for i3 in range(0, n) :
self.seq1[i1][i2][i3] = self.seq_w2[i3]
if n > max :
max = n
# 作業領域
print("max " + str(max))
self.city_i = np.empty((max, 2), np.float) # 都市の位置データ（作業領域）
self.Max = 0 # 最適経路の長さ
##################
# 最適化の実行
##################
def Optimize(self) :
r = 0
# 分割数と開始時間の出力
if self.out_m > 0 :
self.Output(0, r)
for i1 in range(0, self.n_p_y) :
for i2 in range(0, self.n_p_x) :
self.n_seq[i1][i2] = self.n_seq1[i1][i2]
for i3 in range(0, self.n_seq1[i1][i2]) :
self.seq[i1][i2][i3] = self.seq1[i1][i2][i3]
# 分割毎の最適化
for i1 in range(0, self.n_p_y) :
for i2 in range(0, self.n_p_x) :
if self.n_seq[i1][i2] > 3 :
# 近傍の大きさ
if self.n_seq[i1][i2] > 3 :
nb = self.neib
else :
nb = 2
# 都市位置データの設定
for i3 in range(0, self.n_seq[i1][i2]) :
k = self.seq[i1][i2][i3]
self.city_i[i3][0] = self.city[k][0]
self.city_i[i3][1] = self.city[k][1]
# 最適化
it = Iteration(self.n_seq[i1][i2], self.max_try, self.seisu, self.sel, nb, self.fix, 0, -1, 0, self.o_file, self.city_i)
max = it.Optimize()
# 結果の保存
for i3 in range(0, self.n_seq[i1][i2]) :
k = it.seq[i3]
self.seq_w1[i3] = self.seq[i1][i2][k]
for i3 in range(0, self.n_seq[i1][i2]) :
self.seq[i1][i2][i3] = self.seq_w1[i3]
# 出力
if self.seisu > -2 :
r = int(kyori(self.n_seq[i1][i2], self.seq[i1][i2], self.rg))
else :
r = floor(kyori(self.n_seq[i1][i2], self.seq[i1][i2], self.rg) + 0.5)
print(" y " + str(i1+1) + " x " + str(i2+1) + " n_city " + str(self.n_seq[i1][i2]) + " range " + str(r) + " (trial " + str(max) + ")")
# 経路の接続
r = self.Connect()
# 出力
self.Output(self.n_city, r)
########################
# 出力
# n_c : 都市の数
# r : 距離
########################
def Output(self, n_c, r) :
k = 0
if self.out_m <= 0 :
out = sys.stdout
print("距離 " + str(r))
input("")
else :
now = datetime.today().time().isoformat()
out = open(self.o_file, "a")
if n_c > 0 :
print("距離 " + str(r))
out.write(" 距離 " + str(r) + " 時間 " + now + "\n")
else :
out.write("問題 " + self.i_file + " 分割 " + str(self.n_p_x) + " " + str(self.n_p_y) + " 時間 " + now + "\n")
if n_c > 0 and (self.out_m == 0 or self.out_m == 1) :
for i1 in range(0, n_c) :
n = self.seq_w1[i1]
if self.seisu > 0 :
out.write(" " + str(n) + " " + str(int(self.city[n][0])) + " " + str(int(self.city[n][1])) + "\n")
else :
out.write(" " + str(n) + " " + str(self.city[n][0]) + " " + str(self.city[n][1]) + "\n")
if self.out_m == 0 :
k += 1
if k == 10 :
input("")
k = 0
if self.out_m > 0 :
out.close()
########################
# 分割された領域の接続
########################
def Connect(self) :
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 self.n_p_x == 1 and self.n_p_y == 1 :
for i1 in range(0, self.n_seq[0][0]) :
self.seq_w1[i1] = self.seq[0][0][i1]
# 初期設定
else :
for i1 in range(0, self.n_p_y) :
for i2 in range(0, self.n_p_x) :
if self.n_seq[i1][i2] > 0 :
self.state[i1][i2] = 0
else :
self.state[i1][i2] = 1
# 実行
while sw > 0 :
# 最小節点領域
min_c = self.n_city
sw = 0
for i1 in range(0, self.n_p_y) :
for i2 in range(0, self.n_p_x) :
if self.state[i1][i2] == 0 and self.n_seq[i1][i2] < min_c :
sw = 1
r1 = i1
r2 = i2
min_c = self.n_seq[i1][i2]
# 結合する対象領域の決定
if sw > 0 :
sw = 0
for i1 in range(0, self.n_p_y) :
for i2 in range(0, self.n_p_x) :
if self.state[i1][i2] == 0 and (i1 != r1 or i2 !=r2) :
# 節点の数＞２
if self.n_seq[r1][r2] > 1 :
for i3 in range(0, self.n_seq[r1][r2]) :
k1 = self.seq[r1][r2][i3]
if i3 == self.n_seq[r1][r2]-1 :
k2 = self.seq[r1][r2][0]
else :
k2 = self.seq[r1][r2][i3+1]
wd1 = self.rg[k1][k2]
for i4 in range(0, self.n_seq[i1][i2]) :
k3 = self.seq[i1][i2][i4]
if i4 == self.n_seq[i1][i2]-1 :
k4 = self.seq[i1][i2][0]
else :
k4 = self.seq[i1][i2][i4+1]
wd = wd1 + self.rg[k3][k4]
wa1 = self.rg[k1][k3] + self.rg[k2][k4]
wa2 = self.rg[k1][k4] + self.rg[k2][k3]
if sw == 0 or wa1-wd < min :
min = wa1 - wd
r3 = i1
r4 = i2
if i3 == self.n_seq[r1][r2]-1 :
s1 = 0
else :
s1 = i3 + 1
if i4 == self.n_seq[i1][i2]-1 :
s2 = 0
else :
s2 = i4 + 1
sw = -1
if sw == 0 or wa2-wd < min :
min = wa2 - wd
r3 = i1
r4 = i2
s1 = i3
if i4 == self.n_seq[i1][i2]-1 :
s2 = 0
else :
s2 = i4 + 1
sw = 1
# 節点の数＝１
else :
k1 = self.seq[r1][r2][0]
if self.n_seq[i1][i2] > 1 :
for i4 in range(0, self.n_seq[i1][i2]) :
k3 = self.seq[i1][i2][i4]
if i4 == self.n_seq[i1][i2]-1 :
k4 = self.seq[i1][i2][0]
else :
k4 = self.seq[i1][i2][i4+1]
wd = self.rg[k3][k4]
wa1 = self.rg[k1][k3] + self.rg[k1][k4]
if sw == 0 or wa1-wd < min :
min = wa1 - wd
r3 = i1
r4 = i2
s1 = 0
if i4 == self.n_seq[i1][i2]-1 :
s2 = 0
else :
s2 = i4 + 1
sw = 1
else :
k3 = self.seq[i1][i2][0]
wa1 = self.rg[k1][k3]
if sw == 0 or wa1 < min :
min = wa1
r3 = i1
r4 = i2
s1 = 0
s2 = 0
sw = 1
# 領域の結合
self.seq_w1[0] = self.seq[r1][r2][s1]
k = 1
n = s2
for i1 in range(0, self.n_seq[r3][r4]) :
self.seq_w1[k] = self.seq[r3][r4][n]
k += 1
n += 1
if n > self.n_seq[r3][r4]-1 :
n = 0
if sw > 0 :
n = s1 + 1
for i1 in range(0, self.n_seq[r1][r2]-1) :
if n > self.n_seq[r1][r2]-1 :
n = 0
self.seq_w1[k] = self.seq[r1][r2][n]
k += 1
n += 1
else :
n = s1 - 1
for i1 in range(0, self.n_seq[r1][r2]-1) :
if n < 0 :
n = self.n_seq[r1][r2] - 1
self.seq_w1[k] = self.seq[r1][r2][n]
k += 1
n -= 1
# 状態の変更
self.n_seq[r1][r2] += self.n_seq[r3][r4]
self.state[r3][r4] = 1
for i1 in range(0, self.n_seq[r1][r2]) :
self.seq[r1][r2][i1] = self.seq_w1[i1]
sw = 1
if self.seisu > -2 :
r = int(kyori(self.n_city, self.seq_w1, self.rg))
else :
r = floor(kyori(self.n_city, self.seq_w1, self.rg) + 0.5)
self.Max = r
return r
----------------------------------
# -*- coding: UTF-8 -*-
import numpy as np
import sys
from math import *
from random import *
from function import Partition, Iteration
################################
# 巡回セールスマン問題（分割法）
# coded by Y.Suganuma
################################
# 入力ミス
if len(sys.argv) <= 1 :
print("***error ファイル名を入力して下さい")
# 入力ＯＫ
else :
# ファイルのオープン
inn = open(sys.argv[1], "r")
# 問題数と入力データファイル名
s = inn.readline().split()
nm = int(s[1])
for i0 in range(0, nm) :
# 各問題の実行
s = inn.readline().split()
i_file = s[1]
n = int(s[3])
pt = Partition(i_file)
mean = 0.0
max = -1
# 乱数の初期値を変える
for i1 in range(0, n) :
print("\n+++++問題 " + i_file + " +++++")
# 最適化
pt.Optimize()
# 最適値とその平均の計算
mean += pt.Max
if max < 0 or pt.Max < max :
max = pt.Max
# 結果
if pt.out_m <= 0 :
print(" -----最小 " + str(max) + " 平均 " + str(mean/n) + "-----")
else :
out = open(pt.o_file, "a")
out.write(" -----最小 " + str(max) + " 平均 " + str(mean/n) + "-----\n")
out.close()
inn.close()
------------------------ケーススタディデータ------
問題の数 2
問題 data2.txt 繰り返し回数 2
問題 data3.txt 繰り返し回数 1
---------------------データファイル(data2.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
---------------------データファイル(data3.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