####################################
# 巡回セールスマン問題（反復改善法）
# 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