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