近似演算法與鬆弛 (Approximation & Relaxation)#

前面談貪心時，我們已經看過「局部最優不一定等於全域最優」的陷阱。但還有一類更棘手的問題：就算你願意花時間，也不存在已知的高效精確解。 這一節談的就是，當完美解算不出來時，工程上怎麼辦。

動機：有些問題就是沒有高效精確解#

旅行推銷員問題（TSP，走遍所有城市各一次、總路程最短）、排桌問題（N 位賓客排座位、滿足一堆相鄰偏好）、最小頂點覆蓋……這些都屬於 NP-hard。它們的共同特徵是：暴力解的複雜度是階乘級或指數級——城市數從 10 漲到 20，可能路線數就從幾百萬暴增到天文數字，規模一大，再快的電腦也算不完。

「為什麼有些問題注定算不快」並不是工程偷懶，而是問題本身的難度邊界所決定的。這背後的理論可參考 可計算性與問題的邊界。

當精確最優解不可得，目標就要務實地轉個彎：

不再追求「唯一最優解」，而是要在可接受的時間內，找一個夠好、而且能保證誤差範圍的解。

關鍵字是「保證」。近似演算法的價值不只在於「快又還不錯」，更在於它能告訴你這個解離最優最多差多遠——這才是它和「隨便猜一個」的本質區別。

三種鬆弛（Relaxation）技術#

「鬆弛」的共同思路是：原問題太硬解不動，那就先把它放寬成一個解得動的問題，再從寬鬆版的解回推原問題的資訊。 以下三種是骨架。

約束鬆弛（Constraint Relaxation）#

移除部分限制，解一個更簡單的版本，藉此得到原問題的「下界」或「上界」。

以 TSP 為例：原本要求「每個城市恰好經過一次、最後回到起點」。把這條限制放寬成「允許重複經過城市」，問題就退化成連通所有城市的 最小生成樹（MST）——而 MST 有高效解法。

由於真正的最短巡迴路線不可能比 MST 還短，MST 的總長就是真實最優解的一個下界。

假設 MST = 100、而你用某個方法找到的實際路線 = 110，你立刻就知道：最優解一定落在 100 到 110 之間，所以你的解誤差 ≤ 10%。這就示範了近似解如何「界定自己離最優有多遠」。

這類技巧大量用到圖的結構性質，可延伸閱讀 圖論。

連續鬆弛（Continuous Relaxation）#

很多難題的「難」，來自變數只能取 0 或 1 的離散選擇（選或不選、放或不放）。連續鬆弛把這個限制放寬成「可取 0 到 1 之間的任意分數」，問題就從整數規劃變成可以高效求解的線性規劃（LP）。

解出來的分數解當然不能直接用（你不能「選 0.7 個物品」），於是再做一步取整：四捨五入，或把分數當成機率來隨機取整。

這套「先放寬成連續、解完再取整」的流程，常常能在理論上證明：取整後的解不超過最優解的某個固定倍數（例如「不超過兩倍」）。這個倍數就是它的近似保證。

拉格朗日鬆弛（Lagrangian Relaxation）#

有時候卡住問題的，是某幾條「硬性約束」——必須滿足、否則解不合法。拉格朗日鬆弛的做法是：把硬約束降級成「違反就扣分」的懲罰項，併進目標函數裡。

這樣一來，原本因為約束糾纏在一起、動彈不得的問題，就鬆開成一個好解的版本；求解過程會自動傾向少違反約束（因為違反要扣分）。複雜的賽程安排（聯賽排程同時要滿足場地、轉播、休息日等一堆約束）常用這招。

跳出局部最優：隨機化與模擬退火#

鬆弛是「換一個問題解」，另一條路則是「在原問題上更聰明地搜尋」。

純貪心或爬山法（Hill Climbing）只往「眼前更好」的方向走，因此極容易卡在局部最優——走到一個小山頭，四周都比它低，但它根本不是最高峰。

要脫困，核心武器是隨機性，常見三招：

• 隨機微擾：在當前解上做小幅隨機改動，試圖跳到鄰近更好的解。
• 隨機重啟：從一個全新的隨機起點重來，避免被同一個山頭困死。
• 以遞減機率接受劣解：刻意允許「暫時走下坡」，藉此越過山谷、爬向更高的山頭。

模擬退火（Simulated Annealing）#

模擬退火把上面第三招系統化，靈感來自金屬退火：金屬在高溫時原子活躍、能跳出不穩定的排列，緩慢降溫後才凝固成低能量的穩定結構。

對應到搜尋：

• 前期「高溫」：較願意接受比當前更差的解，藉此大膽跳出局部最優、廣泛探索解空間。
• 隨時間「降溫」：接受劣解的機率逐漸下降，搜尋越來越「貪心」，最後只接受能改善的解，收斂到一個好的結果。

模擬退火彌補了 貪心演算法原理 的根本侷限：貪心一步定生死、無法回頭，因此可能困在局部最優；模擬退火則用「機率性地容忍變差」換取跳出局部最優的能力。

當問題結構允許系統化地搜尋並剪掉無望分支時，也可以回頭參考 回溯演算法 的剪枝思路——兩者都是在龐大解空間裡，用不同策略避免窮舉。

近似不是碰運氣#

近似演算法的精髓不是「賭一把、湊合能用」，而是一套有方法論的工程：鬆弛把難題換成解得動的版本，界定讓你知道解離最優最多差多遠（有界、可量化），最後再把鬆弛解轉回原問題的可行解。能說出「誤差不超過 X%」，正是它和瞎猜的分水嶺。

小結#