1. 項目概述從“三分”到“凸函數(shù)”的精確求解在算法競賽和許多工程優(yōu)化問題中我們常常會遇到一類特殊的函數(shù)它們只有一個“谷底”或“峰頂”。想象一下你在山里找最低點或者在海面上找最高點你不需要走遍每一寸土地只需要用一種高效的策略逐步縮小搜索范圍。這就是“三分法”要解決的核心問題。它不是一個簡單的數(shù)值方法而是一個基于函數(shù)凸凹性質的確定性搜索算法專門用于在連續(xù)區(qū)間上尋找單峰函數(shù)的極值點。我最初接觸它是在解決一些最優(yōu)路徑、資源分配和參數(shù)調優(yōu)的問題時發(fā)現(xiàn)暴力枚舉效率低下而導數(shù)法又因為函數(shù)形式復雜或不可導而無法應用。三分法以其簡潔的思想和穩(wěn)定的性能成為了我工具箱里的常客。所謂“三分”顧名思義就是將當前的搜索區(qū)間等分成三份通過比較兩個中間分界點的函數(shù)值來果斷地舍棄掉不可能包含最值的那三分之一區(qū)間。這個過程反復迭代區(qū)間迅速縮小直到滿足我們的精度要求。它解決的是這樣一個明確的需求給定一個在區(qū)間[l, r]上先嚴格單調增、后嚴格單調減或先減后增的函數(shù)f(x)找到那個讓f(x)取得最大值或最小值的x。這個“單峰”的性質就是“凸函數(shù)”在此語境下的實際含義更嚴格地說用于找最小值的是凸函數(shù)找最大值的是凹函數(shù)。本文將為你徹底拆解這個算法的原理、實現(xiàn)細節(jié)、各種變體以及實戰(zhàn)中那些教科書上不會講的坑。無論你是正在備賽的選手還是遇到類似優(yōu)化問題的工程師這份“凸函數(shù)模板”的深度解析都能讓你不僅會套用更能理解其筋骨靈活應用于各種場景。2. 算法核心原理與思路拆解2.1 為什么是“三分”—— 與二分法的本質區(qū)別很多人熟悉二分法它用于在單調序列中查找目標值。三分法可以看作是二分法在尋找函數(shù)極值問題上的一個類比和擴展。但它們有一個根本性的不同二分法依賴于區(qū)間的單調性而三分法依賴于區(qū)間的單峰性。二分法每次比較中點值與目標值的關系總能舍棄一半區(qū)間因為它明確知道目標在中點的左邊還是右邊。但對于一個單峰函數(shù)你只知道極值點在某處比較一個點的函數(shù)值無法告訴你極值點在其左還是右。例如對于一個“先增后減”的函數(shù)如果你在上升段取一個點函數(shù)值很大但極值點最大值既可能在它右邊繼續(xù)上升也可能在它左邊已經過了頂點開始下降。單個點提供的信息不足以做出決策。于是三分法的智慧就體現(xiàn)出來了通過兩個點來探測函數(shù)的“走勢”。將區(qū)間[l, r]分為三段取兩個中間點m1 l (r - l) / 3和m2 r - (r - l) / 3。比較f(m1)和f(m2)如果f(m1) f(m2)對于找最大值的單峰函數(shù)先增后減說明峰值點不可能在m1的左邊。因為如果峰值在左邊那么從峰值到m1是下降的而m1到m2是上升的這與“先增后減”的定義矛盾。因此我們可以安全地將左端點l更新為m1舍棄[l, m1)這段區(qū)間。如果f(m1) f(m2)同理峰值點不可能在m2的右邊可以將右端點r更新為m2舍棄(m2, r]。如果f(m1) f(m2)那么峰值點一定在[m1, m2]之間我們可以同時收縮左右端點令l m1,r m2。這樣每一次迭代我們都能夠確保極值點始終留在新的、更小的區(qū)間內并且區(qū)間長度以大約2/3的比例縮小。這是一種非常樸素而強大的“夾逼”思想。2.2 “凸函數(shù)”在算法中的具體含義在數(shù)學優(yōu)化中凸函數(shù)的定義涉及二階導數(shù)非負或Jensen不等式。但在三分法的實用語境下我們所說的“凸函數(shù)”通常指的是單峰函數(shù)。更準確地當我們尋找最小值時我們要求函數(shù)是凸函數(shù)形狀像碗U型。當我們尋找最大值時我們要求函數(shù)是凹函數(shù)形狀像拱∩型。對于算法本身它只關心函數(shù)的單峰性質在定義域內存在唯一極值點且在該點左側函數(shù)單調右側函數(shù)單調方向相反。你的模板必須明確你是在找最大值還是最小值因為這決定了f(m1)和f(m2)比較后該舍棄哪一段區(qū)間。一個健壯的模板應該能通過一個參數(shù)或簡單的邏輯切換來適應這兩種情況。注意實際編程中很多“凸函數(shù)”并非嚴格的數(shù)學凸函數(shù)可能由多個分段函數(shù)組成但只要在搜索區(qū)間上滿足單峰性三分法就適用。這是其應用廣泛的重要原因。2.3 算法流程與復雜度分析標準三分法的流程可以清晰地分為以下幾步初始化確定搜索區(qū)間[l, r]和精度要求eps例如1e-7。迭代收縮當區(qū)間長度(r - l)大于eps時循環(huán)執(zhí)行 a. 計算兩個三等分點m1 l (r - l) / 3,m2 r - (r - l) / 3。 b. 計算函數(shù)值f(m1)和f(m2)。 c.根據(jù)尋找最值的類型進行比較 - 找最小值若f(m1) f(m2)則r m2否則l m1。 - 找最大值若f(m1) f(m2)則l m1否則r m2。返回結果迭代結束后區(qū)間[l, r]內的任意點通常取(lr)/2都可作為極值點的近似。時間復雜度每次迭代區(qū)間長度乘以2/3。假設初始區(qū)間長度為L要求最終長度小于eps則迭代次數(shù)k滿足L * (2/3)^k eps解得k ≈ log_{3/2}(L/eps)。這是一個對數(shù)復雜度效率非常高。例如對于L1000,eps1e-7迭代次數(shù)大約在 60-70 次左右?？臻g復雜度為O(1)只需要常數(shù)級別的變量存儲。3. 核心實現(xiàn)細節(jié)與模板解析3.1 浮點數(shù)三分模板針對連續(xù)函數(shù)這是最經典的形式用于自變量為連續(xù)實數(shù)的函數(shù)。模板的核心在于循環(huán)條件和比較邏輯。// 尋找凸函數(shù)的最小值 double ternary_search_min(double l, double r) { const double eps 1e-10; // 精度根據(jù)題目要求調整 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; // 最小值在 [l, m2] 區(qū)間 } else { l m1; // 最小值在 [m1, r] 區(qū)間 } } return (l r) / 2.0; // 返回近似極值點 } // 尋找凹函數(shù)的最大值 double ternary_search_max(double l, double r) { const double eps 1e-10; while (r - l eps) { double m1 l (r - l) / 3.0; double m2 r - (r - l) / 3.0; if (f(m1) f(m2)) { l m1; // 最大值在 [m1, r] 區(qū)間 } else { r m2; // 最大值在 [l, m2] 區(qū)間 } } return (l r) / 2.0; }關鍵細節(jié)與解釋精度eps的選擇這是浮點數(shù)三分的靈魂。eps太小可能因浮點數(shù)精度問題陷入無限循環(huán)或產生誤差eps太大結果不精確。通常如果答案要求輸出小數(shù)點后k位eps可以設為1e-(k2)。例如要求輸出6位小數(shù)eps1e-8是個穩(wěn)妥的選擇。有時也采用固定迭代次數(shù)如循環(huán)100次來替代精度判斷這樣更穩(wěn)定。中間點計算務必使用l (r - l) / 3.0而非l (r - l) / 3后者在C/C中會導致整數(shù)除法。更安全的寫法是m1 l (r - l) / 3和m2 r - (r - l) / 3因為(r-l)是浮點數(shù)除以整數(shù)3會得到浮點結果。函數(shù)f的實現(xiàn)f(x)需要根據(jù)具體問題實現(xiàn)。它可能是一個簡單的數(shù)學表達式也可能是一個需要復雜模擬的過程如計算某種配置下的代價。確保f(x)在[l, r]上是單峰的這是算法正確的前提。3.2 整數(shù)三分模板針對離散函數(shù)當自變量是整數(shù)或者函數(shù)定義在整數(shù)域上時我們需要整數(shù)三分。因為區(qū)間長度是整數(shù)當區(qū)間縮小到很短時m1和m2可能重合需要不同的處理邏輯。// 在整數(shù)區(qū)間 [l, r] 上尋找凸函數(shù)的最小值 int ternary_search_int_min(int l, int r) { while (r - l 2) { // 當區(qū)間長度大于2時循環(huán) int m1 l (r - l) / 3; int m2 r - (r - l) / 3; if (f(m1) f(m2)) { r m2; } else { l m1; } } // 區(qū)間長度小于等于3暴力枚舉剩余點 int min_val f(l); int ans l; for (int i l 1; i r; i) { int val f(i); if (val min_val) { min_val val; ans i; } } return ans; }整數(shù)三分的特殊之處循環(huán)條件常用while (r - l 2)。因為當區(qū)間長度小于等于3時兩個三分點m1和m2可能相等或無法有效分割區(qū)間此時直接暴力枚舉區(qū)間內所有整數(shù)點更簡單可靠。中間點計算使用整數(shù)除法。由于是整數(shù)(r-l)/3會向下取整。這保證了m1和m2是整數(shù)且l m1 m2 r。最終處理循環(huán)結束后區(qū)間[l, r]通常只剩下2到3個點。對這些點逐一計算函數(shù)值并比較得到最終的最優(yōu)整數(shù)解。這是確保結果正確的關鍵步驟。3.3 通用模板與參數(shù)化設計一個更通用的模板可以整合尋找最大值和最小值甚至允許自定義比較函數(shù)提高代碼復用率。// 通用三分模板 // cmp: 一個函數(shù)接受兩個double/整數(shù)參數(shù)a,b當a優(yōu)于b時返回true。 template typename T, typename Func T ternary_search(T l, T r, Func f, bool (*cmp)(T, T)) { const double eps 1e-10; // 對于浮點數(shù) while (r - l eps) { // 整數(shù)版本需改為 while (r - l 2) T m1 l (r - l) / 3; T m2 r - (r - l) / 3; if (cmp(f(m1), f(m2))) { // 如果f(m1)比f(m2)更優(yōu)根據(jù)三分邏輯更新端點 // 對于找最小值更優(yōu)意味著更小cmp less // 對于找最大值更優(yōu)意味著更大cmp greater // 更新邏輯需要根據(jù)cmp的具體含義來寫通常需要特化 // 更實用的寫法是下面兩個特化版本 } else { // 更新另一個端點 } } return (l r) / 2; } // 實踐中更清晰的寫法是提供兩個特化函數(shù) double ternary_search_min(double l, double r, double (*f)(double)) { while (r - l 1e-10) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) r m2; else l m1; } return (l r) / 2; } double ternary_search_max(double l, double r, double (*f)(double)) { while (r - l 1e-10) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) l m1; else r m2; } return (l r) / 2; }4. 實戰(zhàn)應用場景與問題剖析三分法模板之所以重要是因為它能解決一系列看似棘手的問題。下面結合幾個典型場景看看如何將問題抽象成單峰函數(shù)求極值。4.1 場景一距離最值問題如“燈泡人”問題問題描述在一條數(shù)軸上有n個點其位置為a[i]。現(xiàn)在要在這條數(shù)軸上找一個點x使得這個點到所有n個點的距離之和f(x) Σ|a[i] - x|最小。這是經典的絕對值和最小問題最優(yōu)解是中位數(shù)。但如果代價不是距離而是距離的平方和f(x) Σ(a[i] - x)^2呢最優(yōu)解是平均數(shù)。如果代價是更復雜的函數(shù)比如f(x) Σ sqrt((a[i] - x)^2 C)C為常數(shù)這就沒有簡單的解析解了。抽象與求解函數(shù)f(x) Σ sqrt((a[i] - x)^2 C)是一個凸函數(shù)可以證明其二階導非負。因此我們可以直接在數(shù)軸的可能范圍例如[min(a[i]), max(a[i])]內使用三分法尋找最小值點x。實現(xiàn)時只需編寫計算f(x)的函數(shù)然后套用浮點數(shù)三分求最小值的模板即可。實操心得這類問題的關鍵在于確定搜索區(qū)間[l, r]。通常極值點不會超出數(shù)據(jù)點的范圍所以將l設為min(a[i])r設為max(a[i])是安全的起點。有時根據(jù)問題物理意義區(qū)間可能需要適當擴大。4.2 場景二最優(yōu)參數(shù)搜索如機器學習中的超參數(shù)調優(yōu)問題描述假設你有一個機器學習模型其性能如準確率是某個連續(xù)超參數(shù)λ例如正則化系數(shù)的函數(shù)P(λ)。通過實驗你發(fā)現(xiàn)P(λ)隨著λ從0開始增大先上升后下降形成一個單峰曲線。你需要找到使準確率最高的λ。抽象與求解將P(λ)視為定義在λ的合理范圍如[0, 10]上的函數(shù)。由于它是單峰的我們可以用三分法來搜索最優(yōu)的λ。這里的f(λ)就是模型在參數(shù)λ下的評估指標計算函數(shù)可能涉及訓練和驗證計算代價較高。注意事項計算成本每次計算f(λ)都可能需要重新訓練或驗證模型非常耗時。因此在設定三分精度eps時要權衡精度和計算成本?？赡苤恍枰械染染湍苷业阶銐蚝玫某瑓?shù)。非嚴格單峰實際中的P(λ)可能不是嚴格的單峰可能存在多個局部極值。三分法只能找到局部最優(yōu)且依賴于初始區(qū)間。在這種情況下三分法可能不如網格搜索或隨機搜索可靠。因此在將三分法應用于此類問題前務必通過初步實驗驗證函數(shù)在選定區(qū)間上的單峰性。4.3 場景三幾何最值問題如“穿越沙漠”問題描述一個經典問題是從點A到點B中間需要經過一條直線L。在A和B位于直線同側的情況下求從A到B經過直線L上一點P的最短路徑。這是一個光的反射原理問題解是使得入射角等于反射角的點。但如果速度在直線兩側不同呢問題就變成了在直線L上找一點P最小化|AP|/v1 |PB|/v2v1,v2為速度。抽象與求解設P點的坐標由其在直線上的某個參數(shù)t表示例如P A0 t * dir其中A0是直線上一點dir是方向向量。那么總時間T(t) |A - P(t)| / v1 |B - P(t)| / v2?？梢宰C明T(t)是關于t的凸函數(shù)。因此我們可以對參數(shù)t在其有效范圍內進行三分搜索尋找使T(t)最小的t。實現(xiàn)技巧計算f(t)時涉及距離計算。確保距離函數(shù)正確并且參數(shù)t的搜索區(qū)間[l, r]涵蓋了所有可能的P點通常可以通過幾何關系確定。由于是連續(xù)函數(shù)使用浮點數(shù)三分模板。5. 常見陷阱、調試技巧與優(yōu)化5.1 陷阱一函數(shù)非單峰這是三分法失敗的最主要原因。如果函數(shù)在搜索區(qū)間內有多個極值點多峰三分法很可能會收斂到某個局部極值點而非全局最優(yōu)。排查與驗證繪制函數(shù)圖像如果可能在應用三分法前用程序在搜索區(qū)間內以較粗的粒度采樣并繪制f(x)的曲線圖直觀檢查單峰性。隨機測試在區(qū)間內隨機選擇大量的點對(x1, x2, x3)且x1 x2 x3檢查是否滿足凸性條件對于最小化問題f(x2) max(f(x1), f(x3))應大致成立。如果大量違反則函數(shù)非凸。領域知識從問題本身分析。很多物理、幾何問題天然具有凸性。經濟學的效用函數(shù)、距離的度量等也常常是凸的。5.2 陷阱二浮點數(shù)精度與循環(huán)終止浮點數(shù)運算存在精度損失。如果eps設置得過小如1e-15可能會因為浮點數(shù)誤差導致r - l始終無法小于eps從而陷入無限循環(huán)或提前終止在錯誤的位置。解決方案設置合理的eps根據(jù)問題對答案的精度要求來設定。通常比輸出要求高2個數(shù)量級足夠安全。使用迭代次數(shù)限制這是更穩(wěn)健的做法。根據(jù)對數(shù)復雜度預先計算一個足夠的迭代次數(shù)。double ternary_search_min(double l, double r) { for (int i 0; i 100; i) { // 循環(huán)100次精度足夠高 double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (f(m1) f(m2)) { r m2; } else { l m1; } } return (l r) / 2; }循環(huán)100次區(qū)間長度將縮小到原來的(2/3)^100 ≈ 2.5e-18倍對于絕大多數(shù)問題都綽綽有余。避免直接比較浮點數(shù)相等在比較f(m1)和f(m2)時如果擔心精度問題可以使用f(m1) eps f(m2)這樣的比較方式但通常直接比較在三分法中問題不大因為決定方向的是大小關系而非精確相等。5.3 陷阱三整數(shù)三分的邊界處理在整數(shù)三分中當區(qū)間長度很小時m1和m2可能相等。如果此時仍然按照f(m1)和f(m2)的比較來更新區(qū)間會導致區(qū)間無法繼續(xù)收縮。正確做法如前文模板所示當r - l 2時跳出主循環(huán)然后暴力枚舉區(qū)間[l, r]內的所有整數(shù)點。這是最安全、最清晰的做法。切勿嘗試在m1 m2時進行特殊邏輯處理那樣容易出錯。5.4 調試技巧打印日志在循環(huán)內打印l, r, m1, m2, f(m1), f(m2)的值。觀察區(qū)間是否在穩(wěn)步縮小以及函數(shù)值的比較是否符合你對函數(shù)形狀的預期。驗證單峰性在最終區(qū)間內或隨機點上多計算幾個f(x)的值檢查是否滿足“先減后增”或“先增后減”的規(guī)律。與暴力枚舉對比對于小范圍問題可以寫一個暴力枚舉所有可能解以很小步長采樣的程序將三分法的結果與暴力枚舉的結果進行對比驗證正確性。檢查函數(shù)實現(xiàn)確保你編寫的f(x)函數(shù)是正確的。這是三分法的基礎往往錯誤就出在這里。特別是當f(x)涉及復雜計算或模擬時要單獨測試這個函數(shù)。5.5 性能優(yōu)化三分法本身已經非常高效。優(yōu)化點主要在于昂貴的f(x)計算記憶化如果f(x)是純函數(shù)且計算昂貴可以考慮緩存記憶化已經計算過的x對應的f(x)值。但在三分法中x是連續(xù)值很難直接命中緩存除非離散化。并行計算在一次迭代中f(m1)和f(m2)的計算是獨立的可以并行進行以提升速度?？s小初始區(qū)間盡可能利用問題性質縮小[l, r]的初始范圍減少迭代次數(shù)。例如通過求導、不等式分析或粗略估計確定極值點的大致位置。6. 模板的變體與擴展6.1 黃金分割法三分法將區(qū)間分成三等份。一個自然的想法是有沒有更優(yōu)的分割比例黃金分割法0.618法就是一種選擇它每次迭代將區(qū)間長度縮小到原來的約0.618倍黃金分割比。與三等分相比黃金分割法的優(yōu)勢在于它每次迭代只需要計算一個新的函數(shù)值因為其中一個點可以復用上一次迭代的點而三分法需要計算兩個新值。當f(x)計算非常昂貴時黃金分割法更有優(yōu)勢。double golden_section_search(double l, double r) { const double phi (sqrt(5) - 1) / 2; // 約 0.618 double m1 r - phi * (r - l); double m2 l phi * (r - l); double f1 f(m1), f2 f(m2); while (r - l eps) { if (f1 f2) { // 找最小值 r m2; m2 m1; f2 f1; m1 r - phi * (r - l); f1 f(m1); } else { l m1; m1 m2; f1 f2; m2 l phi * (r - l); f2 f(m2); } } return (l r) / 2; }6.2 自適應三分與牛頓法對于導數(shù)容易求得的凸函數(shù)牛頓法或梯度下降法的收斂速度更快二階收斂。但三分法的優(yōu)勢在于不需要導數(shù)信息適用性更廣。有一種混合策略先使用幾次三分法快速縮小區(qū)間然后在足夠小的區(qū)間內使用牛頓法進行精確求解。這結合了三分法的穩(wěn)健性和牛頓法的快速收斂性。6.3 高維空間的最優(yōu)值搜索標準的二分法和三分法只適用于一維搜索。對于多維變量的凸函數(shù)優(yōu)化我們需要其他方法如梯度下降、共軛梯度法或更高級的優(yōu)化算法。然而有時多維問題可以轉化為一系列一維問題例如坐標輪換法每次固定其他變量只優(yōu)化一個變量這時就可以在該維度上使用一維搜索方法包括三分法。7. 從理解到精通思維訓練與題目推薦要真正掌握三分法不能只停留在套模板。我建議通過以下步驟進行思維訓練證明單峰性拿到一個問題首先嘗試從數(shù)學上證明或至少說服自己目標函數(shù)在搜索區(qū)間上是單峰的。思考它的導數(shù)符號變化或者利用幾何意義、不等式來論證。手動模擬對于一個小例子用紙筆手動模擬三分法的迭代過程感受區(qū)間是如何一步步縮小的。修改模板嘗試自己編寫支持尋找最大值、最小值的統(tǒng)一模板并增加對整數(shù)域和浮點數(shù)域的支持。解決變體問題嘗試解決一些三分法的變體問題例如尋找一個函數(shù)滿足f(x) target的x如果函數(shù)是單調的用二分如果是凸的可能需要結合三分和函數(shù)值比較。經典練習題推薦可在各大在線判題平臺搜索基礎/模板題直接考察三分法實現(xiàn)通常給出一個明顯的凸函數(shù)讓你求極值點。距離問題變種如前面提到的帶權距離和、復雜距離函數(shù)如加上平方根的最小化問題。幾何問題光線傳播、最佳觀測點、最短時間路徑等問題常能轉化為凸函數(shù)優(yōu)化。物理問題涉及能量、時間最優(yōu)的問題往往具有凸性。經濟模型一些簡單的成本、收益模型在特定假設下也是凸的。最后記住三分法是一個工具它的威力在于將“尋找最優(yōu)”這個模糊的目標轉化為一個可以通過機械迭代精確逼近的過程。當你遇到一個求最值的問題并且感覺函數(shù)值隨著參數(shù)變化是“先好后壞”或“先壞后好”時不妨想想這會不會是一個單峰函數(shù)能不能用三分法來試試這種思維習慣的養(yǎng)成比記住十個模板更有價值。在實際編碼中我習慣將三分法函數(shù)封裝好并附上清晰的注釋說明是用于找最大值還是最小值輸入區(qū)間和精度要求是什么。這樣在競賽或項目遇到相關問題時我可以像調用庫函數(shù)一樣快速、準確地應用它把精力集中在問題建模和函數(shù)f(x)的實現(xiàn)上。