幾何問(wèn)題中的離治法

4.5幾何問(wèn)題中的離治法4.5.1最近對(duì)問(wèn)題

4.5.2凸包問(wèn)題4.5.1最近對(duì)問(wèn)題

設(shè)p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n個(gè)點(diǎn)構(gòu)成的集合S，最近對(duì)問(wèn)題就是找出集合S中距離最近的點(diǎn)對(duì)。嚴(yán)格地講，最接近點(diǎn)對(duì)可能多于一對(duì)，簡(jiǎn)單起見，只找出其中的一對(duì)作為問(wèn)題的解。

用離治法解決最近對(duì)問(wèn)題，很自然的想法就是將集合S分成兩個(gè)子集S1和S2，每個(gè)子集中有n/2個(gè)點(diǎn)。然后在每個(gè)子集中途歸地求其最接近的點(diǎn)對(duì)，在求出每個(gè)子集的最接近點(diǎn)對(duì)后，在合并步中，如果集合S中最接近的兩個(gè)點(diǎn)都在子集S1或S2中，則問(wèn)題很容易解決，如果這兩個(gè)點(diǎn)分別在S1和S2中，問(wèn)題就比較復(fù)雜了。為了使問(wèn)題易于理解，先考慮一維的情形。此時(shí)，S中的點(diǎn)退化為x軸上的n個(gè)點(diǎn)x1,x2,…,xn。用x軸上的某個(gè)點(diǎn)m將S劃分為兩個(gè)集合S1和S2，并且S1和S2含有點(diǎn)的個(gè)數(shù)相同。途歸地在S1和S2上求出最接近點(diǎn)對(duì)(p1,p2)和(q1,q2)，如果集合S中的最接近點(diǎn)對(duì)都在子集S1或S2中，則d=min{(p1,p2),(q1,q2)}即為所求，如果集合S中的最接近點(diǎn)對(duì)分別在S1和S2中，則一定是(p3,q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。為了使問(wèn)題易于理解，先考慮一維的情形。此時(shí)，S中的點(diǎn)退化為x軸上的n個(gè)點(diǎn)x1,x2,…,xn。用x軸上的某個(gè)點(diǎn)m將S劃分為兩個(gè)集合S1和S2，并且S1和S2含有點(diǎn)的個(gè)數(shù)相同。途歸地在S1和S2上求出最接近點(diǎn)對(duì)(p1,p2)和(q1,q2)，如果集合S中的最接近點(diǎn)對(duì)都在子集S1或S2中，則d=min{(p1,p2),(q1,q2)}即為所求，如果集合S中的最接近點(diǎn)對(duì)分別在S1和S2中，則一定是(p3,q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。按這種離治策略求解最近對(duì)問(wèn)題的算法效率取決于劃分點(diǎn)m的選取，一個(gè)基本的要求是要遵循平衡子問(wèn)題的原則。如果選取m=(max{S}+min{S})/2，則有可能因集合S中點(diǎn)分布的不均勻而造成子集S1和S2的不平衡，如果用S中各點(diǎn)坐標(biāo)的中位數(shù)（即S的中值）作為分割點(diǎn)，則會(huì)得到一個(gè)平衡的分割點(diǎn)m，使得子集S1和S2中有個(gè)數(shù)大致相同的點(diǎn)。下面考慮二維的情形，此時(shí)S中的點(diǎn)為平面上的點(diǎn)。為了將平面上的點(diǎn)集S分割為點(diǎn)的個(gè)數(shù)大致相同的兩個(gè)子集S1和S2，選取垂直線x=m來(lái)作為分割線，其中，m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1={p∈S|xp≤m}和S2={q∈S|xq＞m}。途歸地在S1和S2上求解最近對(duì)問(wèn)題，分別得到S1中的最近距離d1和S2中的最近距離d2，令d=min(d1,d2)，若S的最近對(duì)(p,q)之間的距離小于d，則p和q必分屬于S1和S2，不妨設(shè)p∈S1，q∈S2，則p和q距直線x=m的距離均小于d，所以，可以將求解限制在以x=m為中心、寬度為2d的垂直帶P1和P2中，垂直帶之外的任何點(diǎn)對(duì)之間的距離都一定大于d。

4.5.2凸包問(wèn)題

設(shè)p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n個(gè)點(diǎn)構(gòu)成的集合S，并且這些點(diǎn)按照x軸坐標(biāo)升序排列。幾何學(xué)中有這樣一個(gè)明顯的事實(shí)：最左邊的點(diǎn)p1和最右邊的點(diǎn)pn一定是該集合的凸包頂點(diǎn)（即極點(diǎn)）。設(shè)p1pn是從p1到pn的直線，這條直線把集合S分成兩個(gè)子集：S1是位于直線左側(cè)和直線上的點(diǎn)構(gòu)成的集合，S2是位于直線右側(cè)和直線上的點(diǎn)構(gòu)成的集合。S1的凸包由下列線段構(gòu)成：以p1和pn為端點(diǎn)的線段構(gòu)成的下邊界，以及由多條線段構(gòu)成的上邊界，這條上邊界稱為上包。類似地，S2中的多條線段構(gòu)成的下邊界稱為下包。整個(gè)集合S的凸包是由上包和下包構(gòu)成的。

p1pmaxpn快包的思想是：首先找到S1中的頂點(diǎn)pmax，它是距離直線p1pn最遠(yuǎn)的頂點(diǎn)，則三角形pmaxp1pn的面積最大。S1中所有在直線pmaxp1左側(cè)的點(diǎn)構(gòu)成集合S1,1，S1中所有在直線pmaxpn右側(cè)的點(diǎn)構(gòu)成集合S1,2，包含在三角形pmaxp1pn之中的點(diǎn)可以不考慮了。途歸地繼續(xù)構(gòu)造集合S1,1的上包和集合S1,2的上包，然后將求解過(guò)程中得到的所有最遠(yuǎn)距離的點(diǎn)連接起來(lái)，就可以得到集合S1的上包。接下來(lái)的問(wèn)題是如何判斷一個(gè)點(diǎn)是否在給定直線的左側(cè)（或右側(cè)）？幾何學(xué)中有這樣一個(gè)定理：如果p1=(x1,y1),p2=(x2,y2),p3=(x3,y3)是平面上的任意三個(gè)點(diǎn)，則三角形p1p2p3的面積等于下面這個(gè)行列式的絕對(duì)值的一半：當(dāng)且僅當(dāng)點(diǎn)p3=(x3,y3)位于直線p1p2的左側(cè)時(shí)，該式的符號(hào)為正?？梢栽谝粋€(gè)常數(shù)時(shí)間內(nèi)檢查一個(gè)點(diǎn)是否位于兩個(gè)點(diǎn)確定的直線的左側(cè)，并且可以求得這個(gè)點(diǎn)到該直線的距離。311223321321332211111yxyxyxyxyxyxyxyxyx---++=蟻群算法(antcolonyoptimization,ACO)，又稱螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。由MarcoDorigo于1992年在他的博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。

為什么小小的螞蟻能夠找到食物？他們具有智能么？如果我們要為螞蟻設(shè)計(jì)一個(gè)人工智能的程序，那么這個(gè)程序要多么復(fù)雜呢？首先，必須根據(jù)適當(dāng)?shù)牡匦谓o它編進(jìn)指令讓他們能夠巧妙的避開障礙物；其次，需要讓他們遍歷空間上的所有點(diǎn)；再次，計(jì)算所有可能的路徑并且比較它們的大??；你要小心翼翼的編程，這是多么不可思議的程序！太復(fù)雜了，恐怕沒(méi)人能夠完成這樣繁瑣冗余的程序。M.Dorigo等人于1991年首先提出了蟻群算法。其主要特點(diǎn)就是：通過(guò)正反饋、分布式協(xié)作來(lái)尋找最優(yōu)路徑。這是一種基于種群尋優(yōu)的啟發(fā)式搜索算法。它充分利用了生物蟻群能通過(guò)個(gè)體間簡(jiǎn)單的信息傳遞，搜索從蟻巢至食物間最短路徑的集體尋優(yōu)特征，以及該過(guò)程與旅行商問(wèn)題求解之間的相似性。得到了具有NP難度的旅行商問(wèn)題的最優(yōu)解答。同時(shí)，該算法還被用于求解Job-Shop調(diào)度問(wèn)題、二次指派問(wèn)題以及多維背包問(wèn)題等，顯示了其適用于組合優(yōu)化類問(wèn)題求解的優(yōu)越特征。多年來(lái)世界各地研究工作者對(duì)蟻群算法進(jìn)行了精心研究和應(yīng)用開發(fā)，該算法現(xiàn)己被大量應(yīng)用于數(shù)據(jù)分析、機(jī)器人協(xié)作問(wèn)題求解、電力、通信、水利、采礦、化工、建筑、交通等領(lǐng)域。美國(guó)五角大樓正在資助關(guān)于群智能系統(tǒng)的研究工作-群體戰(zhàn)略(SwarmStrategy)，它的一個(gè)實(shí)戰(zhàn)用途是通過(guò)運(yùn)用成群的空中無(wú)人駕駛飛行器和地面車輛來(lái)轉(zhuǎn)移敵人的注意力，讓自己的軍隊(duì)在敵人后方不被察覺(jué)地安全進(jìn)行。英國(guó)電信