題目（下文為簡化后的模型）：在平面α上有兩條線段AB , CD。已知陶陶在平面α上的移動速度為v1，在線段AB上的移動速度為v2，在線段CD上的移動速度為v3（v3,v2>v1）。已知A,B,C,D的坐標，求小陶從A點出發(fā)到達D點所用的最短時間。

解：

(封面為本題模型草圖)

設點M,N分別在線段AB，CD上

由幾何不等式得最優(yōu)路徑一定為A→M→N→D

設向量AM=aAB，向量ND=bCD? ? a,b∈[0,1]

可求出總時長T是關于a,b的一個函數(shù)

于是想到對a,b進行枚舉，得到樸素算法.

三分：

若把a視為參數(shù)，則可推導出T是一個單調或單峰函數(shù)（單調性取決于角BAD，為鈍角則為單調，為銳角則為單峰。證明見下圖）

因此，若把a視為參數(shù)，我們可以用三分法求出T的最小值

于是想到對a進行枚舉，對每一個枚舉的a值，再對b三分即可求出T的最小值

樸素和三分的時間復雜度見下圖