8.2 貪婪啟發式解TSP與著色#

概念說明#

貪婪啟發式（Greedy Heuristic）的原則是「每一步都選當下看起來最好的選項，絕不回頭」。它沒有近似保證（或保證很差），但實作簡單、速度快，是工程上最常見的第一線方案。

TSP 的貪婪策略：

最近鄰居法（Nearest Neighbor）：從某城市出發，每次走到尚未拜訪、距離最近的城市。複雜度 O(n²)，路徑通常比最佳解差 20~25%，且可能留下「橫跨全圖的長返程邊」。
貪婪邊法（Greedy Edge）：把所有邊按距離排序，依序加入不會使任何點度數超過 2、不會提前成圈的邊，直到形成迴路。品質通常優於最近鄰居。
2-opt 改良：把路徑中兩條邊斷開、反向重接，若總長變短就接受，反覆進行直到無法改良。2-opt 常能把貪婪解再縮短 5~15%，是局部搜尋（8.3 節）的最簡實例。

圖著色的貪婪策略（Welsh–Powell / DSATUR）：

Welsh–Powell：頂點按度數遞減排序，依序給每個頂點「最小可用顏色」。
DSATUR：每次選「飽和度最高」（相鄰顏色數最多）的未著色頂點，給最小可用顏色。DSATUR 在許多實例上明顯優於 Welsh–Powell，且對二分圖與輪圖等結構恰好朋友——它能精確解出某些貪婪會失敗的圖。

貪婪著色的理論上界：任何圖的貪婪著色至多用 Δ + 1 種顏色（Δ 為最大度數），而事實上任何圖都可用 Δ + 1 色著色（Brooks 定理說多數圖 Δ 色就夠）。問題在於貪婪的「排序」可能遭遇最壞情況，浪費顏色。

演算法步驟（DSATUR）#

初始所有頂點未著色，飽和度均為 0。
選擇飽和度最大者；平手時選剩餘度數最大者。
給它「相鄰未使用的最小顏色編號」。
更新其鄰居的飽和度與度數。
重複 2~4 直到全部著色；回傳使用的顏色數。

Python 程式碼範例#

import math, random

def nearest_neighbor_tsp(pts, start=0):
    n = len(pts)
    d = lambda a, b: math.dist(pts[a], pts[b])
    unvisited, tour = set(range(n)) - {start}, [start]
    while unvisited:
        cur = tour[-1]
        nxt = min(unvisited, key=lambda v: d(cur, v))
        tour.append(nxt); unvisited.remove(nxt)
    length = sum(math.dist(pts[tour[i]],
                           pts[tour[(i+1) % n]])
                 for i in range(n))
    return tour, length

def two_opt(tour, pts):
    """2-opt 局部改良"""
    n, improved = len(tour), True
    def seg(a, b):
        return math.dist(pts[a], pts[b])
    while improved:
        improved = False
        for i in range(n - 1):
            for j in range(i + 2, n):
                a, b = tour[i], tour[i+1]
                c, d2 = tour[j], tour[(j+1) % n]
                if seg(a, b) + seg(c, d2) > \
                   seg(a, c) + seg(b, d2):
                    tour[i+1:j+1] = reversed(tour[i+1:j+1])
                    improved = True
    return tour

def dsatur_coloring(n, edges):
    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v); adj[v].add(u)
    color = [-1] * n
    for _ in range(n):
        # 飽和度最大者優先
        v = max((u for u in range(n) if color[u] < 0),
                key=lambda u: (len({color[w]
                    for w in adj[u] if color[w] >= 0}),
                    len(adj[u])))
        used = {color[w] for w in adj[v] if color[w] >= 0}
        c = 0
        while c in used:
            c += 1
        color[v] = c
    return color

pts = [(random.uniform(0, 100), random.uniform(0, 100))
       for _ in range(12)]
tour, L = nearest_neighbor_tsp(pts)
tour2 = two_opt(tour, pts)
L2 = sum(math.dist(pts[tour2[i]], pts[tour2[(i+1)%12]])
         for i in range(12))
print(f"貪婪: {L:.1f}  2-opt後: {L2:.1f}")
print(dsatur_coloring(5, [(0,1),(1,2),(2,3),(3,4),(4,0)]))

複雜度分析#

最近鄰居：O(n²)；貪婪邊：O(m log m)；2-opt：每輪 O(n²)，輪數無多項式保證（實務數輪即收斂）。
Welsh–Powell：O(n²)（排序 + 著色）；DSATUR：樸素實作 O(n²)，用堆積可到 O((n + m) log n)。
品質：TSP 貪婪解平均比最佳解差 20% 上下，2-opt 後約 5%；DSATUR 用色數通常非常接近圖的著色數 χ(G)。
無保證：貪婪 TSP 的近似比在最壞情況可達 Θ(log n)，2-opt 的解也可能比最佳解差任意多倍。

練習#

生成 20 個 15 城市隨機實例，比較「最近鄰居」「貪婪邊」「2-opt 改良後」三者的平均路徑長（以暴力最佳解為基準 100%）。
構造一張圖，使 Welsh–Powell 使用的顏色數多於 DSATUR，並解釋失敗原因。
實作 3-opt 的其中一種重接方式，比較其對 2-opt 結果的再改良幅度。