Solve TSP problem by Hillclimbing

本文使用爬山演算法解決 TSP 問題，並用 Gnuplot 輸出結果圖。

定義 TSP 問題

以圖論定義問題：

一張 N 個點的完全圖 G，找一張 cost 最小的 Hamiltonian Graph。

簡單來說，就是 N 個點，每個點之間都有一條邊，在每個點都恰好走一次的情況下，找到從起點繞完所有點後回到起點、且距離最短的路徑。

解決 TSP 問題

競賽常見作法是 DP 及 Branch and Bound，範圍超級小時也有人用窮舉做。實務上通常使用啟發式演算法，例如本文的爬山演算法，或是進階一點的模擬退火。

爬山演算法(Hill Climbing)

考慮這張我用小畫家隨手畫的圖，橫的為 x、直的為 f(x)，要找最大的 f(x)。

• 暴力解
  • 遍歷 x，紀錄最大的 f(x)
  • 很直覺，但如果 x 的範圍為 [0, 1e9]、且間距為 0.01 呢？
• 爬山演算法
  • 一直往前走並更新答案，如果太久沒有更大的值，就當作以後都沒有。
  • 以本文的圖來說，可能第一個波峰到第四個波峰花費時間太久，導致答案為第一個波峰。故本文的爬山方法為從隨機一個新的點去做，來嘗試尋找真正的最大值。

實際做法(python3.7)

測試資料為 eil51-tsp.txt，第七行才開始有資料，資料格式為{$i $x_i $y_i}

def readData():
    with open("eil51-tsp.txt") as file:
        lines = file.read().splitlines()[6:-1]
        return list(map(lambda x: list(map(int, x.split(' ')))[1:], lines))

可以看出我們存的結構為 [[x_1, y_1], [x_2, y_2], … [x_n, y_n]]。

根據爬山算法的概念，知道流程為: 找一個點後開始做，更新最佳解的答案。若太久沒更新，則假設目前得最佳解為實際最佳解。確認後可以直接上 code!

(一開始用遞迴，後來還是改迴圈了)

def solve(current, n): #目前資料為 current, n 次沒更新就結束
    k = 0
    while k < n:
        guess = swapValue(current[:]) #找新的點
        if getTotalDistance(guess) <= getTotalDistance(current): #更新最佳解
            k = 0
            current = guess
        else:
            k = k + 1
    current.append(current[0])
    return current

getDistance 單純在套距離公式，getTotalDistance 則是以目前的順序做的解，swapValue 為交換任意兩點讓路徑更新。

def getDistance(a, b):
    return pow(((a[0] - b[0]) ** 2) + ((a[1] - b[1]) ** 2), 0.5)

def getTotalDistance(data):
    return sum([getDistance(j,  data[i-1]) for i, j in enumerate(data)])

def swapValue(data):
    a = [0 for i in range(2)]
    while a[0] == a[1]:
        a = [random.randint(0, len(data)-1) for i in range(2)]
    data[a[0]], data[a[1]] = data[a[1]], data[a[0]]
    return data

基本上這樣就做完了，並沒有想像的難XD

繪圖

事前需下載 gnuplot，ubuntu 可直接下

sudo apt install gnuplot

做完爬山算法後，將結果存成檔案，格式為 $x_i$<空格>$y_i$<換行>$x{i+1}$<空格>$y_{i+1}$<換行> 直到 i = 點數 + 1。我們假設存成 output.txt。 傳寫一個 run.gp 檔，內容為：

unset key
set terminal png
set output 'result.png'
plot "output.txt" with linespoints pointtype 7 pointsize 1

第一行為不要輸出有的沒的(例如讀入的檔名)；第二行設定輸出 png 檔；第三行設定輸出到的檔名；遞四行表示讀入 “output.txt” 並繪製每個點及連線，後面兩個可看個人喜好。 接著進 terminal 下指令：

gnuplot run.gp

就會發現多一個 result.png 囉！若想即時觀看檔案，可以下 -p 參數來 preview。 在 python 能 import os 後直接執行指令，或是 subprocess 進入互動介面(不寫 gp file)

Repo

本文的完整程式碼可於 Github 找到