1. 從二分到三分算法思想的一次自然延伸在算法學(xué)習(xí)的路上二分查找Binary Search幾乎是所有人的第一道坎也是理解“分治”與“減治”思想的絕佳起點(diǎn)。它的核心邏輯清晰得近乎優(yōu)雅在一個單調(diào)有序的序列中通過不斷與中間值比較將搜索范圍對半砍掉從而以對數(shù)級的時間復(fù)雜度逼近答案。我們用它找數(shù)組中的特定元素解方程甚至在答案具有單調(diào)性時求解最優(yōu)值問題即二分答案法。但不知道你有沒有想過這樣一個問題如果目標(biāo)函數(shù)不是單調(diào)的而是一個先增后減或先減后增的“單峰函數(shù)”我們該如何高效地找到那個頂峰最大值或谷底最小值呢這就是三分法Ternary Search登場的時刻。你可以把它看作是二分法在處理凸函數(shù)極值問題時的一個“表親”。二分法依賴單調(diào)性通過比較中點(diǎn)與目標(biāo)值的關(guān)系決定舍棄左半還是右半。而三分法則適用于尋找單峰函數(shù)Unimodal Function的極值點(diǎn)。所謂單峰就是在定義域[l, r]內(nèi)函數(shù)值先嚴(yán)格單調(diào)上升到峰值然后嚴(yán)格單調(diào)下降或先下降后上升。峰值點(diǎn)或谷值點(diǎn)只有一個。三分法的聰明之處在于它不像二分法那樣只取一個中點(diǎn)而是取兩個點(diǎn)m1 l (r - l) / 3和m2 r - (r - l) / 3。通過比較f(m1)和f(m2)的大小我們就能判斷峰值點(diǎn)更可能位于哪三分之一區(qū)間從而安全地舍棄掉另外三分之一。舉個例子想象你在爬一座形狀規(guī)則的山只有一個山頂你站在山腳l對面山腳是r。你不知道山頂在哪但你能感知海拔函數(shù)值。你向前走三分之一路程到m1再向后走三分之一路程到m2從r往回走。如果你發(fā)現(xiàn)m1的海拔比m2高那說明山頂更可能在你和m2之間嗎不恰恰相反。因?yàn)楹瘮?shù)是單峰的如果f(m1) f(m2)意味著m2點(diǎn)已經(jīng)處在了下降的坡面上那么峰值點(diǎn)山頂必然在m1的左側(cè)即區(qū)間[l, m2]。因?yàn)槿绻逯翟趍2右側(cè)那么從峰值到m2應(yīng)該是下降的但m1在m2左側(cè)且值更高這與單峰性矛盾。因此我們可以安全地將搜索范圍從[l, r]縮小到[l, m2]。同理如果f(m1) f(m2)則峰值在[m1, r]如果相等則峰值就在[m1, m2]之間通常我們可以任意舍棄一邊。理解了這個核心思想你就能明白三分法解決的是二分法無能為力的一類問題在連續(xù)或離散的單峰函數(shù)上尋找極值點(diǎn)。它在競賽編程、數(shù)值計(jì)算和機(jī)器學(xué)習(xí)參數(shù)調(diào)優(yōu)中都有應(yīng)用。接下來我們將深入C實(shí)現(xiàn)的三分法從最基礎(chǔ)的實(shí)數(shù)域求凸函數(shù)極值到離散整數(shù)域上的應(yīng)用再到與二分答案法的對比與結(jié)合最后探討其局限性和常見“坑點(diǎn)”。2. 核心原理與C實(shí)現(xiàn)框架2.1 算法流程與收斂性分析三分法的算法流程非常規(guī)整其正確性完全建立在函數(shù)的單峰性假設(shè)之上。假設(shè)我們要求單峰函數(shù)f(x)在區(qū)間[l, r]上的最大值點(diǎn)求最小值邏輯對稱。以下是標(biāo)準(zhǔn)步驟確定精度或迭代次數(shù)給定一個足夠小的精度要求eps例如1e-7或者一個最大迭代次數(shù)例如對while循環(huán)設(shè)置100次。計(jì)算三等分點(diǎn)在每次迭代中計(jì)算兩個中間點(diǎn)m1 l (r - l) / 3.0m2 r - (r - l) / 3.0注意這里使用(r - l) / 3.0而不是(r - l) * 1.0 / 3是為了避免整數(shù)運(yùn)算帶來的精度問題。關(guān)鍵是要保證m1 m2。比較函數(shù)值并縮小區(qū)間如果f(m1) f(m2)那么最大值點(diǎn)不可能在m1左邊。因?yàn)槿绻畲笾迭c(diǎn)在l和m1之間由于函數(shù)在峰值左側(cè)單調(diào)增應(yīng)該有f(m1) f(m2)與條件矛盾。因此我們可以將左端點(diǎn)更新為l m1。如果f(m1) f(m2)同理最大值點(diǎn)不可能在m2右邊因此將右端點(diǎn)更新為r m2。如果f(m1) f(m2)在浮點(diǎn)數(shù)計(jì)算中很少嚴(yán)格相等通常發(fā)生在峰值平臺區(qū)理論上峰值位于[m1, m2]之間我們可以同時更新l m1和r m2或者任選上述一種策略。實(shí)踐中由于浮點(diǎn)誤差我們通常只使用前兩種判斷。檢查終止條件當(dāng)區(qū)間長度r - l小于預(yù)設(shè)精度eps時終止循環(huán)。此時(l r) / 2.0或l、r均可作為極值點(diǎn)坐標(biāo)的近似值。關(guān)于收斂性每次迭代區(qū)間長度大約縮短為原來的2/3。假設(shè)初始區(qū)間長度為L經(jīng)過k次迭代后區(qū)間長度約為L * (2/3)^k。要達(dá)到精度eps需要的迭代次數(shù)k滿足(2/3)^k * L eps解得k log(eps / L) / log(2/3)。由于log(2/3)是負(fù)數(shù)這個式子是有意義的。例如L1000,eps1e-7大約需要log(1e-10) / log(2/3) ≈ (-23) / (-0.405) ≈ 57次迭代。這比二分法的收斂速度每次區(qū)間減半要慢一些但對于單峰函數(shù)極值問題這是最優(yōu)的基于函數(shù)值比較的確定性算法之一。注意一個常見的誤解是認(rèn)為三分法可以處理多峰函數(shù)。絕對不行。如果函數(shù)有多個局部極值比較f(m1)和f(m2)無法判斷全局極值的位置算法會錯誤地收斂到某個局部極值點(diǎn)或者根本失效。確保單峰性是使用三分法的前提。2.2 浮點(diǎn)數(shù)三分模板代碼與細(xì)節(jié)下面是一個經(jīng)典的C浮點(diǎn)數(shù)三分求函數(shù)最小值的模板。我們以求f(x) x^2 - 6x 10在[0, 10]上的最小值為例。這是一個開口向上的拋物線最小點(diǎn)在x3。#include iostream #include cmath #include iomanip using namespace std; // 目標(biāo)函數(shù)這里是一個簡單的二次函數(shù) double f(double x) { return x * x - 6 * x 10; // 最小值為1在x3處取得 } // 三分法求函數(shù)最小值 double ternary_search_min(double l, double r) { const double eps 1e-9; // 精度要求 while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { // 最小值在左側(cè)區(qū)間 [l, m2] r m2; } else { // 最小值在右側(cè)區(qū)間 [m1, r] l m1; } } // 循環(huán)結(jié)束時l和r非常接近任取其一或取平均作為近似最小值點(diǎn) return (l r) / 2.0; } // 三分法求函數(shù)最大值邏輯對稱 double ternary_search_max(double l, double r) { const double eps 1e-9; while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { // 注意符號與求最小值相反 r m2; } else { l m1; } } return (l r) / 2.0; } int main() { double l 0.0, r 10.0; double min_point ternary_search_min(l, r); cout fixed setprecision(10); cout 最小值點(diǎn) x ≈ min_point endl; cout 最小值 f(x) ≈ f(min_point) endl; // 對于這個開口向上的函數(shù)求最大值在邊界 double max_point ternary_search_max(l, r); cout 最大值點(diǎn) x ≈ max_point endl; // 應(yīng)為0或10 cout 最大值 f(x) ≈ f(max_point) endl; return 0; }關(guān)鍵細(xì)節(jié)與陷阱精度eps的選擇eps并非越小越好。它需要與目標(biāo)函數(shù)的自變量變化尺度以及函數(shù)值計(jì)算精度相匹配。如果eps設(shè)置得比浮點(diǎn)數(shù)精度std::numeric_limitsdouble::epsilon()約2.22e-16還小循環(huán)可能因浮點(diǎn)誤差無法終止或陷入無限循環(huán)。通常1e-9到1e-12對于大多數(shù)問題足夠了。對于答案可能是整數(shù)的問題可以設(shè)置eps1e-7然后對結(jié)果四舍五入到整數(shù)。循環(huán)條件務(wù)必使用while (r - l eps)而不是while (l r)。因?yàn)楦↑c(diǎn)數(shù)比較存在誤差l可能永遠(yuǎn)無法精確等于r。三等分點(diǎn)的計(jì)算強(qiáng)烈建議使用m1 l (r - l) / 3.0和m2 r - (r - l) / 3.0。這比m1 (2*l r) / 3.0和m2 (l 2*r) / 3.0在數(shù)值上更穩(wěn)定尤其是在l和r絕對值很大時能減少舍入誤差。函數(shù)調(diào)用開銷在循環(huán)內(nèi)f(m1)和f(m2)通常會被計(jì)算兩次。如果f(x)計(jì)算非常耗時例如涉及復(fù)雜模擬或數(shù)據(jù)庫查詢這會成為性能瓶頸。一個優(yōu)化技巧是緩存函數(shù)值但在這個簡單模板中清晰性優(yōu)先。2.3 整數(shù)域上的三分法當(dāng)自變量是整數(shù)或者函數(shù)定義在離散的整數(shù)點(diǎn)上時我們同樣可以使用三分法的思想但循環(huán)終止條件需要調(diào)整。因?yàn)閰^(qū)間長度是整數(shù)我們無法也無必要縮放到無限小。整數(shù)三分的典型寫法是通過迭代次數(shù)控制或者當(dāng)區(qū)間長度小于3時直接暴力枚舉。假設(shè)我們在整數(shù)區(qū)間[L, R]上尋找單峰函數(shù)的最大值函數(shù)f(int x)。方法一固定迭代次數(shù)由于每次迭代區(qū)間長度至少減少1/3對于一個長度為N的區(qū)間大約需要O(log_{1.5} N)次迭代。我們可以直接循環(huán)一個足夠多的次數(shù)比如100次這對于N在int范圍內(nèi)綽綽有余。int ternary_search_int(int L, int R) { while (R - L 2) { // 當(dāng)區(qū)間長度大于2時繼續(xù) int m1 L (R - L) / 3; int m2 R - (R - L) / 3; if (f(m1) f(m2)) { L m1; // 峰值在[m1, R] } else { R m2; // 峰值在[L, m2] } } // 區(qū)間長度3暴力比較 int ans f(L), pos L; for (int i L 1; i R; i) { int val f(i); if (val ans) { // 找最大值 ans val; pos i; } } return pos; // 返回最大值點(diǎn) }方法二縮小到小范圍后暴力這是更常見的寫法。循環(huán)條件設(shè)為R - L 3保證區(qū)間內(nèi)至少有兩個中間點(diǎn)m1和m2。退出循環(huán)后區(qū)間內(nèi)最多剩下3個點(diǎn)L, L1, L2直接比較即可。實(shí)操心得整數(shù)三分中m1和m2的計(jì)算使用整數(shù)除法。由于(R - L) / 3會向下取整可能導(dǎo)致m1 m2當(dāng)R-L 3時。這就是為什么循環(huán)條件要設(shè)為R - L 2確保m1和m2是兩個不同的點(diǎn)才能進(jìn)行比較。如果出現(xiàn)m1 m2算法就無法判斷該舍棄哪邊了。3. 典型應(yīng)用場景與問題剖析三分法不是一種每天都會用到的算法但一旦遇到它擅長的問題它就是最直接高效的武器。下面通過幾個典型場景和洛谷上的經(jīng)典題目來具體感受它的應(yīng)用。3.1 場景一單峰函數(shù)求極值這是三分法最直接的應(yīng)用。題目通常會直接或間接地給出一個關(guān)于某個變量的單峰函數(shù)要求你找出極值點(diǎn)。關(guān)鍵在于識別出函數(shù)的單峰性。例題P3382 【模板】三分法洛谷這是三分法的標(biāo)準(zhǔn)模板題。題目直接給出一個N次多項(xiàng)式函數(shù)F(x)并明確告知在區(qū)間[l, r]上是單峰的要求求出峰值點(diǎn)坐標(biāo)。這就是對上述浮點(diǎn)數(shù)三分模板的直接應(yīng)用。你只需要讀入系數(shù)實(shí)現(xiàn)F(x)的計(jì)算然后套用模板即可。這道題的價值在于驗(yàn)證你的三分實(shí)現(xiàn)是否正確特別是浮點(diǎn)數(shù)精度處理。例題尋找函數(shù)最小值自定義假設(shè)一個問題你要在一條筆直的海岸線上建一個碼頭海岸線上有N個倉庫位置已知。碼頭建在海岸線上某一點(diǎn)運(yùn)輸成本與倉庫到碼頭距離的平方成正比。求使總運(yùn)輸成本最小的碼頭位置。 設(shè)碼頭位置為x第i個倉庫位置為a[i]則總成本f(x) Σ (x - a[i])^2。這是一個關(guān)于x的二次函數(shù)Σ x^2 - 2Σ a[i] * x Σ a[i]^2其二次項(xiàng)系數(shù)N 0所以是開口向上的拋物線有唯一最小值點(diǎn)。這個最小值點(diǎn)實(shí)際上就是倉庫位置的算術(shù)平均數(shù)x (Σ a[i]) / N。我們可以用三分法來求解雖然用公式直接算更簡單但這驗(yàn)證了對于凸二次函數(shù)三分法能正確找到極值點(diǎn)。3.2 場景二距離函數(shù)的最大值最小化或最小值最大化這是一類非常經(jīng)典的問題也稱為“最小最大問題”或“最大最小問題”。通常描述為在某種方案下定義一種“代價”或“距離”我們要在最壞情況下最大距離盡可能好最小化這個最大距離或者在最好情況下最小收益盡可能有保障最大化這個最小收益。當(dāng)這個“最壞代價”關(guān)于決策變量是單峰函數(shù)時就可以用三分法。經(jīng)典模型一條直線上有N個點(diǎn)選一個點(diǎn)使得該點(diǎn)到所有點(diǎn)的最大距離最小。這就是最小覆蓋半徑問題。設(shè)選的點(diǎn)為x定義函數(shù)f(x) max(|x - a[i]|)即x到所有點(diǎn)的最遠(yuǎn)距離。我們需要最小化f(x)。 可以證明或直覺感受f(x)是一個先減后增的單峰函數(shù)更準(zhǔn)確地說是一個凸函數(shù)V形。當(dāng)x在最左點(diǎn)左邊時最遠(yuǎn)距離是到最右點(diǎn)且隨x右移而減小當(dāng)x超過某個位置后最遠(yuǎn)距離變成到最左點(diǎn)且隨x右移而增大。最小值點(diǎn)就在最左點(diǎn)和最右點(diǎn)的中點(diǎn)附近。因此我們可以對x進(jìn)行三分求f(x)的最小值。例題P2571 [SCOI2010] 傳送帶洛谷這道題是三分法應(yīng)用的經(jīng)典。題目描述在平面上有兩條線段AB和CD你可以在AB上以速度P移動在CD上以速度Q移動在平面上其他區(qū)域以速度R移動。求從A點(diǎn)出發(fā)經(jīng)過AB上一點(diǎn)X再經(jīng)過CD上一點(diǎn)Y最后到達(dá)D點(diǎn)的最短時間。 設(shè)X是AB上的點(diǎn)Y是CD上的點(diǎn)?？倳r間T是關(guān)于X和Y兩個變量的函數(shù)。一個關(guān)鍵的洞察是當(dāng)X固定時T是關(guān)于Y的單峰函數(shù)凸函數(shù)反之當(dāng)Y固定時T是關(guān)于X的單峰函數(shù)。這允許我們使用三分套三分的方法先在外層三分X的位置對于每一個固定的X在內(nèi)層用三分法求出最優(yōu)的Y從而得到該X下的最短時間。最終外層三分找到最優(yōu)的X。這是三分法處理多變量問題的一種方式要求函數(shù)關(guān)于每個變量單獨(dú)滿足單峰性。3.3 場景三與二分答案法結(jié)合二分答案法要求答案具有單調(diào)性即對于一個猜測的答案mid我們能判斷“是否存在一種方案使得指標(biāo)值至少或至多為mid”并且這個判斷函數(shù)check(mid)的返回值關(guān)于mid是單調(diào)的通常是從True變False或反之。有時候我們遇到的問題的“可行性”關(guān)于某個參數(shù)不是單調(diào)的而是單峰的。這時三分法就可以替代二分法。舉例分配資源使得最小收益最大化。假設(shè)有M個任務(wù)和N個資源單位每個任務(wù)消耗一定資源并產(chǎn)生收益。我們要將資源分配給任務(wù)目標(biāo)是最大化所有任務(wù)中收益最小的那個即讓最差的任務(wù)也盡量好。設(shè)我們設(shè)定的最小收益目標(biāo)是T那么問題轉(zhuǎn)化為是否存在一種分配方案使得每個任務(wù)的收益都至少為T這個check(T)函數(shù)判斷可行性關(guān)于T通常是單調(diào)的如果T很小很容易實(shí)現(xiàn)T很大就無法實(shí)現(xiàn)。所以這是二分答案?，F(xiàn)在考慮一個變種目標(biāo)不是最大化最小收益而是最大化總收益關(guān)于某個分配參數(shù)x的函數(shù)并且這個總收益函數(shù)g(x)是單峰的。例如x代表投資激進(jìn)程度太保守則收益低太冒險則可能虧損中間有個最優(yōu)值。這時最優(yōu)的x就可以通過三分法求得。check(x)在這里不是返回布爾值而是直接計(jì)算g(x)的值。區(qū)分何時用二分何時用三分二分答案用于求解滿足某種條件的最大/最小值。關(guān)鍵在于存在一個單調(diào)的判定函數(shù)check(ans)。例如“最大的最小距離”、“最小的最大重量”這類問題check(mid)通常是“能否做到距離mid”或“能否承受重量mid”答案具有單調(diào)性。三分法用于直接求解一個單峰函數(shù)的極值點(diǎn)。沒有“是否可行”的判定而是直接計(jì)算函數(shù)值進(jìn)行比較。目標(biāo)就是找到使得f(x)最大或最小的x。有些問題既可以用三分也可以用二分答案判定但思路不同。例如前述的“最小覆蓋半徑”可以用三分法直接求f(x)的最小值也可以用二分答案法猜半徑R判定是否存在一個點(diǎn)距離所有點(diǎn)都不超過R這是一個覆蓋問題判定函數(shù)是單調(diào)的。4. 實(shí)現(xiàn)技巧、調(diào)試與常見問題4.1 避免浮點(diǎn)數(shù)誤差的實(shí)用技巧浮點(diǎn)數(shù)三分中誤差主要來自兩個方面一是循環(huán)終止條件二是函數(shù)值比較。以下技巧可以幫助你寫出更魯棒的代碼設(shè)置合理的迭代次數(shù)上限除了用while (r - l eps)可以再加一個計(jì)數(shù)器防止因特殊函數(shù)或精度問題導(dǎo)致無限循環(huán)。int iter 0; while (r - l eps iter 100) { // ... 三分邏輯 iter; }謹(jǐn)慎比較浮點(diǎn)數(shù)避免直接使用比較f(m1)和f(m2)。由于浮點(diǎn)誤差兩個理論上相等的數(shù)可能略有不同。通常使用和就夠了。如果一定要處理相等情況可以用fabs(f(m1)-f(m2)) 1e-12來判斷。最終答案的處理循環(huán)結(jié)束后l和r非常接近。通常取(lr)/2作為最終答案。如果題目要求輸出函數(shù)值最好用這個中點(diǎn)坐標(biāo)重新計(jì)算一次f(x)而不是用最后一次迭代的f(m1)或f(m2)因?yàn)橹悬c(diǎn)坐標(biāo)更穩(wěn)定。精度與數(shù)據(jù)范圍的平衡如果自變量范圍很大如[0, 1e9]而精度要求很高如1e-12可能需要將eps設(shè)置得比1e-12稍大比如1e-10或者增加迭代次數(shù)。因?yàn)楫?dāng)區(qū)間長度很大時浮點(diǎn)數(shù)的相對誤差可能會影響m1和m2的計(jì)算。4.2 驗(yàn)證單峰性三分法正確性的前提三分法最危險的陷阱就是誤用在非單峰函數(shù)上。如何驗(yàn)證單峰性數(shù)學(xué)推導(dǎo)對于連續(xù)函數(shù)可以求二階導(dǎo)數(shù)。如果在定義域內(nèi)二階導(dǎo)數(shù)恒大于等于0是下凸函數(shù)有最小值恒小于等于0是上凸函數(shù)有最大值。對于離散函數(shù)可以分析差分相鄰項(xiàng)的差的變化趨勢。觀察與直覺很多問題具有對稱性或物理意義極值點(diǎn)唯一。例如距離的平方和、時間關(guān)于路徑點(diǎn)的函數(shù)如傳送帶問題通常是凸的。畫圖輔助對于簡單函數(shù)或小規(guī)模數(shù)據(jù)可以編程輸出一系列點(diǎn)的函數(shù)值觀察其變化趨勢。這是調(diào)試時最有效的方法。警惕平臺區(qū)域如果函數(shù)有一段是平坦的導(dǎo)數(shù)等于0嚴(yán)格來說不是“單峰”先嚴(yán)格增后嚴(yán)格減。但三分法通常仍然有效因?yàn)閒(m1)f(m2)時我們無論舍棄哪邊極值點(diǎn)都還在剩下的區(qū)間里。不過收斂到平臺上的具體哪一點(diǎn)就不確定了。4.3 三分法常見問題排查表問題現(xiàn)象可能原因解決方案程序陷入死循環(huán)1. 浮點(diǎn)數(shù)精度eps設(shè)置過小r-l始終大于eps。2. 整數(shù)三分循環(huán)條件寫錯導(dǎo)致m1m2且無法縮小區(qū)間。3. 函數(shù)f(x)在區(qū)間內(nèi)非單峰算法在局部震蕩。1. 增加迭代次數(shù)上限或適當(dāng)調(diào)大eps。2. 檢查整數(shù)三分循環(huán)條件確保R-L3。3. 重新審視問題驗(yàn)證函數(shù)單峰性。輸出中間值觀察區(qū)間變化。結(jié)果精度不夠1.eps設(shè)置過大。2. 迭代次數(shù)不足。3. 函數(shù)值計(jì)算本身有較大誤差如涉及大量浮點(diǎn)運(yùn)算。1. 根據(jù)題目要求精度適當(dāng)減小eps如1e-9。2. 改用固定迭代次數(shù)如100次確保區(qū)間足夠小。3. 使用long double提高計(jì)算精度或優(yōu)化f(x)的計(jì)算順序減少誤差。答案明顯錯誤1. 求最大/最小值時if條件判斷符號寫反。2. 區(qū)間初始值[l, r]設(shè)置錯誤沒有包含真正的極值點(diǎn)。3. 函數(shù)f(x)實(shí)現(xiàn)有bug。1. 牢記口訣求最小值時f(m1) f(m2)則舍去右邊(rm2)?？梢援嬕粋€“V”形圖輔助記憶。2. 確保初始區(qū)間足夠?qū)捘芨采w所有可能的最優(yōu)解。有時需要根據(jù)問題背景估算范圍。3. 單獨(dú)測試f(x)函數(shù)用幾個已知點(diǎn)驗(yàn)證。整數(shù)三分找不到正確整數(shù)解循環(huán)結(jié)束后在[L, R]區(qū)間暴力查找時漏掉了邊界點(diǎn)或比較邏輯有誤。確保暴力查找的循環(huán)是for (int i L; i R; i)并且正確初始化ans和pos。4.4 三分法與其他搜索算法的對比與二分查找對比二分適用于單調(diào)序列中查找特定值或單調(diào)判定函數(shù)下的最優(yōu)解二分答案。三分適用于單峰凸函數(shù)上查找極值點(diǎn)。核心區(qū)別二分每次比較的是中點(diǎn)值與目標(biāo)值的關(guān)系三分比較的是兩個三等分點(diǎn)的函數(shù)值關(guān)系。與黃金分割搜索對比黃金分割搜索Golden-section search也是一種尋找單峰函數(shù)極值的方法。它通過黃金比例約0.618分割區(qū)間每次迭代只需要計(jì)算一個新的函數(shù)值因?yàn)榱硪粋€點(diǎn)可以復(fù)用上一輪的值理論上比三分法每次計(jì)算兩個新點(diǎn)效率稍高。但三分法邏輯更簡單直觀代碼易于理解和記憶在大多數(shù)編程競賽和日常應(yīng)用中其性能差異可以忽略不計(jì)。三分法是更通用的選擇。與梯度下降等數(shù)值方法對比對于高維、非凸、復(fù)雜的函數(shù)三分法不適用。此時需要梯度下降、牛頓法等數(shù)值優(yōu)化方法。三分法的優(yōu)勢在于對于一維單峰函數(shù)它是確定性且收斂性有保證的算法不需要計(jì)算導(dǎo)數(shù)對函數(shù)要求低只需能求值。5. 綜合實(shí)戰(zhàn)從問題識別到代碼實(shí)現(xiàn)讓我們通過一個綜合性的例子走完從問題分析、識別算法到代碼實(shí)現(xiàn)和調(diào)試的全過程。問題描述自定義 你正在設(shè)計(jì)一個無線網(wǎng)絡(luò)基站。在一條筆直的道路上看作x軸有N個用戶第i個用戶的位置是a[i]。你可以在道路上任意位置x放置一個基站。基站的信號強(qiáng)度隨距離衰減對于距離基站d的用戶接收到的信號質(zhì)量為Q P / (1 d^2)其中P是基站的發(fā)射功率常數(shù)。為了保證所有用戶都能正常通信我們需要讓信號質(zhì)量最差的那個用戶的信號質(zhì)量盡可能高。即選擇x最大化min_{i1 to N} (P / (1 (x - a[i])^2))。 由于P是常數(shù)這等價于最小化max_{i1 to N} (1 (x - a[i])^2)也就是最小化x到所有用戶的最大距離的平方再加1。進(jìn)一步也就是最小化x到所有用戶的最大距離。設(shè)f(x) max |x - a[i]|。第一步識別算法問題轉(zhuǎn)化為求一個點(diǎn)x使得它到N個已知點(diǎn)的最大距離最小。這正是前面提到的“最小覆蓋半徑”問題。我們需要證明或確信f(x)是單峰的。當(dāng)x遠(yuǎn)小于所有a[i]時f(x) max(a[i]) - x隨x增大而減小。當(dāng)x遠(yuǎn)大于所有a[i]時f(x) x - min(a[i])隨x增大而增大。當(dāng)x在中間時f(x)是分段線性函數(shù)其圖像是一個“V”形由多個絕對值函數(shù)取最大值構(gòu)成這是一個凸函數(shù)單峰函數(shù)。因此可以使用三分法求其最小值點(diǎn)。第二步確定搜索區(qū)間顯然最優(yōu)的x一定位于所有用戶位置的最小值min_a和最大值max_a之間。我們可以將初始區(qū)間設(shè)為[min_a, max_a]。為了保險甚至可以設(shè)得更寬一些比如[min_a - 1, max_a 1]。第三步實(shí)現(xiàn)函數(shù)f(x)double max_distance(double x, const vectordouble positions) { double max_dist 0.0; for (double pos : positions) { max_dist max(max_dist, fabs(x - pos)); } return max_dist; // f(x) }第四步套用三分法模板求最小值double ternary_search_min_f(const vectordouble pos) { double l *min_element(pos.begin(), pos.end()) - 1.0; // 左邊界 double r *max_element(pos.begin(), pos.end()) 1.0; // 右邊界 const double eps 1e-7; while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (max_distance(m1, pos) max_distance(m2, pos)) { r m2; // 最小值在[l, m2] } else { l m1; // 最小值在[m1, r] } } return (l r) / 2.0; }第五步分析結(jié)果與驗(yàn)證得到最優(yōu)的x_opt后可以計(jì)算f(x_opt)這就是最小的最大覆蓋半徑。有趣的是對于這個問題最優(yōu)解x_opt其實(shí)就是(min_a max_a) / 2即最左和最右用戶的中點(diǎn)。因?yàn)橐棺畲缶嚯x最小基站放在兩端點(diǎn)的中點(diǎn)上這樣到兩端的距離相等且任何其他點(diǎn)都會導(dǎo)致到某一端的距離更大。我們的三分法應(yīng)該能驗(yàn)證這個結(jié)果。第六步擴(kuò)展思考如果用戶不是分布在直線上而是在平面上問題就變成了“最小圓覆蓋”無法用簡單的一維三分法解決需要更復(fù)雜的幾何算法如Welzl算法。這提醒我們?nèi)址ǖ膽?yīng)用前提是問題可以轉(zhuǎn)化為關(guān)于單個變量的一維單峰函數(shù)優(yōu)化。通過這個完整的例子你應(yīng)該對三分法如何解決一個實(shí)際問題有了清晰的認(rèn)識。核心步驟永遠(yuǎn)是1) 定義目標(biāo)函數(shù)2) 證明或論證其單峰性3) 確定搜索范圍4) 實(shí)現(xiàn)函數(shù)求值5) 套用三分模板6) 分析結(jié)果。掌握了這個流程你就能在面對“求最優(yōu)...”、“最大化...”、“最小化...”這類問題時多一種強(qiáng)有力的思路和工具。