论文国家队金恺

《论文国家队金恺》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、极限法——解决几何最优化问题的捷径长郡中学金恺【关键字】最优值极限无穷小微调在平血几何问题中我们经常会遇到一些求极值的问题。在这些问题中，口变量和目标函数町能涉及到坐标、斜率、长度、角度、周长、面积等等一些复杂的量，而且往往口变量还有一些复朵的约束条件，因此直接用函数求极值的方法是行不通或极其复杂的。这些问题中，变量往往有无穷多种取值方案（比如说点的取值范围可能是整个平而或在某条直线上），所以无法枚举毎-•种取值方案來找最值，这时往往能够通过极限法证明：口变量取某些非特殊情况值时H标函数不可能是最

2、优的——因为这时经过微调一个无穷小量I能够使得H标函数的值变得更优，从而剩下有限种特殊的取值情况可能成为最优解，通过枚举所冇特殊情况就能找到目标函数的最优解了。2在另一些同类问题中，本來就可以通过枚举有限个取值情况求出最优解，但是枚举的量很人，时间复杂度较高，我们也可尝试通过极限法來大大减少需要枚举的情况，从而降低时间复杂度。以上就是极限法的大致思想，它的作用简而言之就是化无限为有限，变有限为少量。正文极限法的应用实例菲常的多，比如经典的最小矩形覆盖3问题，就是通过极限法证明了：最小矩形的某条边必

3、须过两个已知点，从而大大减少了需要枚举的矩形数目。然而极限法用起來的确有较人的困难，有时候证明起來非常困难，可能情况比较复杂，也可能不知道如何调整，需要用到三角两数Z类的比较复杂的数学知识，因此其正掌握它需要扎实的数学功底，极强的观察力以及必要的经验是必不可少的。下面就来用极限法解决一些典型问题，从实例的分析中一步一步深入地认识极限法的用途和用法。例题一、巧克力'比如旋转一个无穷小的角度、微移-•段无穷小的距离。在本文中，微量这一名词就是指无穷小量：只要改变得足够小（无穷小），就能使点的相对位置、

4、线段的相交情况等不发生改变。2极限法的本质也就是对目标函数求导，如果导数不为0并口白变量不在定义域的边界则不可能为最优值。这正是采用“极限法”來命名的原因。3平浙上有〃个已知点，求一个面积最小的矩形，使得所冇已知点都在矩形的内部。页共12页问题描述：糖果厂有一种凸起的N(4WNW50)边形巧克力，Kiddy和Carlson凑钱买了一块，想把它用一•刀割成两半。两半的大小必须相等，找出用以分割巧克力的分割线的最短长度。数学模型：已知N个点(XJi)lWiWN构成一凸包P｛已知量｝,求一条划分线L,使

5、得分割线两侧的而积相等｛约束条件｝,并且使L的长度｛目标函数｝最小。问题分析：设分割线的两个端点分别为A、B,A、B可能在P的顶点上也有可能只在P的边上｛不含端点｝。我们分开解决这两种情况：A1、4在P的顶点上(或3在P的顶点上，此时交换Si=SrAB):显然可以枚举P中的一个顶点作为A，由分割SLLQ线两侧而积相等这一约束条件直接确定B的位置，如图1。2、A、B都在P的边上：枚举A、B所在的两条边，B设这两条边相交于C,如图2：图1AAfaa+00UL阴卩B，B设ZC=y,ZCAB=a,ZCBA

6、邙。当a^p时，可以证明：把分割线L稍微旋转一个无穷小量0到L'并保持厶'两边的面积相等，能够使乙‘的长度小于L.证明如下：不妨设旋转后U仍与原來的两边相交(因为仅旋转了一个无穷小量)，交点为B',ZCq'B'w+O,ZCBA=/?-Oo在三角形ABC中，有正弦定理:ACBCsin®sin〈sin©在三角形ABC中，有正弦定理:A2CB2CL2sin(®()sin(〈+()sin©第2页共12页由于L和Z/都是分割线,所以Sabc=Sabg即1122™AC㊉BC=A2C㊉B2CLsin®Lsin

7、(L2sin(®()£2sin(〈+()TM*卜sin©sin©sin©sin©w、二pi>®>(>04pi>®(>04cos(®(2()>cos(®〈)4>所以LoLS,即L'a时，厶不可能为最短的分割线。同理，当卩勺时，厶也不可能是最短的。若L是不过P的顶点的最短的分割线，那么J与P的两个夹角必然相等。这就是我们希望得到的，因为枚举L两个端点所在的边后，L的斜率就确定了，再根据L的两边而积相等，就可以直接算出

8、L的位置。得到了这些结论后，已能够图3设计出0(N2)的算法。小结：通过此题，我们已经初次接触到了极限法，并利用它得到了一个极其简单的结论。使得自变量的取值范I韦I从无穷多条玄线减少到了有限条，从而通过简单的穷举法解决。例题二、太空站SPACE(2003集训讨论试题之0039)问题描述：平面上有0000)个互不重合的点，要求一条玄线，使得所有点到这条肓线的距离和最小。数学模型：已知n点的坐标分别为：V心1ji),必(尤2,尹),・・・必仏片)。肓线l(ax+by+c=0(ab^()