こんにちは、ぱそきいろです。
少し前ですけど、「理系が恋に落ちたので証明してみた。」がアニメで放送されてました。
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()