深索優(yōu)化(生日蛋糕).ppt
《深索優(yōu)化(生日蛋糕).ppt》由會員分享,可在線閱讀,更多相關(guān)《深索優(yōu)化(生日蛋糕).ppt(15頁珍藏版)》請在裝配圖網(wǎng)上搜索。
生日蛋糕,7月17日是MrW的生日,ACM-THU為此要制作一個體積為n的m層生日每層都是一個圓柱體。設(shè)從下往上數(shù)第i(1im)層蛋糕是半徑為Ri,高度為hi的圓柱。當iRi+1且hihi+1。由于要在蛋糕上抹奶油,為盡可能節(jié)約經(jīng)費,我們希望蛋糕外表面(最下一層的下底面除外)的面積Q最小(令Q=S)。請編程對給出的n和m,找出蛋糕的制作方案(適當?shù)膔i和hi的值),使S最小。(除Q外,以上所有數(shù)據(jù)皆為正整數(shù)),輸入有兩行,第一行為n(n10000),表示待制作的蛋糕的體積為n;第二行為m(m20),表示蛋糕的層數(shù)為m。輸出僅一行,是一個正整數(shù)S(若無解則S=0)。樣例輸入1002樣例輸出68附:圓柱公式體積V=r2h側(cè)面積A=2rh底面積A=r2,解析法?,數(shù)據(jù)庫用(i,Ri,Hi,Vi,Si)表示第i層蛋糕的一個狀態(tài)。其中Ri,Hi分別為第i層蛋糕的半徑和高,Vi,Si分別表示做完第i層蛋糕后剩下的蛋糕體積和當前蛋糕的表面積??梢?,初始狀態(tài):(1,R1,H1,n-R1*R1*H1,R1*R1+2*R1*H1)目標狀態(tài):(m,Rm,Hm,0,Sm)于是,我們的目標是找到一條從初始狀態(tài)到任意目標狀態(tài)的路徑,并且Sm最小.擴展的規(guī)則(i,Ri,Hi,Vi,Si)(i+1,Ri+1,Hi+1,Vi+1,Si+1)滿足:(1)RiRi+1(2)HiHi+1(3)Vi+1=Vi-Ri+1*Ri+1*Hi+1(4)Si+1=Si+2*Ri+1*Hi+1,確定第一層蛋糕的大小根據(jù)上一層蛋糕的大小確定下一層蛋糕該怎么做看是否符合條件1)是否做到了m層2)是否最終體積為03)是否當前面積最小若上述條件成立,則保留當前最優(yōu)值,否則繼續(xù)做下一層蛋糕,若重做蛋糕,基本算法,Problem-Cake枚舉所有的初始狀態(tài)-第一層蛋糕的大小forR1mtosqrt(n)do/*假設(shè)H1=1,只做一層蛋糕*/forH1ndiv(R1*R1)downtomdobeginS1=2*R1*H1+R1*R1V1=n-R1*R1*H1Search(1,R1,H1,S1,V1)end;,確定第一層蛋糕的大小,Search(i,Ri,Hi,Si,Vi)對每層蛋糕進行搜索if(i=m)and(Vi=0)thenbegin計算面積s;ifsmin,則無論如何都找不到一個優(yōu)于min的解.因為知道余下的蛋糕體積,因此可以估算一下余下側(cè)面積,這樣我們可以就加入如下剪枝條件:if當前的表面積+余下的側(cè)面積當前最優(yōu)值thenexit設(shè)已經(jīng)做了i層蛋糕,則還需做m-i層,Si:為第i層蛋糕的側(cè)面積,FSi:余下的側(cè)面積,怎么求FSi?因為:2Vi=2Ri+1*Ri+1*Hi+1+.+2Rm*Rm*Hm=Ri+1*Si+1+.+Rm*SmRi+1*(Si+1+.+Sm)=Ri+1*FSi所以:FSi2Vi/Ri+1因此剪枝條件為:ifSi-1+2*Vi-1/Ri當前最優(yōu)值thenexit,可行性剪枝,如果剩下的蛋糕材料太少,不能保證做到m層,那么沒有必要繼續(xù)往下做了,設(shè),最m層半徑和高都為1,Rm=Hm=1第m-1層半徑和高都為2,Rm-1=Hm-1=2第i+1層半徑和高都為i,Ri=Hi=mi這樣,余下的m-i層的最小體積為,因此,剪枝條件為,ifVi當前最優(yōu)值thenexit;剪枝1ifViMINithenexit;剪枝2ifViMAXithenexit;剪枝3ifimthenforRi+1Ridowntom-i+1forHi+1min(Vidiv(Ri+1*Ri+1),Hi)downtom-i+1Si+1Si+2*Ri+1*Hi+1Vi+1Vi-Ri+1*Ri+1*Hi+1Search(i+1,Ri+1,Hi+1,Si+1,Vi+1)ElseifVi=0then更新最優(yōu)值Problem-Cake1.計算MINi和MAXiR,H;2.forR1mtosqrt(n)do/*假設(shè)H1=1,只做一層蛋糕*/3.forH1ndiv(R1*R1)downtomdo4.S1=2*R1*H1+R1*R15.V1=n-R1*R1*H16.Search(1,R1,H1,S1,V1)7.,小節(jié),可行性剪枝,剪枝2:ifVi當前最優(yōu)值thenexit,剪枝原則,正確、高效,深度搜索消耗時間每個節(jié)點操作系數(shù)節(jié)點個數(shù),優(yōu)化1)減少節(jié)點個數(shù)這就是剪枝優(yōu)化;2)減少每個節(jié)點的操作系數(shù)即程序操作量。,- 1.請仔細閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認領(lǐng)!既往收益都歸您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 優(yōu)化 生日蛋糕
鏈接地址:http://appdesigncorp.com/p-3418796.html