最近被滑鐵盧大學分享的一篇PokemonGo最佳路徑規劃文章而 [1] 啟發
於是決定動手試試，拿模擬退火來解決實際生活中的TSP問題
TSP全名Travelling salesman problem，中文翻譯做「旅行商問題」2
給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短迴路
在 Computer Science 內屬於NP Hard的難題
SA全名Simulated Annealing，中文翻譯做「模擬退火」[3] [4]
一種基於熱力學原理的隨機搜尋演算法，用來在固定時間內在一個大的搜尋空間內找最優解
直接執行python tsp.py, 預設會讀取data/pokestops.csv
跑出結果後會畫出cost function和route, 結果如下
最後再把結果存入data/tsp.sqlite內，方便未來分析
推薦下載 Sqlite Browser GUI管理工具來開啟資料庫
markov_step = 10 * num # 內循環次數
T = 100 # 初始溫度
T = 1 # 最低溫度
T_ALPHA = 0.99 # 退溫常數
如果想要得到更好的解，增加markov_step是個好辦法
markov_step = 100 * num # 內循環次數
Barrier avoidance
- Parallelization
- Reannealing
- Cooling schedule
[1]Pokemon Go Traveling Salesman Problem - 國外的Pokemon Go TSP
[2]Travelling salesman problem - TSP背景知識
[3]Simulated annealing - 模擬退火背景知識
[4]模拟退火算法求解旅行商问题 - 詳盡的模擬退火解說 ＋ Java實現，提到了三種產生新狀態的方式
[5]Queen of College Tours - 從Geometric TSP 到 Road TSP
[6]PokemonGo-Map - 地圖掃描工具，從pogom.db獲取道館/補給站座標