【正文】 ile是一個(gè)全局整形變量，用來表示 L形骨牌的編號，初始值為 0。 tr：棋盤左上角方格的行號； tc：棋盤左上角方格的列號； dr：特殊方各所在的行號； dc：特殊方各所在的列號； size： size=2k，棋盤規(guī)格為 2k 2k。 復(fù)雜度分析： T(k)=4k1=O(4k) 漸進(jìn)意義下的最優(yōu)算法 ? ?? ?? ? ? ?????????111401kOkTkOkT77 最接近點(diǎn)對問題 問題描述：給定平面上 n個(gè)點(diǎn)，找其中的一對點(diǎn)，使得在 n個(gè)點(diǎn)所組成的所有點(diǎn)對中，該點(diǎn)對間的距離最小。 說明： 嚴(yán)格來講，最接近點(diǎn)對可能多于一對，為簡便起見，我們只找其中的一對作為問題的解。 一個(gè)簡單的做法是將每一個(gè)點(diǎn)與其他 n1個(gè)點(diǎn)的距離算出，找出最小距離的點(diǎn)對即可。該方法的時(shí)間復(fù)雜性是 T(n)=n(n1)/2+n=O(n2)，效率較低。 已經(jīng)證明，該算法的計(jì)算時(shí)間下界是 Ω(nlogn)。 78 一維空間中的情形 先來考慮一維的情形。此時(shí)， S中的 n個(gè)點(diǎn)退化為 x軸上的 n個(gè)實(shí)數(shù) x1,x2,…,xn 。最接近點(diǎn)對即為這 n個(gè)實(shí)數(shù)中相差最小的 2個(gè)實(shí)數(shù)。 一個(gè)簡單的辦法是先把 x1,x2,…,xn 排好序，再進(jìn)行一次線性掃描就可以找出最接近點(diǎn)對， T(n)=O(nlogn)。然而這種方法無法推廣到二維情形。 假設(shè)我們用 x軸上某個(gè)點(diǎn) m將 S劃分為 2個(gè)子集 S1和 S2 ，基于平衡子問題的思想，用 S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。 遞歸地在 S1和 S2上找出其最接近點(diǎn)對 {p1,p2}和 {q1,q2}，并設(shè) d=min{|p1p2|,|q1q2|}， S中的最接近點(diǎn)對或者是 {p1,p2}，或者是 {q1,q2}，或者是某個(gè) {p3,q3}，其中 p3∈ S1且 q3∈ S2。 能否在線性時(shí)間內(nèi)找到 p3,q3？ 79 如果 S的最接近點(diǎn)對是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者與 m的距離不超過 d，即 p3∈ (md,m]， q3∈ [m,m+d)。 由于在 S1中，每個(gè)長度為 d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于 d），并且 m是 S1和 S2的分割點(diǎn)，因此(md,m]中至多包含 S中的一個(gè)點(diǎn)。由圖可以看出，如果 (md,m]中有 S中的點(diǎn)，則此點(diǎn)就是 S1中最大點(diǎn)。 因此，我們用線性時(shí)間就能找到區(qū)間 (md,m]和 [m,m+d)中所有點(diǎn)，即 p3和 q3。從而我們用線性時(shí)間就可以將 S1的解和 S2的解合并成為 S的解。 分割點(diǎn) m的選取不當(dāng)，會造成 |Si|=1， |Sj|=n1的情形，使得T(n) =T(n1)+O(n)=O(n2)。這種情形可以通過“平衡子問題”方法加以解決：選取各點(diǎn)坐標(biāo)的中位數(shù)作分割點(diǎn)。 一維空間中的情形 80 算法描述及復(fù)雜性 算法描述： bool CPair1(S, d) { n=|S|。 if (n2){d=∞。 return false。} m=Blum(S)。 //S各點(diǎn)坐標(biāo)中位數(shù) S=S1+S2。//S1={x|x=m} S2={x|xm} CPair1(S1, d1)。 CPair1(S2, d2)。 p=max(S1)。 q=min(S2)。 d=min(d1, d2, qp)。 return ture。 } ? ? ? ?? ? ? ????????42/241nnOnTnOnT復(fù)雜性分析： T(n)=O(nlogn) 該算法可推廣到二維的情形中去。 81 二維空間的最接近點(diǎn)對問題 下面來考慮二維的情形。 選取一垂直線 l:x=m來作為分割直線。其中 m為 S中各點(diǎn) x坐標(biāo)的中位數(shù)。由此將 S分割為 S1和 S2。 遞歸地在 S1和 S2上找出其最小距離 d1和 d2，并設(shè)d=min{d1,d2}， S中的最接近點(diǎn)對或者是 d，或者是某個(gè) {p,q}，其中 p∈ P1且 q∈ P2 ，如圖所示。 能否在線性時(shí)間內(nèi)找到 p,q？ 考慮 P1中任意一點(diǎn) p，它若與 P2中的點(diǎn) q構(gòu)成最接近點(diǎn)對的候選者，則必有 distance(p， q)＜ d。滿足這個(gè)條件的 P2中的點(diǎn)一定落在一個(gè) d 2d的矩形 R中，如圖所示。 由 d的意義可知， P2中任何 2個(gè) S中的點(diǎn)的距離都不小于 d。由此可以推出矩形 R中最多只有 6個(gè) S中的點(diǎn)。 距離直線 l小于 d的所有點(diǎn) 包含 q的 d 2d矩形 R 82 R中至多包含 6個(gè) S中的點(diǎn)的證明 證明： 將矩形 R的長為 2d的邊 3等分，將它的長為 d的邊 2等分，由此導(dǎo)出 6個(gè) (d/2) (2d/3)的矩形（如圖 (a)所示 ）。 若矩形 R中有多于 6個(gè) S中的點(diǎn)，則 由鴿舍原理易知至少有一個(gè) (d/2) (2d/3)的小矩形中有 2個(gè)以上 S中的點(diǎn)。 設(shè) u， v是位于同一小矩形中的 2個(gè)點(diǎn)， 則 因此， distance(u,v)d。這與 d的意義相矛盾。 也就是說，矩形 R中最多有 6個(gè) S中的點(diǎn)。 極端情形：圖 (b)是矩形 R中恰有 6個(gè) S中的點(diǎn)的極端情形。 ? ? ? ?? ? ? ? ? ?? ?? ? ? ? 2222236253/22/ dddvyuyvxux??????83 說明 因此，在分治法的合并步驟中最多只需要檢查6 n/2=3n個(gè)候選者。 為了確切地知道要檢查哪 6個(gè)點(diǎn)，可以將 p和 P2中所有 S2的點(diǎn)投影到垂直線 l上。由于能與 p點(diǎn)一起構(gòu)成最接近點(diǎn)對候選者的 S2中點(diǎn)一定在矩形 R中，所以它們在直線 l上的投影點(diǎn)距 p在 l上投影點(diǎn)的距離小于 d。由上面的分析可知，這種投影點(diǎn)最多只有 6個(gè)。 因此，若將 P1和 P2中所有 S中點(diǎn)按其 y坐標(biāo)排好序，則對 P1中所有點(diǎn)，對排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對的候選者。對 P1中每一點(diǎn)最多只要檢查 P2中排好序的相繼 6個(gè)點(diǎn)。 84 算法描述及復(fù)雜性分析 算法描述： public static double CPair2(S) { n=|S|。 if (n 2) return 。 m=S中各點(diǎn) x間坐標(biāo)的中位數(shù) 。 構(gòu)造 S1和 S2； //S1={p∈ S|x(p)=m}, S2={p∈ S|x(p)m} d1=cpair2(S1)。 d2=cpair2(S2)。 dm=min(d1,d2)。 設(shè) P1是 S1中距垂直分割線 l的距離在 dm之內(nèi)的所有點(diǎn)組成的集合； P2是 S2中距分割線 l的距離在dm之內(nèi)所有點(diǎn)組成的集合； 將 P1和 P2中點(diǎn)依其 y坐標(biāo)值排序； 并設(shè) X和 Y是相應(yīng)的已排好序的點(diǎn)列； 通過掃描 X以及對于 X中每個(gè)點(diǎn)檢查 Y中與其距離在 dm之內(nèi)的所有點(diǎn) (最多 6個(gè) )可以完成合并； 當(dāng) X中的掃描指針逐次向上移動(dòng)時(shí)， Y中的掃描指針可在寬為 2dm的區(qū)間內(nèi)移動(dòng)； 設(shè) dl是按這種掃描方式找到的點(diǎn)對間的最小距離； d=min(dm,dl)。 return d。 } 85 算法描述及復(fù)雜性分析 復(fù)雜度分析： T(n)=O(nlogn) ? ? ? ?? ? ? ????????42/241nnOnTnOnT86 循環(huán)賽日程表 分治法不僅可以用來設(shè)計(jì)算法，而且再其他方面也有廣泛應(yīng)用：利用分治法設(shè)計(jì)電路、構(gòu)造數(shù)學(xué)證明等。 循環(huán)賽日程表問題，設(shè)有 n=2k個(gè)選手要進(jìn)行循環(huán)賽，設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： 每個(gè)選手必須與其他 n1個(gè)選手各賽一次； 每個(gè)選手一天只能賽一次； 循環(huán)賽一共進(jìn)行 n1天。 按此要求，可以將比賽日程表設(shè)計(jì)成 n行 n1列的表格， i行 j列表示第 i個(gè)選手在第 j天所遇到的選手。 87 循環(huán)賽日程表 基本思路：按分治策略，將所有的選手分為兩組，n個(gè)選手的比賽日程表就可以通過為 n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這 2個(gè)選手進(jìn)行比賽就可以了。 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7