集訓(xùn)隊論文1999-2009 集訓(xùn)隊2003論 劉一鳴 劉一鳴

1、一類搜索的優(yōu)化思想 數(shù)據(jù)有序化,南京市金陵中學(xué) 劉一鳴,數(shù)據(jù)有序化,為什么要進行數(shù)據(jù)有序化 數(shù)據(jù)有序化的實現(xiàn) 兩種實現(xiàn)方法的比較,數(shù)據(jù)有序化的思想，就是將雜亂的數(shù)據(jù)，通過簡單的分類和排序，變成有序的數(shù)據(jù)，從而加快搜索的速度。,為什么要進行數(shù)據(jù)有序化,例1 裝箱問題,題目大意： 現(xiàn)有一個體積為V的集裝箱和N種貨物，每一種貨物都有固定的體積，數(shù)量無限。你的任務(wù)是：寫一個程序，求出最少用多少個貨物，就能放滿集裝箱。 數(shù)據(jù)規(guī)模：V貨V109,運行時間的對比,測試方法：隨機生成20個數(shù)據(jù)，測試運行時間并求平均值。,程序效率不同的原因,不理想的初始解,最理想的初始解,最優(yōu)解,比較理想的初始解,數(shù)據(jù)有序化的

2、益處,對于大多數(shù)的數(shù)據(jù)，都有良好的優(yōu)化效果； 簡便易行； 和其他類型的優(yōu)化方法一般都不沖突。,數(shù)據(jù)有序化的實現(xiàn),預(yù)處理階段的數(shù)據(jù)有序化 實時處理階段的數(shù)據(jù)有序化,預(yù)處理階段的數(shù)據(jù)有序化,加工,例2 積木搭建,題目大意：給定12種積木和一個體積小于50的構(gòu)型，求最少使用多少個積木可以將這個構(gòu)型搭建起來,目標構(gòu)型示例,積木示例,第1步數(shù)據(jù)有序化,集合1,10,第2步數(shù)據(jù)有序化,1,2,3,4,5,6,7,9,10,8,積木3,6,7,9,1,2,3,4,5,6,7,9,10,8,1,10,1,2,4,5,8,10,1,10-3,6,7,9 = 1,2,4,5,8,10,從構(gòu)型中挖去一個積木,試圖再

3、放一塊積木,4,5,7,8,1,2,4,5,8,10,積木不能放入構(gòu)型,積木的沖突,1,2,3,4,5,6,7,10,8,9,數(shù)據(jù)有序化前后數(shù)學(xué)模型的對比,數(shù)據(jù)有序化后，數(shù)學(xué)模型得到了精簡,實時處理階段的數(shù)據(jù)有序化,加工,保存,舍棄,傳統(tǒng)表示方法,S,保存,舍棄,最小表示法,S,Smin,保存,舍棄,例3 N皇后問題-2,題目大意：假定通過翻轉(zhuǎn)、旋轉(zhuǎn)得到的狀態(tài)與原狀態(tài)屬于同構(gòu)狀態(tài)，求所有不同構(gòu)的n皇后狀態(tài)總數(shù)。,狀態(tài)表示方法,由于一行中只能有一個皇后，所以用一個n元組(a1,a2,a3,an)表示當前的狀態(tài)，其中ai表示第i列的皇后所在的行。,(3,1,4,2,5),翻轉(zhuǎn)、旋轉(zhuǎn)的具體過程(1)

4、,以鉛垂線為軸的翻轉(zhuǎn)：,（a1,a2,a3,a4,a5）,（a5,a4,a3,a2,a1）,90度、180度、270度的旋轉(zhuǎn) （a1,a2,a3,a4,a5）（6-b1,6-b2,6-b3,6-b4,6-b5） （6-a5,6-a4,6-a3,6-a2,6-a1） （6-b5,6-b4,6-b3,6-b2,6-b1）,以水平線為軸的翻轉(zhuǎn)： （a1,a2,a3,a4,a5）（6-a1,6-a2,6-a3,6-a4,6-a5）,以對角線為軸的翻轉(zhuǎn)： （a1,a2,a3,a4,a5）（b1,b2,b3,b4,b5） （b5,b4,b3,b2,b1）,翻轉(zhuǎn)、旋轉(zhuǎn)的具體過程(2),應(yīng)用數(shù)據(jù)有序化,S,Smin,枚舉,回溯,新的剪枝條件,a1a5 a16-a1 a1b1 a1b5 a16-b1 a16-a5 a16-b5,空間復(fù)雜度的降低,S,Smin,枚舉,回溯,應(yīng)