誰かがすでに言っている？それともアルゴリズムの世界ではすでに常識、私自身知っていたが忘れた、かは知らない。
(かなり明快なので誰も気づかないとは思えないけど...）
複数点を結ぶ最短距離は交差しない
100個程度の座標を最短距離で結ぶアルゴリズム
全点の中の数点を選びその入れ替えを全パターン試してもっとも短いものを選択していく
これを延々繰り返す。
プログラムを少し大きめにして、任意の点を選ぶと、その近くの数点を全入れ替えするロジックを入れてみたもの
いずれもまったく交差していない。
上の２つは最短ではない（おそらく）
初期のリンクデータはそこそこ並んでいるもので（教師ありデータのようなもの）
このリンクデータをごそっとソートかけてから実行すると大きな輪が幾重にも重なったようになって、数点の入れ替えでは解消されない。
作成環境
ubuntu 18.04
Python 3.7.3
pygame 1.9.6
＜ソースリスト＞
import pygame, random, os, copy, itertools
from pygame.locals import *
os.environ['SDL_VIDEO_WINDOW_POS'] = "%d,%d" % (100,100)
pygame.init()
screen = pygame.display.set_mode((1000, 800))
font = pygame.font.SysFont("notosansmonocjkjp", 32)
class Siro:
def __init__(t, line):
_, t.name, t.id, t.kd, t.add = line.split(",") #城名 緯度 軽度
t.id, t.kd = int(float(t.id)*100), int(float(t.kd)*100)
t.px, t.py = 0, 0 #画面上の表示位置
t.pos = ()
def setPos(t, minX, maxX, minY, maxY): #画面上の表示位置の計算
x = t.kd - minX
y = t.id - minY
sx = maxX - minX
sy = maxY - minY
t.px = int(900 * x / sx) + 50
t.py = 750 - int(700 * y / sy)
t.pos=(t.px, t.py)
def length(t, siro): #他の城との距離（画面上）
return ((t.px - siro.px) **2 + (t.py - siro.py) **2) **0.5
def lengthXY(t, x, y): #他の城との距離（画面上）
return ((t.px - x) **2 + (t.py - y) **2) **0.5
def totalLength(p): #pの順番で城をつないだ時の総距離
global siros
r=0
for n, i in enumerate(p[1:]):
r += siros[p[n]].length( siros[p[n+1]] )
return r
def mazemaze(p,n): #順番をランダムに入れ替える（csvデータが良いため値は悪くなる)
for i in range(n):
r1 = random.randint(0, len(p) - 1)
r2 = random.randint(0, len(p) - 1)
if r1 != r2:
p[r1], p[r2]=p[r2], p[r1]
return p
def locatePrint(x, y, s):
text = font.render(s, True, (255, 255, 255))
screen.blit(text, [x * 50, y * 50])
def nearSet(near,pn,siroNum):
global siros
lengthData=[]
for i in range(siroNum):
lengthData+=[[siros[i].length(siros[near]),i]]
lengthData.sort()
tp=()
r=[]
for i in range(pn):
r+=[lengthData[i][1]]
tp += (i,)
return r,tp
bLength = 1000000
siros = []
def main():
global siros, bLength
csv_data = open("./siro2.csv", "r")
lines = csv_data.readlines()
for line in lines:
if len(line) > 0:siros += [Siro(line)]
csv_data.close()
minX = min([i.kd for i in siros])
maxX = max([i.kd for i in siros])
minY = min([i.id for i in siros])
maxY = max([i.id for i in siros])
for i in siros:
i.setPos(minX, maxX, minY, maxY)
siroNum=len(siros)
path=[i for i in range(siroNum)]
#path=mazemaze(path,1000) #CSV時の経路をバラバラにする
end_game = False
near=-1
nearSw=0
while not end_game:
for event in pygame.event.get():
if event.type == pygame.QUIT:
end_game = True
if event.type == MOUSEBUTTONDOWN and event.button == 1:
x, y = event.pos
bl=100000
for i in range(siroNum):
l=siros[i].lengthXY(x,y)
if l<bl:
bl=l
near=i
nearSw=1
screen.fill((100, 100, 250))
for n, i in enumerate(path[1:]): #経路の可視化
pygame.draw.line(screen, (0, 0, 0), siros[path[n]].pos, siros[i].pos,3)
for n, i in enumerate(siros): #城位置の可視化
if near==n:
pygame.draw.rect(screen, (250, 50, 50), Rect(i.px-5, i.py-5, 10, 10))
elif path[0]==n or path[siroNum-1]==n:
pygame.draw.rect(screen, (100, 250, 100), Rect(i.px-5, i.py-5, 10, 10))
else:
pygame.draw.rect(screen, (250, 250, 250), Rect(i.px-5, i.py-5, 10, 10))
locatePrint(1, 1, str(int(bLength))) #現在の最短距離
if near>-1:locatePrint(1, 2, siros[near].name+" "+siros[near].add)
pygame.display.flip()
sw = 0
c=0
while sw < 1:
c+=1
if c>2:break
pn = 5 #一度に入れ替える数 大きいと逆に遅くなる
r = []
tp = ()
if nearSw==1:
pn=8
r,tp = nearSet(near,pn,siroNum)
nearSw=0
else:
for i in range(pn):
r += [random.randint(0, len(path)-1)]
tp += (i,) #タプルに1つだけ追加する時はカンマが必要
if len(set(r)) != pn:continue #同じ番号が選択させていたらパス
for i in list(itertools.permutations(tp)): #入れ替えのパターン作成
p = copy.deepcopy(path)
for j in range(pn):
p[ r[j] ] = path[ r[i[j]] ]
length = totalLength(p)
if length < bLength:
bLength = length
path = p
sw = 1
pygame.quit()
quit()
main()
＜CSVデータ＞マップを大きく見せるため沖縄と北海道の1つはけずっています。
ファイル名 siro2.csv プログラムファイルと同じフォルダに必要
＜参考資料＞
------ここから
2,五稜郭,41.7972222,140.7569444,北海道函館市
3,松前城,41.4297222,140.1083333,北海道松前町
4,弘前城,40.6075,140.4638888,青森県弘前市
5,根城,40.5061111,141.4605555,青森県八戸市
6,盛岡城,39.7005555,141.15,岩手県盛岡市
7,多賀城,38.3066666,140.9883333,宮城県多賀城市
8,仙台城,38.2530555,140.8555555,宮城県仙台市
9,久保田城,39.7227777,140.1236111,秋田県秋田市
10,山形城,38.2555555,140.3283333,山形県山形市
11,二本松城,37.5994444,140.4277777,福島県二本松市
12,会津若松城,37.4875,139.9297222,福島県会津若松市
13,白河小峰城,37.1325,140.2133333,福島県白河市
14,水戸城,36.3752777,140.4769444,茨城県水戸市
15,足利氏館,36.3375,139.4522222,栃木県足利市
16,箕輪城,36.405,138.9508333,群馬県高崎市
17,金山城,36.3169444,139.3777777,群馬県太田市
18,鉢形城,36.1091666,139.1958333,埼玉県寄居町
19,川越城,35.9247222,139.4913888,埼玉県川越市
20,佐倉城,35.7222222,140.2158333,千葉県佐倉市
21,江戸城,35.6872222,139.7552777,東京都千代田区
22,八王子城,35.6530555,139.2527777,東京都八王子市
23,小田原城,35.2513888,139.1536111,神奈川県小田原市
24,武田氏館,35.6866666,138.5766666,山梨県甲府市
25,甲府城,35.6652777,138.5713888,山梨県甲府市
26,松代城,36.5658333,138.1958333,長野県長野市
27,上田城,36.4036111,138.2444444,長野県上田市
28,小諸城,36.3269444,138.4169444,長野県小諸市
29,松本城,36.2386111,137.9688888,長野県松本市
30,高遠城,35.8327777,138.0625,長野県伊那市
31,新発田城,37.9552777,139.3252777,新潟県新発田市
32,春日山城,37.1466666,138.2055555,新潟県上越市
33,高岡城,36.7491666,137.0208333,富山県高岡市
34,七尾城,37.0086111,136.9838888,石川県七尾市
35,金沢城,36.5636111,136.6594444,石川県金沢市
36,丸岡城,36.1519444,136.2722222,福井県坂井市
37,一乗谷城,35.9958333,136.3080555,福井県福井市
38,岩村城,35.3597222,137.4511111,岐阜県恵那市
39,岐阜城,35.4338888,136.7822222,岐阜県岐阜市
40,山中城,35.1561111,138.9919444,静岡県三島市
41,駿府城,34.9791666,138.3830555,静岡県静岡市
42,掛川城,34.775,138.0138888,静岡県掛川市
43,犬山城,35.3883333,136.9391666,愛知県犬山市
44,名古屋城,35.1858333,136.8994444,愛知県名古屋市
45,岡崎城,34.9561111,137.1588888,愛知県岡崎市
46,長篠城,34.9227777,137.5597222,愛知県新城市
47,伊賀上野城,34.77,136.1272222,三重県伊賀市
48,松阪城,34.5758333,136.5255555,三重県松阪市
49,小谷城,35.4588888,136.2763888,滋賀県長浜市
50,彦根城,35.2763888,136.2516666,滋賀県彦根市
51,安土城,35.1558333,136.1391666,滋賀県近江八幡市
52,観音寺城,35.1458333,136.1577777,滋賀県近江八幡市
53,二条城,35.0141666,135.7477777,京都府京都市
54,大阪城,34.6875,135.5258333,大阪府大阪市
55,千早城,34.4169444,135.6513888,大阪府千早赤阪村
56,竹田城,35.3,134.8288888,兵庫県朝来市
57,篠山城,35.0730555,135.2175,兵庫県篠山市
58,明石城,34.6525,134.9916666,兵庫県明石市
59,姫路城,34.8394444,134.6938888,兵庫県姫路市
60,赤穂城,34.7458333,134.3891666,兵庫県赤穂市
61,高取城,34.4291666,135.8275,奈良県高取町
62,和歌山城,34.2275,135.1713888,和歌山県和歌山市
63,鳥取城,35.51,134.2411111,鳥取県鳥取市
64,松江城,35.475,133.0505555,島根県松江市
65,月山富田城,35.3608333,133.1847222,島根県安来市
66,津和野城,34.46,131.7641666,島根県津和野町
67,津山城,35.0627777,134.005,岡山県津山市
68,備中松山城,34.8088888,133.6219444,岡山県高梁市
69,鬼ノ城,34.7275,133.7677777,岡山県総社市
70,岡山城,34.665,133.9361111,岡山県岡山市
71,福山城,34.4908333,133.3611111,広島県福山市
72,郡山城,34.6736111,132.7094444,広島県安芸高田市
73,広島城,34.4025,132.4591666,広島県広島市
74,岩国城,34.1752777,132.1741666,山口県岩国市
75,萩城,34.4213888,131.3813888,山口県萩市
76,徳島城,34.0752777,134.555,徳島県徳島市
77,高松城,34.3502777,134.0516666,香川県高松市
78,丸亀城,34.2861111,133.8005555,香川県丸亀市
79,今治城,34.0633333,133.0069444,愛媛県今治市
80,湯築城,33.8486111,132.7863888,愛媛県松山市
81,松山城,33.8455555,132.7655555,愛媛県松山市
82,大洲城,33.5094444,132.5411111,愛媛県大洲市
83,宇和島城,33.2191666,132.565,愛媛県宇和島市
84,高知城,33.5608333,133.5311111,高知県高知市
85,福岡城,33.5847222,130.3830555,福岡県福岡市
86,大野城,33.5397222,130.5230555,福岡県大野城市
87,名護屋城,33.5302777,129.8691666,佐賀県唐津市
88,吉野ヶ里,33.3247222,130.3833333,佐賀県吉野ヶ里町
89,佐賀城,33.2452777,130.3027777,佐賀県佐賀市
90,平戸城,33.3683333,129.5575,長崎県平戸市
91,島原城,32.7891666,130.3672222,長崎県島原市
92,熊本城,32.8061111,130.7058333,熊本県熊本市
93,人吉城,32.2111111,130.7663888,熊本県人吉市
94,大分府内城,33.2405555,131.6113888,大分県大分市
95,岡城,32.9691666,131.4077777,大分県竹田市
96,飫肥城,31.6288888,131.35,宮崎県日南市
97,鹿児島城,31.5986111,130.5547222,鹿児島県鹿児島市
