国家集训队2004论文集 金恺

《国家集训队2004论文集 金恺》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、极限法——解决几何最优化问题的捷径长郡中学金恺概述在平面几何问题中我们经常会遇到一些求极值的问题。在这些问题中，自变量和目标函数可能涉及到坐标、斜率、角度、周长、面积等等一些复杂的量，而且自变量往往还有复杂的约束条件，所以直接用求函数最值的方法无从下手或者极其复杂。化无限为有限在这些问题中，自变量往往有无穷多种取值方案（比如点在平面上)，无法枚举每种取值方案来求最值。怎么办？通过极限法，可以证明：自变量取非特殊情况时函数不可能得到最优解，因为把自变量微调一个无穷小量能够使得目标函数变得更优。从而只剩下有限个特殊情况需要考虑。枚举所有的特殊情

2、况，就可找到最优解了。化有限为少量在另一些问题中，本就可以通过枚举有限个特殊情况求出最优解，但是枚举的量很大，时间复杂度较高；尝试通过极限法减少需要枚举的情况数，降低时间复杂度。极限法的本质就是对目标函数求导：如果自变量不取定义域的边界（取边界时对应某些特殊情况）并且这一点的导数不为0（导数为0时对应另一些特殊情况），则目标函数不可能为最优值。例题一、巧克力问题描述：两个小孩一起买了一块凸N边形巧克力，想一刀把它割成两半,两半的面积必须相等。找出用以分割巧克力的分割线的最短长度。数学模型：已知量：N个点(Xi,Yi),1≤i≤N，构成一个凸

3、包P；求：一条分割线L；约束条件：P在L两侧的面积相等；目标函数：L的长度；要求使目标函数值最小的一条L。问题分析设L的两个端点为A、B；L可能过P的顶点也可能不过，分开解决这两种情况：1、A在P的顶点上（B在P的顶点上类似）1)枚举P中的一个顶点作为A；2)由分割线两侧面积相等确定B所在的边；3)算出B的具体位置。ASLSRBL2、A、B都在P的边{不含端点}上：枚举A、B所在的两条边a、b设这两条边相交于C，∠C=γBCγβαLA设∠CAB=α，∠CBA=β。下面将证明α≠β时（即非特殊情况下），L不是最优的分割线。不妨设β>αab

4、先把L绕B点往交点C方向旋转一个微量θ；再平移一个微量到L'使P在L'两边的面积相等；L'仍与a、b相交，交点为A'、B'；则∠CA'B'=α+θ，∠CB'A'=β-θ；A'BCα+θγβαθθβ-θLAB'L'θL和L'都是分割线，所以ab∴L2>L'2，L'1由正弦定理：AC·BC=A'C·B'C结论如果a、b平行即C在无穷远处，也有相同结论若L是最短的分割线但不经过P的顶点，那么L与P的两个夹角必然相等。枚举a、b后，确定L的斜率，根据P在L两边面积相等，可算出L的位置。需要枚举的a、b只有N对，可以

5、用滑动指针的算法找到所有这样的边对，总复杂度为O(N)通过此题，我们已经初次接触到了极限法，并利用它得到了一个极其简单的结论。本题中极限法的作用是：把自变量的取值范围从无穷多条直线减少到了N条直线。例题二、太空站问题描述：平面上有n(3≤n≤10000)个互不重合的已知点，求一条直线，使得所有已知点到这条直线的距离和最小。数学模型已知n点的坐标分别为：V1(x1,y1),V2(x2,y2),…,Vn(xn,yn)。直线l(ax+by+c=0(ab≠0))的费用定义为求min{f(l)}想法：枚举所有的直线，得到最优值平面中的直线有无穷多条怎

6、样的直线才有可能是我们要找的那一条呢？若l不经过任何已知点。设l两侧的点数分别有a、b个，a≥b将l往点多的一侧平移一个无穷小量△到l'则f(l')-f(l)=b△-a△=(b-a)△≤0∴f(l')≤f(l)所以已知点相对于l的位置未发生改变，即a、b值未变。可不断往同一个方向平移l'直至碰到一个已知点，到l''处，同样有f(l'')≤f(l)。l''经过某一个已知点，且费用不比l高。l'l''①规定直线l经过某一个已知点。la个点b个点△△△②直线l必经过两个已知点。根据结论①，设l过V1，而不过其它已知点。定义：Li—Vi到V

7、1的距离αi—Vi到l的垂线与ViV1的夹角lα2α4α3α7α5α6L2L4L3L7L5L6V1V4V3V5V6V7V2证明②将l绕V1逆时针旋转一个无穷小的角度θ到l'；将l顺时针旋转相同的角度θ到l''；θ足够小，使旋转过程中不碰到其它的已知点。ll'l''θθ单独的考虑一个已知点i(i>1)到l的距离的改变当αi=0时∵直角三角形中直角边<斜边∴不论直线旋转到l'还是l''，Vi到直线的距离都严格减小了ViV1ll'l''当αi>0时θθV1Viαiθθθθ对称的情况：∴l不可能为最优的ll'l''或∴算法一待枚举的直线变为了有限条

8、(N2条)，得到一个有效的算法：min∞枚举两个已知点根据这两个点确定直线h计算f(h)若f(h)