圓排列算法課件

1、圓排列問題 問題描述： 給定n個(gè)大小不等的圓 C1,C2,Cn,現(xiàn)要將這n個(gè) 圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框的底邊 相切。圓排列問題要求從n個(gè)圓的所有排列中找出 有最小長度的圓排列。 例如，當(dāng)n=3，且所給的3 個(gè)圓的半徑分別為1，1， 2時(shí)，這3個(gè)圓的最小長度的圓排列如圖所示。其最 小長度為2+42 算法任務(wù)：算法任務(wù)： 對于給定的n個(gè)圓，設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支 限界法，計(jì)算n個(gè)圓的最佳排列方案，使其長 度達(dá)到最小 思想歷程 解題思路 1.實(shí)例 腦海里出現(xiàn)多個(gè)圓，若在某個(gè)圓排列中 有三個(gè)挨著的圓是按降序或升序排列,則此圓 排列一定不是最小長度的圓排列. 可能的解： 3.腦海里出現(xiàn)多個(gè)

2、特殊圓 正確的求圓排 列長度的方法 1求圓心坐標(biāo)時(shí)，不能直接從倒數(shù)第二個(gè)圓 開始，必須從第一個(gè)開始，依次算過去 求當(dāng)前圓排列的長度時(shí)，也是要從第一 個(gè)圓開始,依次算過去 所以，每個(gè)圓結(jié)點(diǎn)必須記錄到該圓時(shí)的圓排 列，還得記錄它的分支 /求圓心坐標(biāo) void CircleNode:Center() double temp=0; for(int i=1;itemp) temp=valuex; xend=temp; /求圓排列的長度 void CircleNode:Compute() double low=0,high=0; for(int i=1;i=end;i+) if(xi-rihigh) hi

3、gh=xi+ri; cleng=(high-low); 4相同圓不必處理 因?yàn)樘幚硪彩且冻龃鷥r(jià)的. 如果有相同圓,我們所做的工作只是不必執(zhí)行 兩圓交換的動(dòng)作.該動(dòng)作的時(shí)間復(fù)雜度為O(1), 即：如果有相同圓，我們只能節(jié)省O(1)的時(shí) 間，付出的卻是每組圓排列中每個(gè)圓都要進(jìn) 行一次比較當(dāng)n較大，相同圓較小時(shí)，得不 償失猜測到老師的測試數(shù)據(jù)，就不處理 5解決鏡像問題 我們知道根據(jù)鏡像原理,有一半的圓排列與另 一半剛好對稱,即:以某圓開頭的圓排列,一定 會(huì)存在一個(gè)以該圓結(jié)尾的圓排列.那么怎么來 判斷當(dāng)前圓排列是否與前面已經(jīng)算過的某圓 排列對稱呢？ 例：設(shè)有四個(gè)圓的半徑分別為4,3,2,1,則所有

4、的圓排列為: 4321 3421 2431 1432 4312 3412 2413 1423 4231 3241 2341 1342 4213 3214 2314 1324 4123 3142 2143 1243 4132 3124 2134 1234 由上面的例子可以看出： 最后一棵子樹可以直接砍去。 若第一子樹保留，則從第二棵子樹開始，凡 是以該樹前面的子樹的根結(jié)點(diǎn)結(jié)尾的圓排列 均會(huì)與已存在的圓排列對稱。但是在本題中 我們必須到葉結(jié)點(diǎn)才能做出判斷，所以不判 斷，判斷要付出更多代價(jià)。 主程序代碼 void Circle:Backtrack ( int t ) if ( t n ) Compute ( ) ; else for ( int j = t ; j =n ; j+ ) Swap ( r t , r j ) ; cout r t r j endl ; float centerx=Center ( t ) ; if ( centerx + r t + r1 min ) x t = centerx ; Backtrack ( t + 1 ) ; Swap ( r t , r j ) ; 復(fù)雜度分析 不考慮計(jì)算圓排列長度和計(jì)算圓心很坐標(biāo)的 時(shí)間，時(shí)間復(fù)