DSA 旅行商問題

旅行商問題

旅行商問題指出，你是一名推銷員，必須拜訪若干個城市或城鎮。

除了 Held-Karp 演算法（該演算法非常高階且耗時，(\(O(2^n n^2)\))，此處不作描述）之外，沒有其他方法可以找到最短路線，只能透過檢查所有可能的路線。

這意味著解決此問題的時空複雜度為 \(O(n!)\)，即對於 6 個城市需要檢查 720 條路線，對於 8 個城市必須檢查 40,320 條路線，如果你需要訪問 10 個城市，則需要檢查超過 360 萬條路線！

旅行商問題 (TSP) 是一個值得研究的問題，因為它非常實用，但又非常耗時，以至於即使在一個只有 20-30 個頂點的圖中，也幾乎不可能找到最短路線。

如果我們有一個有效的演算法來解決旅行商問題，那麼在許多領域將產生巨大的影響，例如晶片設計、車輛路徑規劃、電信和城市規劃。

檢查所有路線以解決旅行商問題

為了找到旅行商問題的最優解，我們將檢查所有可能的路線，並且每次找到一條更短的路線時，我們都會將其儲存起來，這樣最終我們就能得到最短的路線。

優點：找到全域性最短路線。

缺點：需要大量的計算，特別是對於大量城市，這意味著它非常耗時。

這種尋找問題解決方案的方式稱為蠻力法。

蠻力法並非真正的演算法，它只是指透過檢查所有可能性來找到解決方案，通常是因為缺乏更好的方法。

正如上面所示，旅行商問題的蠻力法之所以如此耗時，是因為我們在檢查所有路線，而當城市數量增加時，可能路線的數量會急劇增加。

from itertools import permutations

def calculate_distance(route, distances):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distances[route[i]][route[i + 1]]
    total_distance += distances[route[-1]][route[0]]
    return total_distance

def brute_force_tsp(distances):
    n = len(distances)
    cities = list(range(1, n))
    shortest_route = None
    min_distance = float('inf')
    
    for perm in permutations(cities):
        current_route = [0] + list(perm)
        current_distance = calculate_distance(current_route, distances)
        
        if current_distance < min_distance:
            min_distance = current_distance
            shortest_route = current_route
    
    shortest_route.append(0)
    return shortest_route, min_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = brute_force_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

使用貪婪演算法解決旅行商問題

由於檢查所有可能的路線來解決旅行商問題（如我們上面所做的）非常耗時，我們可以改為透過在每一步都前往最近的未訪問城市來找到一條短路線，這要快得多。

優點：比檢查所有路線的速度快得多地找到旅行商問題的解決方案。

缺點：找不到全域性最短路線，它只找到一條比平均隨機路線短得多的路線。

這種在旅行商問題中尋找最短路線近似值的方法，即在每一步都前往最近的未訪問城市，稱為貪婪演算法。

正如你透過執行此模擬幾次所見，找到的路線並非完全不合理。除了偶爾出現的線路交叉（尤其是在演算法後期），結果路線比隨機選擇下一個城市所得到的路線要短得多。

def nearest_neighbor_tsp(distances):
    n = len(distances)
    visited = [False] * n
    route = [0]
    visited[0] = True
    total_distance = 0

    for _ in range(1, n):
        last = route[-1]
        nearest = None
        min_dist = float('inf')
        for i in range(n):
            if not visited[i] and distances[last][i] < min_dist:
                min_dist = distances[last][i]
                nearest = i
        route.append(nearest)
        visited[nearest] = True
        total_distance += min_dist

    total_distance += distances[route[-1]][0]
    route.append(0)
    return route, total_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = nearest_neighbor_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

其他找到旅行商問題近似最優解的演算法

除了使用貪婪演算法解決旅行商問題之外，還有其他演算法可以找到最短路線的近似值。

這些演算法很受歡迎，因為它們比實際檢查所有可能的解決方案更有效，但與上述貪婪演算法一樣，它們找不到全域性最短路線。

用於找到旅行商問題近似最優解的演算法包括：

