# -*- 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
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 :
############################
# コンストラクタ
# name : ファイル名
############################
def __init__(self, name) :
# ファイルのオープン
inn = open(name, "r")
# 基本データ
s = inn.readline().split()
self.n_city = int(s[1]) # 都市の数
self.max_try = int(s[3]) # 最大試行回数
self.sel = int(s[5]) # エッジの選択方法
# =0 : 最良のものを選択
# =1 : 最初のものを選択
self.neib = int(s[7]) # 近傍（2 or 3）
s = inn.readline().split()
self.out_lvl = int(s[1]) # 出力レベル
# =0 : 最終出力だけ
# n>0 : ｎ回毎に出力（負の時はファイル）
self.out_m = int(s[3]) # 出力方法
# =-1 : 出力しない
# =0 : すべてを出力
# =1 : 評価値だけを出力（最終結果だけはすべてを出力）
s = inn.readline().split()
self.o_file = s[1] # 出力ファイル名
self.out_d = int(s[3]) # 表示間隔
# 都市の位置データ
self.city = np.empty((self.n_city, 2), np.int)
for i1 in range(0, self.n_city) :
s = inn.readline().split()
self.city[i1][0] = int(s[0])
self.city[i1][1] = int(s[1])
# ファイルのクローズ
inn.close()
# 距離テーブルの作成
self.rg = np.empty((self.n_city, self.n_city), np.int) # 都市間の距離
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] = int(sqrt(x * x + y * y) + 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.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) # 都市を訪れる順序（ワーク）
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.int)
max[0] = kyori(self.n_city, self.seq, self.rg)
if self.out_m >= 0 and abs(self.out_lvl) > 0 :
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 :
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
k1 = self.out_m
self.out_m = 0
print("***試行回数 " + str(n_tri) + " 距離 " + str(-max[0]))
self.Output(self.out_lvl, n_tri, max[0])
self.out_m = k1
return n_tri
###############################
# 出力
# sw : >=0 : 出力先未定
# <0 : ファイル
# n_tri : 現在の試行回数
# r : 距離の負値
###############################
def Output(self, sw, n_tri, r) :
k = 0
pr = -1
if sw >= 0 :
pr = int(input(" 出力先は（0:出力なし，n:画面にｎ個づつ，-1:ファイル）？ "))
if pr != 0 :
if pr > 0 :
out = sys.stdout
input("")
else :
now = datetime.today().time().isoformat()
out = open(self.o_file, "a")
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]
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) :
ch = 0
sw = 0
max = r_m[0]
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 :
n1 = self.n_city - 1
if n3 == 0 :
n1 = self.n_city - 2
i2 = n3 + 2
while i2 <= n1 and ch == 0 :
# 枝の場所（(n3,n3+1), (k1,k2)）
k1 = i2
k2 = i2 + 1
if i2 == self.n_city-1 :
k2 = 0
# 枝の入れ替え
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
k2 = i3 + 1
if i3 == self.n_city-1 :
k2 = 0
# 枝の入れ替えと評価
# 入れ替え（その１）
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
----------------------------------
# -*- coding: UTF-8 -*-
import numpy as np
import sys
from math import *
from random import *
from function import Iteration
####################################
# 巡回セールスマン問題（反復改善法）
# coded by Y.Suganuma
####################################
# 入力ミス
if len(sys.argv) <= 1 :
print("***error ファイル名を入力して下さい")
# 入力ＯＫ
else :
# データの数と入力データファイル名の入力
inn = open(sys.argv[1], "r")
ss = inn.readline()
n = int(ss) # データの数
i_file = []
for i1 in range(0, n) :
i_file.append(inn.readline().strip(" \n"))
inn.close()
# 実行
for i1 in range(0, n) :
print("\n+++++ケース " + str(i1+1) + "+++++")
# 入力と初期設定
it = Iteration (i_file[i1])
# 最適化
it.Optimize()
------------------------ケーススタディデータ------
3
data2.txt
data2.txt
data3.txt
------------------データファイル(data2.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
------------------データファイル(data3.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