[閱讀筆記] Algorithms to Live By - 鬆弛 (Relaxation)

 鬆弛 (Relaxation) — 放鬆點，不求完美才有解

1. 柯布漢-艾德蒙斯假說 (Cobham–Edmonds thesis)：如果一個演算法花費的時間是多項次時間 (polynomial time)，也就是 O(n2)、O(n3) 或 n 的任何次方，則這個演算法應被視為「有效率」。因此，如果我們知道如何以有效率的演算法在多項次時間內解決問題，此問題是「可解問題」；若無法在多項次時間內解決問題，此問題是「難解問題」。除了是規模極小的難解問題，不管是運算能力多大的電腦，都無法解決難解問題。

2. 要解決「難解問題」，就必須先「放鬆問題的限制」。電腦科學中相當簡單的放鬆方式，是限制鬆弛法 (Constraint Relaxation)。研究人員運用此技巧時，會先移除問題的某些限制，再著手解決問題，有了一定進展之後，再慢慢加回限制。也就是說，數學家先簡化問題，讓問題容易處理後，再把它改回實際狀況。限制鬆弛法是先讓難解的問題變成可解，取得理想化版本的進展後，再思考現實世界的版本。此法不保證可找到最佳解答，但可以幫助在時間限制與決策品質間做出取捨，只要願意接受近似次佳解，再棘手的問題都有適當技巧可以求解。

3. 遇到難解問題，即使擁有超級電腦也無用武之地。我們要學會放鬆 (Relaxation)，電腦才派得上用場。

放鬆方法	說明
① 限制鬆弛法 (Constraint Relaxation)	直接去除某些限制，求出比較鬆弛問題的解，再把結果套用到真實狀況。
② 連續鬆弛法	把離散或二元選擇轉化成連續體，例如決定點冰紅茶或檸檬水時，先想像混合兩種飲料的冰檸檬紅茶，再決定要進位或捨去；又如飲料從加糖與不加糖，變成一到十分糖。
③ 拉式鬆弛法 (Lagrangian Relaxation)	把不可能變成高昂代價，教我們改變規則 (或是先違反規則、再接受後果)，例如，演唱會稍微超過限制時間並支付罰款，會比嚴格限制表演時間來得好，以換取歌迷滿意度。

4. 鬆弛法的優點與必要性

優點與必要性	說明
① 為真實解答設下品質界線	透過放鬆限制條件的 trade-off 有助於讓人看見問題的全貌與合理設定自己的期待。
② 能與現實互相調和	提出一個與現實調和的參考解，讓人知道最佳解存在的範疇，在那個範疇附近都算OK。
③ 追求完美是一種浪費資源與生命的行為	先假設比較容易的問題，並加以解決，才是取得進展的最佳策略。