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

4.5.2凸包問題4.5.1最近對問題

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

用離治法解決最近對問題，很自然的想法就是將集合S分成兩個子集S1和S2，每個子集中有n/2個點。然后在每個子集中途歸地求其最接近的點對，在求出每個子集的最接近點對后，在合并步中，如果集合S中最接近的兩個點都在子集S1或S2中，則問題很容易解決，如果這兩個點分別在S1和S2中，問題就比較復雜了。為了使問題易于理解，先考慮一維的情形。此時，S中的點退化為x軸上的n個點x1,x2,…,xn。用x軸上的某個點m將S劃分為兩個集合S1和S2，并且S1和S2含有點的個數相同。途歸地在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含有點的個數相同。途歸地在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中各點坐標的中位數（即S的中值）作為分割點，則會得到一個平衡的分割點m，使得子集S1和S2中有個數大致相同的點。下面考慮二維的情形，此時S中的點為平面上的點。為了將平面上的點集S分割為點的個數大致相同的兩個子集S1和S2，選取垂直線x=m來作為分割線，其中，m為S中各點x坐標的中位數。由此將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，不妨設p∈S1，q∈S2，則p和q距直線x=m的距離均小于d，所以，可以將求解限制在以x=m為中心、寬度為2d的垂直帶P1和P2中，垂直帶之外的任何點對之間的距離都一定大于d。

4.5.2凸包問題

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

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

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