NOI導(dǎo)刊 搜索順序的選取與剪枝策略PPT課件

1、.1，搜索的剪枝策略，搜索對象的選擇和搜索順序，朱，長沙市雅麗中學(xué)，2，條件1: V=n h=m層形狀：每層是一個圓柱體。條件2:從下到上設(shè)置數(shù)字i(1Ri 1和HiHi 1)。條件3:表面積Q最小，使Q=S問題：給定n和m，找出蛋糕制作方案(適當(dāng)?shù)膔i和Hi值)，使s最小。(除q外的所有上述數(shù)據(jù)均為正整數(shù))輸入n (n=10000)，m(MRI 1(2)hi 1(3)VI 1=VI-ri 1 * ri 1 * hi 1(4)si 1=si 2 * ri 1 * hi 1，5、確定第一層蛋糕的大?。桓鶕?jù)前一層蛋糕的大小決定如何做下一層蛋糕，看是否符合條件1)是否m層2)最終體積是否為0.3)當(dāng)

2、前面積是否最?。蝗绻麧M足上述條件，保持當(dāng)前最優(yōu)值；否則，繼續(xù)做下一層蛋糕；如果蛋糕又做了，基本算法，6，搜索(I，Ri，Hi，Si，VI)搜索蛋糕的每一層如果(i=m)和(Vi=0 ),則更新ri 1ri-1的最優(yōu)值else至Hi 1hi-1至ISi 1si 2 * ri 1 * hi 1 Vi 1vi-ri 1 * ri 1 * hi 1搜索(I 1，ri 1，hi 1，si 1，Vi 1)問題-蛋糕列舉所有初始狀態(tài)-第一層蛋糕的大小r1m至sqrt (n) do/。只做一層蛋糕*/從R1 * R1到MDOS1=2 * R1 * h1 R1 * R1 v1=n-R1 * R1 * h1搜索(

3、1，R1，h1，S1，v1)。7，優(yōu)化？(1)因?yàn)槲覀冎朗Ｓ嗟牡案怏w積，我們可以估計(jì)剩余的橫向面積，所以我們可以添加以下修剪條件：如果當(dāng)前表面積和剩余的橫向面積當(dāng)前最優(yōu)值然后退出。如果I層蛋糕已經(jīng)做好了，那么m-i層，Si :橫向面積為I層蛋糕，F(xiàn)Si:剩余橫向面積，我們?nèi)绾握业紽Si？因?yàn)椋?2vi=2ri 1 * ri 1 * hi 1.2rm * rm * hm=ri 1 * si！rm * sm ri1 * (si 1 .sm)=Ri 1 * FSi so : FSi2Vi/Ri 1 so修剪條件為：如果Si-1 2 * Vi-1/Ri當(dāng)前最佳值，則退出。8，優(yōu)化？(2)如果剩余的餅

4、料太少，無法保證達(dá)到M層，則沒有必要繼續(xù)這樣做。假設(shè)M層的半徑和高度都是1，Rm=Hm=1，m-1層的半徑和高度都是2，RM-1=HM-1=2.i 1層的半徑和高度都是I，RI=HI=MI。因此，剩余m1層的最小體積是，因此，修剪條件是，當(dāng)前的最佳值如果v1，則退出；修剪1如果Vi MINi，則退出；修剪2 ifvi maxi然后退出；修剪3如果ITIME 3時間n(時間i表示第一個處理器的處理時間)，則可以設(shè)置閾值：如果當(dāng)前處理器的處理時間=當(dāng)前最佳解決方案，或者剩余處理機(jī)器的數(shù)量是從上一個處理器的處理時間開始的剩余操作所需的處理時間，則執(zhí)行回溯。因?yàn)樵谥暗募s束下，沒有解決方案。因此，從以

5、上比較來看，第二種方法明顯優(yōu)于第一種方法。下面是對第二種方法的進(jìn)一步討論。對于任務(wù)一，時間1的上限可以通過貪婪獲得。然后，也可以使用時間1的下限UP(總操作時間/加工機(jī)器數(shù)量)。(向上表示大于或等于小數(shù)的最小整數(shù))。搜索從上限開始。在找到解決方案后，如果它等于下限，則可以停止搜索。對于任務(wù)2，可以采用可變深度的下限。下限是上限(總操作時間/有限時間)，即至少需要加工機(jī)器的數(shù)量。并將時間1的上限設(shè)為t。有2N塊木頭。每塊木頭都標(biāo)有自然數(shù)1到n中的一個，每個數(shù)字都會出現(xiàn)在兩塊木頭上。將這些木塊排成一行的要求是，其他木塊應(yīng)在標(biāo)記為1的兩個木塊之間隔開。例如，如果N=3，以下是可行的安排：3，1，2，

