幾何問題中的離治法

4.5幾何問題中的離治法4.5.1最近對問題

4.5.2凸包問題4.5.1最近對問題

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

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

4.5.2凸包問題

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

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

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