################################
# 巡回セールスマン問題（分割法）
# 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
###################################
# コンストラクタ
# 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 initialize(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)
# 値の設定
@_n_city = n_city_i # 都市の数
@_max_try = max_tri_i # 最大試行回数
@_seisu = sei_i # 位置データの表現方法
# =1 整数
# =-1 実数（距離を整数計算）
# =-2 実数（距離を実数計算）
@_sel = sel_i # エッジの選択方法
# =0 最良のものを選択
# =1 最初のものを選択
@_neib = neib_i # 近傍（2 or 3）
@_fix = fix_i # =1 近傍を固定
# =0 近傍を可変
@_out_lvl = out_lvl_i # 出力レベル
# =0 最終出力だけ
# n>0 ｎ世代毎に出力（負の時はファイル）
@_out_m = out_m_i # 出力方法
# =-1 出力しない
# =0 すべてを出力
# =1 評価値だけを出力（最終結果だけはすべてを出力）
@_out_d = out_d_i # 表示間隔
@_o_file = o_file_i # 出力ファイル名
@_city = city_i # 都市の位置データ
# 距離テーブルの作成
@_rg = Array.new(@_n_city)
for i1 in 0 ... @_n_city
@_rg[i1] = Array.new(@_n_city)
end
for i1 in 0 ... @_n_city-1
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)
if @_seisu > -2
@_rg[i1][i2] = @_rg[i1][i2].round()
end
end
end
for i1 in 1 ... @_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)
@_seq_w3 = Array.new(@_n_city)
@_seq_w4 = Array.new(@_n_city)
@_seq_w5 = 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 && @_out_lvl.abs() > 0
if @_seisu > -2
print("***試行回数 " + String(n_tri) + " 距離 " + String(Integer(max[0])) + "\n")
else
print("***試行回数 " + String(n_tri) + " 距離 " + String(max[0]) + "\n")
end
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
if @_seisu > -2
print("***試行回数 " + String(n_tri) + " 距離 " + String(Integer(max[0])) + "\n")
else
print("***試行回数 " + String(n_tri) + " 距離 " + String(max[0]) + "\n")
end
end
if @_out_m >= 0 && @_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
if @_seisu > -2
print("***試行回数 " + String(n_tri) + " 距離 " + String(Integer(max[0])) + "\n")
else
print("***試行回数 " + String(n_tri) + " 距離 " + String(max[0]) + "\n")
end
Output(@_out_lvl, n_tri, max[0])
end
return n_tri
end
################################
# 出力
# sw >=0 出力先未定
# <0 ファイル
# n_tri 現在の試行回数
# r 距離
################################
def Output(sw, n_tri, r)
k = 0
if sw >= 0
print(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ ")
pr = Integer($stdin.gets())
else
pr = -1
end
if pr != 0
if pr > 0
out = $stdout
$stdin.gets()
else
now = String(Time.now)
out = open(@_o_file, "a")
if @_seisu > -2
out.print("***試行回数 " + String(n_tri) + " 距離 " + String(int(r)) + " 時間 " + now + "\n")
else
out.print("***試行回数 " + String(n_tri) + " 距離 " + String(r) + " 時間 " + now + "\n")
end
end
if @_out_m == 0
for i1 in 0 ... @_n_city
n = @_seq[i1]
if @_seisu > 0
out.write(" " + String(n) + " " + String(int(@_city[n][0])) + " " + String(int(@_city[n][1])) + "\n")
else
out.write(" " + String(n) + " " + String(@_city[n][0]) + " " + String(@_city[n][1]) + "\n")
end
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)
max = r_m[0]
max1 = 0.0
ch = 0
k1 = 0
k2 = 0
n1 = 0
n2 = 0
sw = 0
sw1 = 0
# 近傍を可変
if @_fix == 0
# 初期設定（ｋ＝２）
k = 2
for i1 in 0 ... @_n_city
@_seq_w4[i1] = @_seq[i1]
@_seq_w3[i1] = 0
end
# 評価
sw2 = 0
i0 = 0
while i0 < @_n_city-2 && sw2 < 2
if i0 == 0
n = @_n_city - 1
else
n = @_n_city
end
i1 = i0 + 2
while i1 < n && sw2 < 2
# 相手の場所
k3 = i1
k4 = k3 + 1
if k4 > @_n_city-1
k4 = 0
end
# 順番の入れ替え
n3 = -1
for i2 in 0 ... @_n_city
if @_seq_w4[i2] == @_seq[i0+1]
n3 = i2 + 1
break
end
end
nn = n3
n4 = -1
for i2 in 0 ... @_n_city
if nn > @_n_city-1
nn = 0
end
if @_seq_w4[nn] == @_seq[k3] || @_seq_w4[nn] == @_seq[k4]
n4 = @_seq_w4[nn]
break
else
nn += 1
end
end
if n4 == @_seq[k4]
n4 = k3
k3 = k4
k4 = n4
end
# 評価
@_seq_w1[0] = @_seq[k4]
@_seq_w1[1] = @_seq[i0+1]
n4 = -1
nn = 2
while n4 < 0
if n3 > @_n_city-1
n3 = 0
end
@_seq_w1[nn] = @_seq_w4[n3]
if @_seq_w4[n3] == @_seq[k3]
n4 = 1
end
nn += 1
n3 += 1
end
@_seq_w1[nn] = @_seq[i0]
nn += 1
n3 = -1
n4 = -1
for i2 in 0 ... @_n_city
if @_seq_w4[i2] == @_seq[i0]
n3 = i2 - 1
if n3 < 0
n3 = @_n_city - 1
end
break
end
end
while n4 < 0
if @_seq_w4[n3] == @_seq[k4]
n4 = 1
else
@_seq_w1[nn] = @_seq_w4[n3]
nn += 1
n3 -= 1
if n3 < 0
n3 = @_n_city - 1
end
end
end
r = kyori(@_n_city, @_seq_w1, @_rg)
# 最適値の保存
if sw2 == 0 || r < max1
sw2 = 1
max1 = r
n1 = k3
n2 = k4
k1 = i0
k2 = i0 + 1
for i2 in 0 ... @_n_city
@_seq_w5[i2] = @_seq_w1[i2]
end
if @_sel > 0 && max1 < max
sw2 = 2
end
end
i1 += 1
end
i0 += 1
end
# 最適値の保存と近傍の増加
if sw2 > 0
if max1 < max
sw = 1
max = max1
for i1 in 0 ... @_n_city
@_seq_w2[i1] = @_seq_w5[i1]
end
end
if k < @_neib
for i1 in 0 ... @_n_city
@_seq_w4[i1] = @_seq_w5[i1]
end
@_seq_w3[k1] = 1
@_seq_w3[k2] = 1
@_seq_w3[n1] = 1
@_seq_w3[n2] = 1
k1 = n2
k += 1
else
sw1 = 1
end
else
sw1 = 1
end
# 実行（ｋ＞２）
while sw1 == 0
# 評価
sw2 = 0
for i1 in 0 ... @_n_city
# 相手の場所
k3 = i1
k4 = k3 + 1
if k4 > @_n_city-1
k4 = 0
end
if @_seq_w3[k3] == 0 && @_seq_w3[k4] == 0
# 順番の入れ替え
n3 = -1
for i2 in 0 ... @_n_city
if @_seq_w4[i2] == @_seq[k2]
n3 = i2 + 1
break
end
end
nn = n3
n4 = -1
for i2 in 0 ... @_n_city
if nn > @_n_city-1
nn = 0
end
if @_seq_w4[nn] == @_seq[k3] || @_seq_w4[nn] == @_seq[k4]
n4 = @_seq_w4[nn]
break
else
nn += 1
end
end
if n4 == @_seq[k4]
n4 = k3
k3 = k4
k4 = n4
end
# 評価
@_seq_w1[0] = @_seq[k4]
@_seq_w1[1] = @_seq[k2]
n4 = -1
nn = 2
while n4 < 0
if n3 > @_n_city-1
n3 = 0
end
@_seq_w1[nn] = @_seq_w4[n3]
if @_seq_w4[n3] == @_seq[k3]
n4 = 1
end
nn += 1
n3 += 1
end
@_seq_w1[nn] = @_seq[k1]
nn += 1
n3 = -1
n4 = -1
for i2 in 0 ... @_n_city
if @_seq_w4[i2] == @_seq[k1]
n3 = i2 - 1
if n3 < 0
n3 = @_n_city - 1
end
break
end
end
while n4 < 0
if @_seq_w4[n3] == @_seq[k4]
n4 = 1
else
@_seq_w1[nn] = @_seq_w4[n3]
nn += 1
n3 -= 1
if n3 < 0
n3 = @_n_city - 1
end
end
end
r = kyori(@_n_city, @_seq_w1, @_rg)
# 最適値の保存
if sw2 == 0 || r < max1
sw2 = 1
max1 = r
n1 = k3
n2 = k4
for i2 in 0 ... @_n_city
@_seq_w5[i2] = @_seq_w1[i2]
end
end
end
end
# 最適値の保存と近傍の増加
if sw2 > 0
if max1 < max
sw = 1
max = max1
for i1 in 0 ... @_n_city
@_seq_w2[i1] = @_seq_w5[i1]
end
end
if k < @_neib
for i1 in 0 ... @_n_city
@_seq_w4[i1] = @_seq_w5[i1]
end
@_seq_w3[n1] = 1
@_seq_w3[n2] = 1
k1 = n2
k += 1
else
sw1 = 1
end
else
sw1 = 1
end
end
# 近傍を固定
else
n3 = Integer(rand(0) * (@_n_city - 2))
if n3 > @_n_city-3
n3 = @_n_city - 3
end
# ２近傍
i1 = 0
while i1 <= @_n_city-3 && ch == 0
if n3 == 0
n1 = @_n_city - 2
else
n1 = @_n_city - 1
end
i2 = n3 + 2
while i2 <= n1 && ch == 0
# 枝の場所（(n3,n3+1), (k1,k2)）
k1 = i2
if i2 == @_n_city-1
k2 = 0
else
k2 = i2 + 1
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 && ch == 0
i1 = 0
while i1 <= @_n_city-3 && ch == 0
n1 = @_n_city - 2
n2 = @_n_city - 1
i2 = n3 + 1
while i2 <= n1 && ch == 0
i3 = i2 + 1
while i3 <= n2 && ch == 0
# 枝の場所（(n3,n3+1), (i2,i2+1), (k1,k2)）
k1 = i3
if i3 == @_n_city-1
k2 = 0
else
k2 = i3 + 1
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
end
# 設定
if sw > 0
r_m[0] = max
for i1 in 0 ... @_n_city
@_seq[i1] = @_seq_w2[i1]
end
end
return sw
end
attr("_seq", true)
end
#########################
# クラスPartitionの定義
#########################
class Partition
##########################
# コンストラクタ
# name ファイル名
##########################
def initialize(name)
max = 0
# ファイルのオープン
@_i_file = name # 入力ファイル名
inn = open(name, "r")
# 基本データ
s = inn.gets().split(" ")
@_n_city = Integer(s[1]) # 都市の数
@_sel = Integer(s[3]) # エッジの選択方法
# =0 最良のものを選択
# =1 最初のものを選択
@_neib = Integer(s[5]) # 近傍（2 or 3）
@_seisu = Integer(s[7]) # 位置データの表現方法
# =1 整数
# =-1 実数（距離を整数計算）
# =-2 実数（距離を実数計算）
s = inn.gets().split(" ")
@_out_m = Integer(s[1]) # 出力方法
# =-1 ディスプレイ（経路長だけ）
# =0 ディスプレイ
# =1 ファイル
# =2 ファイル（経路長だけ）
@_o_file = ""
if @_out_m > 0
@_o_file = s[3]
end
s = inn.gets().split(" ")
@_n_p_x = Integer(s[2]) # ｘ軸方向の分割数
@_n_p_y = Integer(s[4]) # ｙ軸方向の分割数
@_max_try = Integer(s[6]) # 最大試行回数
@_fix = 1 # =1 近傍を固定
# =0 近傍を可変
if @_neib < 0
@_neib = -@_neib
@_fix = 0
end
# 都市の位置データ
@_city = Array.new(@_n_city)
for i1 in 0 ... @_n_city
@_city[i1] = Array.new(2)
s = inn.gets().split(" ")
@_city[i1][0] = Float(s[0])
@_city[i1][1] = Float(s[1])
end
# ファイルのクローズ
inn.close()
# 距離テーブルの作成
@_rg = Array.new(@_n_city) # 都市間の距離
for i1 in 0 ... @_n_city
@_rg[i1] = Array.new(@_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)
if @_seisu > -2
@_rg[i1][i2] = rg[i1][i2].round()
end
end
end
for i1 in 0 ... @_n_city
for i2 in 0 ... i1
@_rg[i1][i2] = @_rg[i2][i1]
end
end
# 作業領域
@_state = Array.new(@_n_p_y) # 領域結合用ワーク
@_n_seq = Array.new(@_n_p_y) # 各領域の都市数
@_n_seq1 = Array.new(@_n_p_y) # 各領域の都市数（ワーク）
for i1 in 0 ... @_n_p_y
@_state[i1] = Array.new(@_n_p_x) # 領域結合用ワーク
@_n_seq[i1] = Array.new(@_n_p_x) # 各領域の都市数
@_n_seq1[i1] = Array.new(@_n_p_x) # 各領域の都市数（ワーク）
end
@_seq_w1 = Array.new(@_n_city) # 作業領域
for i1 in 0 ... @_n_city
@_seq_w1[i1] = 0
end
@_seq_w2 = Array.new(@_n_city) # 作業領域
@_p_x = Array.new(@_n_p_x) # ｘ軸の分割点
@_p_y = Array.new(@_n_p_y) # ｙ軸の分割点
# 都市の分割
min_x = @_city[0][0]
max_x = @_city[0][0]
min_y = @_city[0][1]
max_y = @_city[0][1]
for i1 in 1 ... @_n_city
if @_city[i1][0] < min_x
min_x = @_city[i1][0]
else
if @_city[i1][0] > max_x
max_x = @_city[i1][0]
end
end
if @_city[i1][1] < min_y
min_y = @_city[i1][1]
else
if @_city[i1][1] > max_y
max_y = @_city[i1][1]
end
end
end
s_x = (max_x - min_x) / @_n_p_x
@_p_x[0] = min_x + s_x
@_p_x[@_n_p_x-1] = max_x
for i1 in 1 ... @_n_p_x-1
@_p_x[i1] = @_p_x[0] + i1 * s_x
end
s_y = (max_y - min_y) / @_n_p_y
@_p_y[0] = min_y + s_y
@_p_y[@_n_p_y-1] = max_y
for i1 in 1 ... @_n_p_y-1
@_p_y[i1] = @_p_y[0] + i1 * s_y
end
@_seq = Array.new(@_n_p_y) # 経路
@_seq1 = Array.new(@_n_p_y) # 経路（ワーク）
for i1 in 0 ... @_n_p_y
@_seq[i1] = Array.new(@_n_p_x)
@_seq1[i1] = Array.new(@_n_p_x)
for i2 in 0 ... @_n_p_x
@_seq[i1][i2] = Array.new(@_n_city)
@_seq1[i1][i2] = Array.new(@_n_city)
n = 0
for i3 in 0 ... @_n_city
if @_seq_w1[i3] == 0
if @_city[i3][0] <= @_p_x[i2] && @_city[i3][1] <= @_p_y[i1]
@_seq_w1[i3] = 1
@_seq_w2[n] = i3
n += 1
end
end
end
@_n_seq1[i1][i2] = n
if n > 0
for i3 in 0 ... n
@_seq1[i1][i2][i3] = @_seq_w2[i3]
end
if n > max
max = n
end
end
end
end
# 作業領域
print("最大都市数 " + String(max) + "\n")
@_city_i = Array.new(max) # 都市の位置データ（作業領域）
for i1 in 0 ... max
@_city_i[i1] = Array.new(2)
end
@_max = 0 # 最適経路の長さ
end
##################
# 最適化の実行
##################
def Optimize()
r = 0
# 分割数と開始時間の出力
if @_out_m > 0
Output(0, r)
end
for i1 in 0 ... @_n_p_y
for i2 in 0 ... @_n_p_x
@_n_seq[i1][i2] = @_n_seq1[i1][i2]
for i3 in 0 ... @_n_seq1[i1][i2]
@_seq[i1][i2][i3] = @_seq1[i1][i2][i3]
end
end
end
# 分割毎の最適化
for i1 in 0 ... @_n_p_y
for i2 in 0 ... @_n_p_x
if @_n_seq[i1][i2] > 3
# 近傍の大きさ
if @_n_seq[i1][i2] > 3
nb = @_neib
else
nb = 2
end
# 都市位置データの設定
for i3 in 0 ... @_n_seq[i1][i2]
k = @_seq[i1][i2][i3]
@_city_i[i3][0] = @_city[k][0]
@_city_i[i3][1] = @_city[k][1]
end
# 最適化
it = Iteration.new(@_n_seq[i1][i2], @_max_try, @_seisu, @_sel, nb, @_fix, 0, -1, 0, @_o_file, @_city_i)
max = it.Optimize()
# 結果の保存
for i3 in 0 ... @_n_seq[i1][i2]
k = it._seq[i3]
@_seq_w1[i3] = @_seq[i1][i2][k]
end
for i3 in 0 ... @_n_seq[i1][i2]
@_seq[i1][i2][i3] = @_seq_w1[i3]
end
# 出力
if @_seisu > -2
r = Integer(kyori(@_n_seq[i1][i2], @_seq[i1][i2], @_rg))
else
r = kyori(@_n_seq[i1][i2], @_seq[i1][i2], @_rg).round()
print(" y " + String(i1+1) + " x " + String(i2+1) + " n_city " + String(@_n_seq[i1][i2]) + " range " + String(r) + " (trial " + String(max) + ")\n")
end
end
end
end
# 経路の接続
r = Connect()
# 出力
Output(@_n_city, r)
end
########################
# 出力
# n_c 都市の数
# r 距離
########################
def Output(n_c, r)
k = 0
if @_out_m <= 0
print("距離 " + String(r) + "\n")
out = $stdout
$stdin.gets()
else
now = String(Time.now)
out = open(@_o_file, "a")
if n_c > 0
print("距離 " + String(r) + "\n")
printf(out, " 距離 " + String(r) + " 時間 " + now + "\n")
else
printf("問題 " + @_i_file + " 分割 " + String(@_n_p_x) + " " + String(@_n_p_y) + " 時間 " + now + "\n")
end
end
if n_c > 0 && (@_out_m == 0 || @_out_m == 1)
for i1 in 0 ... n_c
n = @_seq_w1[i1]
if @_seisu > 0
out.print(" " + String(n) + " " + String(int(@_city[n][0])) + " " + String(int(@_city[n][1])) + "\n")
else
out.print(" " + String(n) + " " + String(@_city[n][0]) + " " + String(@_city[n][1]) + "\n")
end
if @_out_m == 0
k += 1
if k == 10
$stdin.gets()
k = 0
end
end
end
end
if @_out_m > 0
out.close()
end
end
########################
# 分割された領域の接続
########################
def 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 @_n_p_x == 1 && @_n_p_y == 1
for i1 in 0 ... @_n_seq[0][0]
@_seq_w1[i1] = @_seq[0][0][i1]
end
# 初期設定
else
for i1 in 0 ... @_n_p_y
for i2 in 0 ... @_n_p_x
if @_n_seq[i1][i2] > 0
@_state[i1][i2] = 0
else
@_state[i1][i2] = 1
end
end
end
# 実行
while sw > 0
# 最小節点領域
min_c = @_n_city
sw = 0
for i1 in 0 ... @_n_p_y
for i2 in 0 ... @_n_p_x
if @_state[i1][i2] == 0 && @_n_seq[i1][i2] < min_c
sw = 1
r1 = i1
r2 = i2
min_c = @_n_seq[i1][i2]
end
end
end
# 結合する対象領域の決定
if sw > 0
sw = 0
for i1 in 0 ... @_n_p_y
for i2 in 0 ... @_n_p_x
if @_state[i1][i2] == 0 && (i1 != r1 || i2 != r2)
# 節点の数＞２
if @_n_seq[r1][r2] > 1
for i3 in 0 ... @_n_seq[r1][r2]
k1 = @_seq[r1][r2][i3]
if i3 == @_n_seq[r1][r2]-1
k2 = @_seq[r1][r2][0]
else
k2 = @_seq[r1][r2][i3+1]
end
wd1 = @_rg[k1][k2]
for i4 in 0 ... @_n_seq[i1][i2]
k3 = @_seq[i1][i2][i4]
if i4 == @_n_seq[i1][i2]-1
k4 = @_seq[i1][i2][0]
else
k4 = @_seq[i1][i2][i4+1]
end
wd = wd1 + @_rg[k3][k4]
wa1 = @_rg[k1][k3] + @_rg[k2][k4]
wa2 = @_rg[k1][k4] + @_rg[k2][k3]
if sw == 0 || wa1-wd < min
min = wa1 - wd
r3 = i1
r4 = i2
if i3 == @_n_seq[r1][r2]-1
s1 = 0
else
s1 = i3 + 1
end
if i4 == @_n_seq[i1][i2]-1
s2 = 0
else
s2 = i4 + 1
end
sw = -1
end
if sw == 0 || wa2-wd < min
min = wa2 - wd
r3 = i1
r4 = i2
s1 = i3
if i4 == @_n_seq[i1][i2]-1
s2 = 0
else
s2 = i4 + 1
end
sw = 1
end
end
end
# 節点の数＝１
else
k1 = @_seq[r1][r2][0]
if @_n_seq[i1][i2] > 1
for i4 in 0 ... @_n_seq[i1][i2]
k3 = @_seq[i1][i2][i4]
if i4 == @_n_seq[i1][i2]-1
k4 = @_seq[i1][i2][0]
else
k4 = @_seq[i1][i2][i4+1]
end
wd = @_rg[k3][k4]
wa1 = @_rg[k1][k3] + @_rg[k1][k4]
if sw == 0 || wa1-wd < min
min = wa1 - wd
r3 = i1
r4 = i2
s1 = 0
if i4 == @_n_seq[i1][i2]-1
s2 = 0
else
s2 = i4 + 1
end
sw = 1
end
end
else
k3 = @_seq[i1][i2][0]
wa1 = @_rg[k1][k3]
if sw == 0 || wa1 < min
min = wa1
r3 = i1
r4 = i2
s1 = 0
s2 = 0
sw = 1
end
end
end
end
end
end
# 領域の結合
@_seq_w1[0] = @_seq[r1][r2][s1]
k = 1
n = s2
for i1 in 0 ... @_n_seq[r3][r4]
@_seq_w1[k] = @_seq[r3][r4][n]
k += 1
n += 1
if n > @_n_seq[r3][r4]-1
n = 0
end
end
if sw > 0
n = s1 + 1
for i1 in 0 ... @_n_seq[r1][r2]-1
if n > @_n_seq[r1][r2]-1
n = 0
end
@_seq_w1[k] = @_seq[r1][r2][n]
k += 1
n += 1
end
else
n = s1 - 1
for i1 in 0 ... @_n_seq[r1][r2]-1
if n < 0
n = @_n_seq[r1][r2] - 1
end
@_seq_w1[k] = @_seq[r1][r2][n]
k += 1
n -= 1
end
end
# 状態の変更
@_n_seq[r1][r2] += @_n_seq[r3][r4]
@_state[r3][r4] = 1
for i1 in 0 ... @_n_seq[r1][r2]
@_seq[r1][r2][i1] = @_seq_w1[i1]
end
sw = 1
end
end
end
if @_seisu > -2
r = Integer(kyori(@_n_city, @_seq_w1, @_rg))
else
r = kyori(@_n_city, @_seq_w1, @_rg).round()
end
@_max = r
return r
end
attr("_out_m", true)
attr("_o_file", true)
attr("_max", true)
end
# 入力ミス
if ARGV[0] == nil
print("***error ファイル名を入力して下さい\n")
# 入力ＯＫ
else
# 問題数と入力データファイル名
line = gets()
a = line.split(" ")
nm = Integer(a[1])
aa = Array.new(nm)
for i0 in 0 ... nm
aa[i0] = gets()
end
for i0 in 0 ... nm
# 各問題の実行
a = aa[i0].split(" ")
i_file = a[1]
n = Integer(a[3])
pt = Partition.new(i_file)
mean = 0.0
max = -1
# 乱数の初期値を変える
for i1 in 0 ... n
print("\n+++++問題 " + i_file + " +++++\n")
srand(1000 * i1 + 1234567);
# 最適化
pt.Optimize()
# 最適値とその平均の計算
mean += pt._max
if max < 0 or pt._max < max
max = pt._max
end
end
# 結果
if pt._out_m <= 0
print(" -----最小 " + String(max) + " 平均 " + String(mean/n) + "-----\n")
else
out = open(pt._o_file, "a")
out = open("out.txt", "a")
printf(out, " -----最小 " + String(max) + " 平均 " + String(mean/n) + "-----\n")
out.close()
end
end
end
=begin
------------------------ケーススタディデータ(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
=end