ぱそきいろのIT日記

ぱそきいろがITに関する記事を書いていきます。

巡回セールスマン問題をTkinterで可視化(ディズニーランドの最適化)

こんにちは、ぱそきいろです。

少し前ですけど、「理系が恋に落ちたので証明してみた。」がアニメで放送されてました。
rikekoi.com

情報系の理系が見るととても面白かったです。
その中で主人公二人がテーマパークに行くシーンがありました。
(以下、いらすとや による再現)
f:id:takabsk55:20200530162145j:plain:h240

f:id:takabsk55:20200530162209j:plain:h240

f:id:takabsk55:20200530162228j:plain:h240
実は、自分も同じことを考えたことがありました笑
いい機会なので実際に作ってみようと思います。

ただ、ディズニーランドで巡回セールスマン問題を解くのは、既にいろんな人がトライしています。
とりあえず、可視化するところをメインに作ってみることにしました。

ちなみに、完成形はこんな感じになりました。


よろしくお願いします。

方針

ディズニーランドのアトラクションをいくつか選び、それらを巡る最短経路を求めます。
アトラクションの場所は必ずしも正確ではなく、経路も直線距離で考えていきます。
(実際の道なりは計測できないので分からない、、、)
クリックして行きたい場所を選択、計算ボタンを押して最短経路を表示するようにします。

最短経路を求める方法はいろんな人がやっているので、可視化するところをメインに作っていこうと思います。
過去にTkinterを使ったことがあるのでこれを使って実装していきます。
www.takacpu55.xyz

巡回セールスマン問題

巡回セールスマン問題を実装してくれている人は多いので、ここはあまり力を入れないことにします。
PythonでPuLPを使う方法が簡単そうだったので、下のリンクを参照して実装します。
(ほぼコピペだったので、コードは割愛します)
www.nct9.ne.jp

Tkinterで可視化

イメージとしては、以下のような感じを考えてます。
まずは、ディズニーランドの地図を表示します。
f:id:takabsk55:20200527003817p:plain:h240

この上に点をプロットします。
f:id:takabsk55:20200527003940p:plain:h240

点同士の最短経路を求めていくことにします。
f:id:takabsk55:20200527003956p:plain:h240

クリアーボタンを作ったり、点を追加したら経路を再計算するようにしておきます。

画像の表示がうまくいかず、詰まりました。
imgをglobalで宣言することで解決しました。
teratail.com

コードが長いので最後に載せておきます。
適宜コメントを入れてるから分かるかと思います。

できたもの

初めにも載せたのですが、もう一度載せておきます。



まとめ

ディズニーランドでアトラクションの最短経路を可視化しました。
巡回セールスマンの実装はサボりました←
可視化を頑張ったので許してください。
いつになったらディズニーランド再開するんですかね。
(特に行く予定はないけど、、)

コード
# -*- 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()