論文--極限法——解決幾何最優(yōu)化問題的捷徑

《論文--極限法——解決幾何最優(yōu)化問題的捷徑》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、極限法——解決幾何最優(yōu)化問題的捷徑【關(guān)鍵字】最優(yōu)值極限無窮小微調(diào)【概述】在平面幾何問題中我們經(jīng)常會(huì)遇到一些求極值的問題。在這些問題中，自變量和目標(biāo)函數(shù)可能涉及到坐標(biāo)、斜率、長(zhǎng)度、角度、周長(zhǎng)、面積等等一些復(fù)雜的量，而且往往自變量還有一些復(fù)雜的約束條件，因此直接用函數(shù)求極值的方法是行不通或極其復(fù)雜的。這些問題中，變量往往有無窮多種取值方案（比如說點(diǎn)的取值范圍可能是整個(gè)平面或在某條直線上），所以無法枚舉每一種取值方案來找最值，這時(shí)往往能夠通過極限法證明：自變量取某些非特殊情況值時(shí)目標(biāo)函數(shù)不可能是最優(yōu)的——因?yàn)檫@時(shí)經(jīng)過微調(diào)一個(gè)無窮小量比如旋轉(zhuǎn)一個(gè)無窮小的角度、微移一段無窮小的距離。在

2、本文中，微量這一名詞就是指無窮小量：只要改變得足夠?。o窮小），就能使點(diǎn)的相對(duì)位置、線段的相交情況等不發(fā)生改變。能夠使得目標(biāo)函數(shù)的值變得更優(yōu)，從而剩下有限種特殊的取值情況可能成為最優(yōu)解，通過枚舉所有特殊情況就能找到目標(biāo)函數(shù)的最優(yōu)解了。極限法的本質(zhì)也就是對(duì)目標(biāo)函數(shù)求導(dǎo)，如果導(dǎo)數(shù)不為0并且自變量不在定義域的邊界則不可能為最優(yōu)值。這正是采用“極限法”來命名的原因。在另一些同類問題中，本來就可以通過枚舉有限個(gè)取值情況求出最優(yōu)解，但是枚舉的量很大，時(shí)間復(fù)雜度較高，我們也可嘗試通過極限法來大大減少需要枚舉的情況，從而降低時(shí)間復(fù)雜度。以上就是極限法的大致思想，它的作用簡(jiǎn)而言之就是化無限為有

3、限，變有限為少量。正文極限法的應(yīng)用實(shí)例非常的多，比如經(jīng)典的最小矩形覆蓋平面上有n個(gè)已知點(diǎn)，求一個(gè)面積最小的矩形，使得所有已知點(diǎn)都在矩形的內(nèi)部。問題，就是通過極限法證明了：最小矩形的某條邊必須過兩個(gè)已知點(diǎn)，從而大大減少了需要枚舉的矩形數(shù)目。然而極限法用起來的確有較大的困難，有時(shí)候證明起來非常困難，可能情況比較復(fù)雜，也可能不知道如何調(diào)整，需要用到三角函數(shù)之類的比較復(fù)雜的數(shù)學(xué)知識(shí)，因此真正掌握它需要扎實(shí)的數(shù)學(xué)功底，極強(qiáng)的觀察力以及必要的經(jīng)驗(yàn)是必不可少的。下面就來用極限法解決一些典型問題，從實(shí)例的分析中一步一步深入地認(rèn)識(shí)極限法的用途和用法。例題一、巧克力問題描述：糖果廠有一種凸起的N

4、（4≤N≤50）邊形巧克力，Kiddy和Carlson湊錢買了一塊，想把它用一刀割成兩半。兩半的大小必須相等，找出用以分割巧克力的分割線的最短長(zhǎng)度。數(shù)學(xué)模型：已知N個(gè)點(diǎn)(Xi,Yi)1≤i≤N構(gòu)成一凸包P{已知量}，求一條劃分線L，使得分割線兩側(cè)的面積相等{約束條件}，并且使L的長(zhǎng)度{目標(biāo)函數(shù)}最小。ASRBLSLSL=SR問題分析：設(shè)分割線的兩個(gè)端點(diǎn)分別為A、B，A、B可能在P的頂點(diǎn)上也有可能只在P的邊上{不含端點(diǎn)}。我們分開解決這兩種情況：1、A在P的頂點(diǎn)上（或B在P的頂點(diǎn)上，此時(shí)交換AB）：顯然可以枚舉P中的一個(gè)頂點(diǎn)作為A，由分割線兩側(cè)面積相等這一約束條件直接確定B的位

5、置，如圖1。圖12、A、B都在P的邊上：枚舉A、B所在的兩條邊，設(shè)這兩條邊相交于C，如圖2：A’BCα+θγβαθθβ-θLAB’L’圖2設(shè)∠C=γ，∠CAB=α，∠CBA=β。當(dāng)α≠β時(shí)，可以證明：把分割線L稍微旋轉(zhuǎn)一個(gè)無窮小量θ到L’并保持L’兩邊的面積相等，能夠使L’的長(zhǎng)度小于L。證明如下：不妨設(shè)α>β，旋轉(zhuǎn)后L’仍與原來的兩邊相交（因?yàn)閮H旋轉(zhuǎn)了一個(gè)無窮小量），交點(diǎn)為A’、B’，∠CA’B’=α+θ，∠CBA=β-θ。在三角形ABC中，有正弦定理：在三角形A’B’C中，有正弦定理：由于L和L’都是分割線，所以SABC=SA’B’C，即圖3所以L2>L’2，即L’

6、果A、B所在的兩邊平行（即C在無窮遠(yuǎn)處），也有相同的結(jié)論（如圖3）。因此若β>α?xí)r，L不可能為最短的分割線。同理，當(dāng)β<α?xí)r，L也不可能是最短的。若L是不過P的頂點(diǎn)的最短的分割線，那么L與P的兩個(gè)夾角必然相等。這就是我們希望得到的，因?yàn)槊杜eL兩個(gè)端點(diǎn)所在的邊后，L的斜率就確定了，再根據(jù)L的兩邊面積相等，就可以直接算出L的位置。得到了這些結(jié)論后，已能夠設(shè)計(jì)出O(N2)的算法。小結(jié)：通過此題，我們已經(jīng)初次接觸到了極限法，并利用它得到了一個(gè)極其簡(jiǎn)單的結(jié)論。使得自變量的取值范圍從無窮多條直線減少到了有限條，從而通過簡(jiǎn)單的窮舉法解決。例題二、太空站SPACE(2003集訓(xùn)討論試題之00

7、39)問題描述：平面上有n(3≤n≤10000)個(gè)互不重合的點(diǎn)，要求一條直線，使得所有點(diǎn)到這條直線的距離和最小。數(shù)學(xué)模型：已知n點(diǎn)的坐標(biāo)分別為：V1(x1,y1),V2(x2,y2),…Vn(xn,yn)。直線l(ax+by+c=0(ab≠0))的f值定義為，求min{f(l)}。試題分析：最容易想到的做法是枚舉所有的直線，得到最優(yōu)值。但平面中的直線有無窮多條，怎樣的直線才有可能是我們要找的那一條呢？⑴可以規(guī)定直線l經(jīng)過某一個(gè)已知點(diǎn)。因?yàn)椋喝鬺不經(jīng)過任何一個(gè)已知點(diǎn)，則l兩側(cè)肯定有一側(cè)的點(diǎn)數(shù)不少于另一側(cè)，