Web | Coding | Blog | SOHO

[程式語言]PokemonGo-TSP 補給站的最佳路徑規劃

作者因滑鐵盧大學分享的一篇PokemonGo最佳路徑規劃文章 [1] 而啟發,加上也瘋著此款遊戲,因此決定動手試著做。


那麼什麼是TSP呢?

TSP全名Travelling salesman problem,中文翻譯做「旅行商問題」[2]
給定一系列城市和每對城市之間的距離,求解訪問每一座城市一次並回到起始城市的最短迴路

在 Computer Science 內屬於NP Hard的難題

image


而 SA又是什麼呢?

SA全名Simulated Annealing,中文翻譯做「模擬退火」[3] [4]

一種基於熱力學原理的隨機搜尋演算法,用來在固定時間內在一個大的搜尋空間內找最優解

image


用Python實現模擬退火來計算TSP
目前的Repo內的數據是交大校內的補給站(78個點)
其他地方的資料可以用PokemonGo-Map來抓取


直接執行python tsp.py, 預設會讀取data/pokestops.csv

跑出結果後會畫出cost function和route, 結果如下

image

作者將其套用至地圖上像這個樣子:

作者的話:目前是人工手拉的地圖,希望未來能夠自動整合到地圖上QQ

image

作者的話:用Google Map API 來計算實際地理距離目前還有點雷,像是操場/壘球場這種地方會繞一大圈而不是直接穿越


相信很快便有更多Pokemon GO 的相關輔助程式(非外掛)造福各個訓練家。
如果可以與寶貝地圖相結合,覺得是相當不錯的點子。
一邊可以照著最佳路線走,也可以一邊捕捉神奇寶貝,到了寶可夢驛站又可以補充身上的物品。


如果您喜歡本站的文章,也歡迎將文章分享轉貼並註明出處;
另外還未按讚粉絲專頁的朋友,也可以動動手點擊追蹤最新的文章唷:


相關連結:

作者GitHub:https://github.com/tnlin/PokemonGo-TSP

python taiwan:
https://www.facebook.com/groups/pythontw/permalink/10155311297603438/

 

Comments

comments

如果您喜歡本站的文章,也歡迎將文章分享轉貼並註明出處;另外還未按讚粉絲專頁的朋友,也可以動動手點擊追蹤最新的文章唷:


© 2017 4xCode™ | Design:SC 站長

歡迎來到SC站長網站

 

本站文章不再更新,新文章將發表至

4 x ‘s Space 網站

 

謝謝您一直以來的支持,我們新網站見~

 

SC站長網站文章也會將慢慢轉移至新網站,

新網站連結 4-x.tw 點此前往,或點擊上方圖案)