圓排列算法課件

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

2、特殊圓 正確的求圓排 列長(zhǎng)度的方法 1求圓心坐標(biāo)時(shí)，不能直接從倒數(shù)第二個(gè)圓 開(kāi)始，必須從第一個(gè)開(kāi)始，依次算過(guò)去 求當(dāng)前圓排列的長(zhǎng)度時(shí)，也是要從第一 個(gè)圓開(kāi)始,依次算過(guò)去 所以，每個(gè)圓結(jié)點(diǎn)必須記錄到該圓時(shí)的圓排 列，還得記錄它的分支 /求圓心坐標(biāo) void CircleNode:Center() double temp=0; for(int i=1;itemp) temp=valuex; xend=temp; /求圓排列的長(zhǎng)度 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í)，得不 償失猜測(cè)到老師的測(cè)試數(shù)據(jù)，就不處理 5解決鏡像問(wèn)題 我們知道根據(jù)鏡像原理,有一半的圓排列與另 一半剛好對(duì)稱,即:以某圓開(kāi)頭的圓排列,一定 會(huì)存在一個(gè)以該圓結(jié)尾的圓排列.那么怎么來(lái) 判斷當(dāng)前圓排列是否與前面已經(jīng)算過(guò)的某圓 排列對(duì)稱呢？ 例：設(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 由上面的例子可以看出： 最后一棵子樹(shù)可以直接砍去。 若第一子樹(shù)保留，則從第二棵子樹(shù)開(kāi)始，凡 是以該樹(shù)前面的子樹(shù)的根結(jié)點(diǎn)結(jié)尾的圓排列 均會(huì)與已存在的圓排列對(duì)稱。但是在本題中 我們必須到葉結(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ì)算圓排列長(zhǎng)度和計(jì)算圓心很坐標(biāo)的 時(shí)間，時(shí)間復(fù)