混亂無序的數(shù)據(jù)，通過簡單的方法

《混亂無序的數(shù)據(jù)，通過簡單的方法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、約定：凡是用(*和*)括住的都不是發(fā)言內(nèi)容?。。o.1(*動畫結(jié)束*)大家好！我是南京市金陵中學(xué)的劉一鳴。今天我要和大家討論的就是：一類搜索問題的優(yōu)化思想——數(shù)據(jù)的有序化。No.2數(shù)據(jù)有序化的思想，就是將雜亂的數(shù)據(jù)，通過簡單的分類和排序，變成有序的數(shù)據(jù)，從而加快搜索的速度。(*點擊超級鏈接“為什么要進行數(shù)據(jù)有序化”，gotoNo.3*)No.3為什么要數(shù)據(jù)有序化呢？我們平時遇到的搜索問題，其數(shù)據(jù)往往有一大特點，那就是雜亂無章，毫無次序可言。(*點擊鼠標(biāo)，雜亂數(shù)據(jù)圖出現(xiàn)*)就是雜亂的數(shù)據(jù)。(*點擊鼠標(biāo)，有

2、序數(shù)據(jù)圖出現(xiàn)*)而這則是有序的數(shù)據(jù)。但是，在同一個題目中，應(yīng)用的算法相同，而數(shù)據(jù)的有序程度不同，程序的效率往往會有較大的差異。下面，我就給大家舉一個例子，“裝箱問題”。No.4請大家仔細(xì)看題目，注意，這里和一般的“裝箱問題”不同的地方就在于，題目是要求“放滿”集裝箱，也就是說，貨物體積總和必須恰巧等于集裝箱總體積。No.5這里提供了兩種算法的時間比較，我們不難發(fā)現(xiàn)，第2種算法在多數(shù)情況下運行得很好，而第1種算法則不很理想。No.6兩個程序效率不同的原因在哪里？(*點擊鼠標(biāo)，圖表出現(xiàn)*)主要的原因是，我們在

3、使用最優(yōu)性剪枝的時候，最希望的就是能較早地得到一個逼近最優(yōu)解的較優(yōu)解。(*點擊鼠標(biāo)，"最優(yōu)解"出現(xiàn)*)這里就是最優(yōu)解。(*點擊鼠標(biāo)，"不理想解"出現(xiàn)*)這里是不太理想的初始解，不排序而直接搜索，很可能會產(chǎn)生這種初始解。(*點擊鼠標(biāo)，"最理想解"出現(xiàn)*)這里是最理想的初始解，不排序而直接搜索和先排序再搜索都可能會產(chǎn)生這種初始解，不過后者的概率似乎略大。(*點擊鼠標(biāo)，"較理想解"出現(xiàn)*)這里是較為理想的初始解，先排序再搜索，很可能會產(chǎn)生這種初始解，這就是它的優(yōu)勢所在。No.7當(dāng)然，數(shù)據(jù)有序化的優(yōu)點并不僅僅是這

4、些。首先，對于大多數(shù)數(shù)據(jù)，它都有良好的優(yōu)化效果，不過也不乏專門針對它的數(shù)據(jù)；其次，它實現(xiàn)起來很簡單，對于剛才那個問題，在搜索前加上一個冒泡排序，只用加上幾行就可以了；再其次，使用這種方法不會與其它優(yōu)化方法形成沖突，甚至?xí)樗鼈儎?chuàng)造便利。所以，不難看出，數(shù)據(jù)有序化在實際應(yīng)用中是大有裨益的。No.8數(shù)據(jù)有序化大致可以分為兩種。第1種就是“預(yù)處理階段的數(shù)據(jù)有序化”(*點擊對應(yīng)的HyperLink,gotoNo.9*)No.9(*點擊鼠標(biāo)*)一般來說，我們解決一個問題，都是讀入數(shù)據(jù)以后直接進行數(shù)據(jù)的加工。(*點擊

5、鼠標(biāo)，直至"加工"出現(xiàn)*)預(yù)處理階段的數(shù)據(jù)有序化，就是在加工之前多一個數(shù)據(jù)的處理過程，把它們由雜亂的排成有序的。(*點擊鼠標(biāo)，直至第2個箭頭出現(xiàn)*)下面，我以IOI2000的"積木搭建"為例具體講解。No.10這道題目的題意大家應(yīng)該比較熟悉了，我就不再多講了。傳統(tǒng)的做法，是基于3維空間的算法，大家可以看看WangRenshen同學(xué)的解題報告，這種方法雖然容易想到，但是效率并不高，有些官方測試數(shù)據(jù)甚至?xí)瑫r?，F(xiàn)在，我們嘗試在預(yù)處理階段對數(shù)據(jù)進行有序化處理，來優(yōu)化搜索。No.11先對構(gòu)型的數(shù)據(jù)進行有序化處理。

6、(*點擊鼠標(biāo)*)將構(gòu)型的所有小方塊按照它們在空間中的順序排序并編號。(*點擊2次鼠標(biāo)*)用一個集合[1,v]表示構(gòu)型。(*點擊2次鼠標(biāo)*)這樣，就將原來的3維幾何體轉(zhuǎn)化成了一個1維的集合。No.12然后，我們對積木的數(shù)據(jù)進行有序化處理。(*點擊鼠標(biāo)*)枚舉所有能夠插入構(gòu)型的積木。(*點擊2次鼠標(biāo)*)用積木所包含的方塊的編號組成的集合分別表示每塊積木。(*點擊3次鼠標(biāo)*)這樣，一個積木可以放進構(gòu)型里，就可以用一個集合是否包含于另一個集合來表示。(*點擊2次鼠標(biāo)*)No.13下面，我們看看怎樣從一個構(gòu)型里挖去

7、一塊積木。這是一個構(gòu)型，(*點擊鼠標(biāo)*)我們用[1,10]表示?，F(xiàn)在，我們挖去一塊積木，(*點擊鼠標(biāo)，并將鼠標(biāo)指針指向淺綠色區(qū)域*)大家請看，淺綠色區(qū)域代表挖掉的一塊積木{3,6,7,9}，那么，剩下的構(gòu)型就是集合{1,2,4,5,8,10}。(*點擊2次鼠標(biāo)*)這個操作，數(shù)據(jù)有序化處理以后，我們可以用集合的減運算來表示。(*點擊鼠標(biāo)*)No.14我們現(xiàn)在對于剩下的那個構(gòu)型(*點擊3次鼠標(biāo)*)還想繼續(xù)放一塊積木(*點擊3次鼠標(biāo)*)就是這塊{4,5,7,8}。我們發(fā)現(xiàn)，{4,5,7,8}并不包含于{1,2,

8、4,5,8,10}，(*點擊鼠標(biāo)*)所以我們判定，(*點擊2次鼠標(biāo)*)積木不能放入構(gòu)型。No.15最后看看積木的沖突的判定(*點擊2次鼠標(biāo)*)不難看出，左右兩個積木單獨放，都能放進構(gòu)型(*點擊2次鼠標(biāo)*)但是，這兩個積木同時放，是存在沖突的，就是第7號方塊(*鼠標(biāo)指向7號方塊*)(*點擊鼠標(biāo)*)轉(zhuǎn)化為集合表示，我們會發(fā)現(xiàn)，沖突的積木的交集不為空集。No.16至此，預(yù)處理階段的數(shù)據(jù)有序化處理全部完畢，大家可以看一看有序化前后的比