圓排列問題專題培訓(xùn)市公開課金獎(jiǎng)市賽課一等獎(jiǎng)?wù)n件

圓排列問題

04037石曼銀第1頁第1頁問題描述：給定n個(gè)大小不等圓C1,C2,…,Cn,現(xiàn)要將這n個(gè)圓排進(jìn)一個(gè)矩形框中，且要求各圓與矩形框底邊相切。圓排列問題要求從n個(gè)圓所有排列中找出有最小長(zhǎng)度圓排列。比如，當(dāng)n=3，且所給3個(gè)圓半徑分別為1，1，2時(shí)，這3個(gè)圓最小長(zhǎng)度圓排列如圖所表示。其最小長(zhǎng)度為2+4第2頁第2頁

第3頁第3頁

編程任務(wù)：

對(duì)于給定n個(gè)圓，設(shè)計(jì)一個(gè)優(yōu)先隊(duì)列式分支限界法，計(jì)算n個(gè)圓最佳排列方案，使其長(zhǎng)度達(dá)到最小第4頁第4頁思想歷程解題思緒1.腦海里出現(xiàn)三個(gè)圓和四個(gè)圓用貪心算法先求一個(gè)近似最優(yōu)解？第5頁第5頁

用貪心算法求一個(gè)最優(yōu)解？

從上面圓情況發(fā)覺,盡也許讓小圓靠近大圓,能夠節(jié)約圓排列長(zhǎng)度,能夠用貪心算法先求出一個(gè)近似最優(yōu)解.然后以此最優(yōu)解為剪枝條件，在葉結(jié)點(diǎn)處剪枝．程序以下:第6頁第6頁

//用貪心策略求最佳排列 doublebestL=0; intend=0; if(n%2==0){ bestL=r[0]; end=n-1; } else{ end=n-1; bestL=r[end]+a[end][0]; --end; } for(i=0;i<n/2;i++){ if(a[i][end]+a[end][i+1]>a[i][i+1]) bestL+=a[i][end]+a[end][i+1]; else bestL+=a[i][i+1]; --end; } bestL+=r[end+1];第7頁第7頁用貪心算法求一個(gè)最優(yōu)解？這種辦法求出圓排列長(zhǎng)度，在有些情況下是錯(cuò)誤．例：765812求出結(jié)果是:174.011而正確結(jié)果是:266.182由此,也想到了求圓排列長(zhǎng)度辦法有誤,書上是正確.第8頁第8頁

貪心求近似最優(yōu)解無效剪枝策略

２．腦海里出現(xiàn)多個(gè)圓貪心求近似最優(yōu)解無效剪枝策略由剛剛例子,明顯看出貪心無效,但是卻讓我想到一個(gè)剪枝策略.若在某個(gè)圓排列中有三個(gè)挨著圓是按降序或升序排列,則此圓排列一定不是最小長(zhǎng)度圓排列.先看特例:(26.9176)(266.182)(309.719)第9頁第9頁

貪心求近似最優(yōu)解無效剪枝策略求證：任何含有三個(gè)挨著按升序或降序排列圓圓排列一定不是最小長(zhǎng)度圓排列。證實(shí)：用反證法。假設(shè)結(jié)論不成立，則其否命題為：存在一個(gè)含有三個(gè)挨著按升序或降序排列圓圓排列是最小長(zhǎng)度圓排列。(轉(zhuǎn)不妨設(shè)文檔)第10頁第10頁剪枝策略效率分析剪枝策略效率分析：（看比較示例）假設(shè)每個(gè)圓半徑都不相同,則剪掉排列有:C(n,3)P(n-2)=(n(n-1)(n-2)/6)(n-2)!又在每個(gè)當(dāng)前圓處,都要進(jìn)行O(2n)次計(jì)算因此當(dāng)n較大時(shí),能夠節(jié)約諸多時(shí)間,即使到了離葉結(jié)點(diǎn)很近地方第11頁第11頁正確求圓排列長(zhǎng)度辦法