6、1，3，2。編程，對于給定的N(n=40)，找到一個可行的安排。28，操作效果比較，29，選擇搜索順序的基本原則，1，首先搜索具有小值范圍的搜索元素。2.一個搜索元素的確定對其他搜索元素的取值范圍的影響稱為限制力。首先搜索限制較大的搜索元素。3.搜索對解有較大影響的元素可以使評價函數(shù)更精確，剪枝更有效。顧梅運(yùn)算符由小寫字母A到M組成，分別對應(yīng)于現(xiàn)代運(yùn)算符0、1、2、3、4、5、6、7、8、9、*、=之一。給出了一組由顧梅算子表示的方程。如果存在滿足方程的對應(yīng)關(guān)系，則輸出所有顧梅算子與可確定的現(xiàn)代算子之間的對應(yīng)關(guān)系。否則，輸出“noway”。在上面的例子中，可能的現(xiàn)代表達(dá)式是6*2=12，2=1

7、 1、6*4=24，4=2 2、6*8=48，8=4 4?？梢钥闯?，只有A對應(yīng)于6，B對應(yīng)于*，D對應(yīng)于=，F(xiàn)對應(yīng)于并且應(yīng)該被輸出。31，三個最特殊的元素，本主題中有三個最特殊的運(yùn)算符：=， * ，它們必須滿足以下條件：1，這三個運(yùn)算符不能出現(xiàn)在方程的最左端和最右端。2.這三個運(yùn)算符不能彼此相鄰。 3 =是最特殊的運(yùn)算符，必須出現(xiàn)在任何方程中，并且只能出現(xiàn)一次。32、確定搜索順序，考慮取值范圍，取值范圍“=”、“、“*”是所有運(yùn)算符中最小的；從約束力的角度來看，“=”和“，*”的約束力無疑比“0”到“9”的十位數(shù)更強(qiáng)。從剪枝的角度來看，這三個運(yùn)算符對解決方案的影響最大，因此“=”、“”、“*”

8、應(yīng)該放在搜索序列的前面。對于這三個運(yùn)算符，因?yàn)椤?”的限制更大，而且值的范圍更小，所以應(yīng)該首先搜索它。最佳搜索順序如下：搜索=，然后是， * ，最后是10個數(shù)字。在一些問題中，搜索元素的約束力和值范圍在搜索過程中變化不大，或者變化對搜索效率影響不大。如果要動態(tài)判斷元素的取值范圍和限制，會花費(fèi)很多，優(yōu)化效果也不好。在這種情況下，只需要在搜索開始之前確定搜索順序，而無需在搜索過程中更改搜索順序。34、動態(tài)調(diào)整搜索順序，有時在搜索過程中，元素的取值范圍和限制會發(fā)生很大變化，而這些變化會直接影響搜索樹的大小，因此有必要動態(tài)調(diào)整搜索順序，即啟發(fā)式搜索。啟發(fā)式搜索繼承了回溯法的優(yōu)點(diǎn)，如空間小、編程簡單。啟

9、發(fā)式搜索的最大優(yōu)點(diǎn)是可以在短時間內(nèi)找到一組可行解，最適合解決一類只需要找到一組可行解的搜索問題。(IOI94)，主題的簡要說明：用數(shù)字填充一個5*5的正方形矩陣，這樣沿著行、列和兩條對角線的5個數(shù)字可以形成一個5位數(shù)的質(zhì)數(shù)(5位數(shù)質(zhì)數(shù)的第一個數(shù)字不是0)。所有質(zhì)數(shù)的和必須等于一個常數(shù)。這個常數(shù)和方陣左上角的數(shù)字是預(yù)先給定的。如果有多個解決方案，則必須全部獲得。輸入11 1輸出，36，搜索元素的屬性，1，最后一行和最后一列：只能填寫1，3，7，9。2.兩條對角線：與方陣中的所有五個質(zhì)數(shù)相關(guān)。3.其他行和列：特殊性取決于行和列中已經(jīng)確定的網(wǎng)格數(shù)量。37、根據(jù)元素的取值范圍和約束條件來確定搜索順序，

10、1、最后一行和最后一列是搜索元素的最小取值范圍，它們對所有其他元素都有一定的約束，所以應(yīng)該放在搜索序列的前面。2.兩條對角線也會影響所有其他搜索元素，并且剩余網(wǎng)格中的限制力最大，因此搜索也應(yīng)該優(yōu)先。3.剩余的行和列根據(jù)其值范圍的大小確定搜索順序。有五個隊(duì)參加籃球錦標(biāo)賽。比賽采用單一循環(huán)，每兩個隊(duì)打一場。了解每支球隊(duì)的最終贏、輸、總得分和總失分，列出所有得分的比賽，詢問可能的比賽。(每場比賽各隊(duì)得分記錄表)。很難確定搜索元素之間的約束力的大小(即每個匹配的分?jǐn)?shù))。在本主題中，元素的值范圍被定義為團(tuán)隊(duì)在某個字段中的分?jǐn)?shù)可以有幾個可能的值。由于分值范圍在搜索中會有很大的變化，這種變化將直接影響搜索樹的大小，所以改變搜索順序的主要依據(jù)是各個分值范圍的大小。首先，我們需要做