• 2-opt 啟發式演算法：一種逐步改進解決方案的演算法，在每一步移除兩條邊，然後以不同的方式重新連線兩條路徑，以減少總路徑長度。
• 遺傳演算法：這是一種受自然選擇過程啟發的演算法型別，它使用選擇、變異和交叉等技術來進化問題的解決方案，包括 TSP。
• 模擬退火：這種方法受到了冶金學中退火過程的啟發。它包括加熱然後緩慢冷卻材料以減少缺陷。在 TSP 的上下文中，它透過以允許偶爾移動到更差解決方案的方式探索解決方案空間來尋找近似最優解，這有助於避免陷入區域性最小值。
• 蟻群最佳化：該演算法受到螞蟻在尋找從蟻群到食物源的路徑的行為的啟發。它是一種更復雜的機率技術，用於解決可以對映到在圖中尋找良好路徑的計算問題。

解決旅行商問題的時間複雜度

為了快速獲得近似最優解，我們可以使用一種貪婪演算法，該演算法在每一步都只前往最近的未訪問城市，如本頁的第二個模擬所示。

以這種貪婪方式解決旅行商問題意味著，在每一步，都會將當前城市到所有其他未訪問城市之間的距離進行比較，因此我們得到的時間複雜度為 \(O(n^2) \)。

但找到所有路線中最短的路線需要更多的操作，其時間複雜度為 \(O(n!)\)，如前所述，這意味著對於 4 個城市，有 4! 條可能路線，等於 \(4 \cdot 3 \cdot 2 \cdot 1 = 24\)。而對於例如僅 12 個城市，則有 \(12! = 12 \cdot 11 \cdot 10 \cdot \; ... \; \cdot 2 \cdot 1 = 479,001,600\) 條可能路線！

在下面的圖中，可以看到貪婪演算法 \(O(n^2)\) 的時間複雜度與透過比較所有路線 \(O(n!)\) 來找到最短路線的時間複雜度之間的比較。

但是，我們可以做兩件事來減少需要檢查的路線數量。

在旅行商問題中，路線從同一點開始和結束，形成一個環。這意味著最短路線的長度無論從哪個城市開始都將是相同的。這就是為什麼我們在上面的模擬中選擇了一個固定的起始城市，這使得可能路線的數量從 \(n!\) 減少到 \((n-1)!\)。

此外，由於這些路線是環形的，所以一條路線向一個方向走和向另一個方向走的距離是相同的，所以我們實際上只需要檢查一半路線的距離，因為另一半隻是相同的路線反向走，所以我們需要檢查的路線數量實際上是 \( \frac{(n-1)!}{2}\)。

但是，即使我們可以將需要檢查的路線數量減少到 \( \frac{(n-1)!}{2}\)，時間複雜度仍然是 \( O(n!)\)，因為對於非常大的 \(n\)，將 \(n\) 減一併除以 2，在 \(n\) 增加時，並不會顯著改變時間複雜度的增長方式。

要更好地理解時間複雜度如何工作，請訪問此頁面。

實際的旅行商問題更復雜

在這個旅行商問題的上下文中，圖中的邊權重告訴我們從一個點到另一個點的難易程度，而我們要最小化的是一條路線的總邊權重。

到目前為止，本頁中的邊權重一直是兩個點之間的直線距離。這使得解釋旅行商問題和顯示它變得容易得多。

但在現實世界中，有許多其他因素會影響邊權重

1. 障礙物：在從一個地方移動到另一個地方時，我們通常會試圖避開障礙物，例如樹木、河流、房屋。這意味著從 A 到 B 的路程更長、花費的時間更多，需要增加邊權重值來考慮這一點，因為不再是直線了。
2. 交通網路：旅行時我們通常會沿著道路行駛或使用公共交通系統，這也影響了從一個地方到另一個地方的難易程度（或傳送包裹）。
3. 交通狀況：旅行擁堵也會影響旅行時間，因此也應該反映在邊權重值中。
4. 法律和政治邊界：例如，跨越邊境可能會使一條路線比另一條路線更難選擇，這意味著最短的直線路線可能更慢或成本更高。
5. 經濟因素：使用燃料、員工時間、維護車輛，所有這些都會花費金錢，也應計入邊權重。

如你所見，僅使用直線距離作為邊權重可能比實際問題過於簡單。並且對於這種簡化的模型解決旅行商問題，可能會得到一個在實際意義上並非最優的解決方案。

當邊長度不再僅僅是兩個點之間的直線距離時，視覺化旅行商問題並不容易，但計算機可以很好地處理這個問題。