こんにちは、ぱそきいろです。
少し前ですけど、「理系が恋に落ちたので証明してみた。」がアニメで放送されてました。
rikekoi.com
情報系の理系が見るととても面白かったです。
その中で主人公二人がテーマパークに行くシーンがありました。
（以下、いらすとや による再現）
実は、自分も同じことを考えたことがありました笑
いい機会なので実際に作ってみようと思います。
ただ、ディズニーランドで巡回セールスマン問題を解くのは、既にいろんな人がトライしています。
とりあえず、可視化するところをメインに作ってみることにしました。
ちなみに、完成形はこんな感じになりました。
ディズニーランドのアトラクションをどうやったら効率的に回れるのか。
— ぱそきいろ (@takacpu55) 2020年6月1日
巡回セールスマン問題として最適な経路を求めてみた。 pic.twitter.com/lbiCHy37ho
よろしくお願いします。
方針
ディズニーランドのアトラクションをいくつか選び、それらを巡る最短経路を求めます。
アトラクションの場所は必ずしも正確ではなく、経路も直線距離で考えていきます。
（実際の道なりは計測できないので分からない、、、）
クリックして行きたい場所を選択、計算ボタンを押して最短経路を表示するようにします。
最短経路を求める方法はいろんな人がやっているので、可視化するところをメインに作っていこうと思います。
過去にTkinterを使ったことがあるのでこれを使って実装していきます。
www.takacpu55.xyz
巡回セールスマン問題
巡回セールスマン問題を実装してくれている人は多いので、ここはあまり力を入れないことにします。
PythonでPuLPを使う方法が簡単そうだったので、下のリンクを参照して実装します。
（ほぼコピペだったので、コードは割愛します）
www.nct9.ne.jp
Tkinterで可視化
イメージとしては、以下のような感じを考えてます。
まずは、ディズニーランドの地図を表示します。
この上に点をプロットします。
点同士の最短経路を求めていくことにします。
クリアーボタンを作ったり、点を追加したら経路を再計算するようにしておきます。
画像の表示がうまくいかず、詰まりました。
imgをglobalで宣言することで解決しました。
teratail.com
コードが長いので最後に載せておきます。
適宜コメントを入れてるから分かるかと思います。
できたもの
初めにも載せたのですが、もう一度載せておきます。
ディズニーランドのアトラクションをどうやったら効率的に回れるのか。
— ぱそきいろ (@takacpu55) 2020年6月1日
巡回セールスマン問題として最適な経路を求めてみた。 pic.twitter.com/lbiCHy37ho
まとめ
ディズニーランドでアトラクションの最短経路を可視化しました。
巡回セールスマンの実装はサボりました←
可視化を頑張ったので許してください。
いつになったらディズニーランド再開するんですかね。
（特に行く予定はないけど、、）
コード
# -*- coding:utf-8 -*-
import tkinter
from tkinter import *
from PIL import Image,ImageTk
import matplotlib
#巡回セールスマン問題を解くソルバーを別で作ってインポートする
from solver import solver2
matplotlib.use("Agg")
class Scribble:
points=[]
# ボタンが押された
def on_pressed(self, event):
self.canvas.create_oval(event.x-self.width, event.y-self.width, event.x+self.width, event.y+self.width,
fill="red",
outline="red",
#width=self.width,
tag="red"
)
self.points.append([event.x,event.y])
# ウィンドウを作る
def create_window(self):
window = tkinter.Tk()
window.title("巡回セールス問題")
#これをしておかないとうまく画像が表示されない
global photo
img=Image.open("map.jpg")
photo=ImageTk.PhotoImage(img)
self.canvas = tkinter.Canvas(window, background="white",
width=800, height=580)
self.canvas.pack()
self.canvas.create_image(0, 0, image=photo, anchor=tkinter.NW)
quit_button = tkinter.Button(window, text="終了",
command=window.quit)
quit_button.pack(side=tkinter.RIGHT)
delete_button=tkinter.Button(window,text="クリアー",command=self.delete)
delete_button.pack(side=tkinter.RIGHT)
calc_button = tkinter.Button(window, text="計算", command=self.calc)
calc_button.pack(side=tkinter.RIGHT)
self.canvas.bind("<ButtonPress-1>", self.on_pressed)
self.color="red"
self.width=10
return window;
def run(self):
self.window.mainloop()
def delete(self):
self.points=[]
self.canvas.delete("red")
self.canvas.delete("line")
def calc(self):
#ここでpointsを渡して最短経路を求める
x=solver2(self.points)
ansroute=[]
routenow=0
self.canvas.delete("line")
for i in range(len(self.points)):
for j in range(len(self.points)):
if x[i][j].varValue==1.0:
ansroute.append((i,j))
for i in range(len(ansroute)):
self.canvas.create_line(self.points[ansroute[i][0]][0], self.points[ansroute[i][0]][1],
self.points[ansroute[i][1]][0], self.points[ansroute[i][1]][1],
fill="red",tag="line",width=10)
print(ansroute)
def __init__(self):
self.window = self.create_window(); # 呼び出すときはself. + メソッド名
# 開始
Scribble().run()