【正文】 :S中的 n個點(diǎn)退化為 x軸上的 n個實(shí)數(shù) x1,x2,…,x n。最接近點(diǎn)對為其中相差最小的 2個實(shí)數(shù)。 分治算法舉例 7：最接近點(diǎn)對問題 —— 《算法分析與設(shè)計(jì)》 75 優(yōu)化最接近點(diǎn)對問題算法 問題： 無法應(yīng)用于二維點(diǎn)對。 解決方法： 對所有點(diǎn)進(jìn)行排序，需要 O(n㏒ n)。再掃描一遍即可以得出最接近點(diǎn)對。 證明得知，該問題的時間下界為 Ω(n ㏒ n) —— 《算法分析與設(shè)計(jì)》 76 優(yōu)化最接近點(diǎn)對問題算法 ?假設(shè)用 x軸上某個點(diǎn) m將 S劃分為 2個子集 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}，或是某個 {p3,q3}，其中 p3∈S 1且 q3∈S 2。 ?思考：能否在線性時間內(nèi)找到 p3,q3？ —— 《算法分析與設(shè)計(jì)》 77 ?如果 S的最接近點(diǎn)對是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者 與 m的距離不超過 d，即 p3∈(m d,m]， q3∈(m,m+d] 。 ?由于在 S1中，每個長度為 d的半閉區(qū)間至多包含一個點(diǎn)（否則 必有兩點(diǎn)距離小于 d），并且 m是 S1和 S2的分割點(diǎn)，因此 (md, m]中至多包含 S中的一個點(diǎn)。由圖可以看出，如果 (md,m]中 有 S中的點(diǎn)，則此點(diǎn)就是 S1中最大點(diǎn)。 ?因此，用線性時間就能找到區(qū)間 (md,m]和 (m,m+d]中所有點(diǎn)， 即 p3和 q3。從而用線性時間就可以將 S1的解和 S2的解合并成 為 S的解。 —— 《算法分析與設(shè)計(jì)》 78 一維點(diǎn)集 S的最接近點(diǎn)對的算法 double cpair1(S) { //排序 , Ω(n ㏒ n) n = |S|。 if (n2) return ≦。 m=S中各點(diǎn)坐標(biāo)的中位數(shù)； //線性時間 構(gòu)造 S1和 S2。 //線性時間 d1=cpair1(S1)。 //計(jì)算左側(cè)的最接近距離 d2=cpair1(S2)。 //計(jì)算右側(cè)的最接近距離 p=max(S1)。 // 左側(cè)最大值 ,線性時間 q=min(S2)。 //右側(cè)最小值 ,線性時間 d=min(d1,d2,qp)。 //最接近距離 ,常量時間 return d。 } —— 《算法分析與設(shè)計(jì)》 79 (2) 二維情形 ?選取一垂直線 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，或者是 某個 {p,q}，其中 p∈P 1且 q∈P 2。 ?能否在線性時間內(nèi)找到 p,q？ —— 《算法分析與設(shè)計(jì)》 80 考慮 P1中任意一點(diǎn) p，若與 P2中的點(diǎn) q構(gòu)成最接近點(diǎn)對的候選者，必有 distance(p， q)＜ d。滿足這個條件的 P2中的點(diǎn)一定落在一個 d 2d的矩形 R中，由 d的意義可知， P2中任何 2個 S中的點(diǎn)的距離都不小于 d。由此可以推 出矩形 R中最多只有 6個 S中的點(diǎn)，因此在分治算法的合并步驟中最多只需要 檢查 6 n/2=3n個候選者。 證明 :將矩形 R的長為 2d的邊 3等分，將它的長為 d的邊 2等分，由此導(dǎo)出 6 個 (d/2) (2d/3)的矩形。若矩形 R中有多于 6個 S中的點(diǎn)，則由鴿舍原理 易知至少有一個 (d/2) (2d/3)的小矩形中有 2個以上 S中的點(diǎn)。設(shè) u， v 是位于同一小矩形中的 2個點(diǎn)，則 distance(u,v)d。這與 d的意義矛盾。 —— 《算法分析與設(shè)計(jì)》 81 為了確切地知道要檢查哪 6個點(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個。因此，若將 P1和 P2中所有 S中點(diǎn) 按其 y坐標(biāo)排好序，則對 P1中所有點(diǎn)，對 排好序的點(diǎn)列作一次掃描，就可以找出 所有最接近點(diǎn)對的候選者。對 P1中每一 點(diǎn)最多只要檢查 P2中排好序的相繼 6個點(diǎn) —— 《算法分析與設(shè)計(jì)》 82 double cpair2(S) { n=|S|。 if (n 2) return 。 1. m=S中各點(diǎn) x間坐標(biāo)的中位數(shù) 。 //構(gòu)造 S1和 S2； S1={p∈S|x(p)=m}, S2={p∈S|x(p)m} 2. d1=cpair2(S1)。 d2=cpair2(S2)。 3. dm=min(d1,d2)。 4. 設(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)列； 5. 通過掃描 X以及對于 X中每個點(diǎn)檢查 Y中與其距離在 dm之內(nèi)的所有點(diǎn) (最多 6個 )可以完成合并；當(dāng) X中的掃描指針逐次向上移動時， Y中的掃描指針可在寬為 2dm的區(qū)間內(nèi)移動；設(shè) dl是按這種掃描方式找到的點(diǎn)對間的最小距離； 6. d=min(dm,dl)。 —— 《算法分析與設(shè)計(jì)》 83 練習(xí)一：郵局選址問題 問題描述： 在一個按照東西和南北方向劃分成規(guī)整街區(qū)的城市里， n個居民點(diǎn)散亂地分布在不同的街區(qū)中。用 x坐標(biāo)表示東西向，用 y坐標(biāo)表示南北向。各居民點(diǎn)的位臵可以由坐標(biāo) (x,y)表示。 要求： 為建郵 局選址，使得 n個居民點(diǎn)到郵局之距離的總和最小 提示： 帶權(quán)中位數(shù)（分治算法） —— 《算法分析與設(shè)計(jì)》 靜夜四無鄰，荒居舊業(yè)貧。 , March 17, 2023 雨中黃葉樹，燈下白頭人。 16:13:3616:13:3616:133/17/2023 4:13:36 PM 1以我獨(dú)沈久，愧君相見頻。 :13:3616:13Mar2317Mar23 1故人江海別，幾度隔山川。 16:13:3616:13:3616:13Friday, March 17, 2023 1乍見翻疑夢，相悲各問年。 :13:3616:13:36March 17, 2023 1他鄉(xiāng)生白發(fā)，舊國見青山。 2023年 3月 17日星期五 下午 4時 13分 36秒 16:13: 1比不了得就不比，得不到的就不要。 2023年 3月 下午 4時 13分 :13March 17, 2023 1行動出成果，工作出財(cái)富。 2023年 3月 17日星期五 4時 13分 36秒 16:13:3617 March 2023 1做前，能夠環(huán)視四周；做時，你只能或者最好沿著以腳為起點(diǎn)的射線向前。 下午 4時 13分 36秒 下午 4時 13分 16:13: 沒有失敗，只有暫時停止成功！。 , March 17, 2023 很多事情努力了未必有結(jié)果，但是不努力卻什么改變也沒有。 16:13:3616:13:3616:133/17/2023 4:13:36 PM 1成功就是日復(fù)一日那一點(diǎn)點(diǎn)小小努力的積累。 :13:3616:13Mar2317Mar23 1世間成事，不求其絕對圓滿，留一份不足，可得無限完美。 16:13:3616:13:3616:13Friday, March 17, 2023 1不知香積寺，數(shù)里入云峰。 :13:3616:13:36March 17, 2023 1意志堅(jiān)強(qiáng)的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 3月 17日星期五 下午 4時 13分 36秒 16:13: 1楚塞三湘接，荊門九派通。 2023年 3月 下午 4時 13分 :13March 17, 2023 1少年十五二十時，步行奪得胡馬騎。 2023年 3月 17日星期五 4時 13分 36秒 16:13:3617 March 2023 1空山新雨后，天氣晚來秋。 下午 4時 13分 36秒 下午 4時 13分 16:13: 楊柳散和風(fēng)，青山澹吾慮。 , March 17, 2023 閱讀一切好書如同和過去最杰出的人談話。 16:13:3616:13:3616:133/17/2023 4:13:36 PM 1越是沒有本領(lǐng)的就越加自命不凡。 :13:3616:13Mar2317Mar23 1越是無能的人，越喜歡挑剔別人的錯兒。 16:13:3616:13:3616:13Friday, March 17, 2023 1知人者智，自知者明。勝人者有力，自勝者強(qiáng)。 :13:3616:13:36March 17, 2023 1意志堅(jiān)強(qiáng)的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 3月 17日星期五 下午 4時 13分 36秒 16:13: 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。 2023年 3月 下午 4時 13分 :13March 17, 2023 1業(yè)余生活要有意義，不要越軌。 2023年 3月 17日星期五 4時 13分 36秒 16:13:3617 March 2023 1一個人即使已登上頂峰，也仍要自強(qiáng)不息。 下午 4時 13分 36秒 下午 4時 13分 16:13: MOMODA POWERPOINT Lorem ipsum dolor sit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis amet, consectetur adipiscing elit. Fusce id urna blanditut cursus. 感謝您的下載觀看 專家告訴