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