3.腦海里出現(xiàn)多個(gè)特殊圓正確求圓排列長(zhǎng)度辦法第12頁第12頁

正確求圓排列長(zhǎng)度辦法1．求圓心坐標(biāo)時(shí)，不能直接從倒數(shù)第二個(gè)圓開始，必須從第一個(gè)開始，依次算過去．２．求當(dāng)前圓排列長(zhǎng)度時(shí)，也是要從第一個(gè)圓開始,依次算過去．因此，每個(gè)圓結(jié)點(diǎn)必須統(tǒng)計(jì)到該圓時(shí)圓排列，還得統(tǒng)計(jì)它兒子們第13頁第13頁

正確求圓排列長(zhǎng)度辦法//求圓心坐標(biāo)voidCircleNode::Center(){ doubletemp=0; for(inti=1;i<end;i++){ doublevaluex=x[i]+2.0*sqrt(r[end]*r[i]); if(valuex>temp)temp=valuex; } x[end]=temp;}第14頁第14頁正確求圓排列長(zhǎng)度辦法//求圓排列長(zhǎng)度voidCircleNode::Compute(){ doublelow=0,high=0; for(inti=1;i<=end;i++){ if(x[i]-r[i]<low)low=x[i]-r[i]; if(x[i]+r[i]>high)high=x[i]+r[i]; } cleng=(high-low);}第15頁第15頁相同圓不必處理4．相同圓不必處理由于處理也是要付出代價(jià).假如有相同圓,我們所做工作只是不必執(zhí)行兩圓互換動(dòng)作.該動(dòng)作時(shí)間復(fù)雜度為O(1),即：假如有相同圓，我們只能節(jié)約O(1)時(shí)間，付出卻是每組圓排列中每個(gè)圓都要進(jìn)行一次比較．當(dāng)n較大，相同圓較小時(shí)，得不償失．猜想到老師測(cè)試數(shù)據(jù)，就不處理．第16頁第16頁處理鏡像問題5．處理鏡像問題我們知道依據(jù)鏡像原理,有二分之一圓排列與另二分之一剛好對(duì)稱,即:以某圓開頭圓排列,一定會(huì)存在一個(gè)以該圓結(jié)尾圓排列.那么怎么來判斷當(dāng)前圓排列是否與前面已經(jīng)算過某圓排列對(duì)稱呢？第17頁第17頁處理鏡像問題例：設(shè)有四個(gè)圓半徑分別為4,3,2,1,則所有圓排列為:432134212431143243123412241314234231324123411342421332142314132441233142214312434132312421341234第18頁第18頁處理鏡像問題由上面例子能夠看出：最后一棵子樹能夠直接砍去。若第一子樹保留，則從第二棵子樹開始，但凡以該樹前面子樹根結(jié)點(diǎn)結(jié)尾圓排列均會(huì)與已存在圓排列對(duì)稱。但是在本題中我們必須到葉結(jié)點(diǎn)才干做出判斷，因此不判斷，判斷要付出更多代價(jià)。第19頁第19頁主程序代碼６．主程序代碼for(i=1;i<n;i++){//第一層結(jié)點(diǎn)入隊(duì) E=newCircleNode;E->x=newdouble[n+1]; E->r=newdouble[n+1]; E->x[1]=0; E->end=1; for(intj=1;j<=n;j++) E->r[j]=r[j]; E->Swap(i); E->cleng=2*E->r[1]; H.push(E); } 第20頁第20頁主程序代碼for(inti=E->end+1;i<=n;i++){//中間結(jié)點(diǎn)兒子們?nèi)腙?duì) N=newCircleNode; N->r=newdouble[n+1]; N->x=newdouble[n+1]; for(intj=1;j<=n;j++){ N->x[j]=E->x[j]; N->r[j]=E->r[j]; } N->end=E->end+1; N->Swap(i); N->Center(); N->Compute(); if(confine(N))continue; H.push(N); }第21頁第21頁