網(wǎng)上找的一些算法搜索lunwen

1、論程序設(shè)計中搜索的優(yōu)化蘇展（金陵中學(xué)初一 6 班）【關(guān)鍵字】程序設(shè)計、搜索、時間與空間【摘要】本文作者利用搜索的一般知識結(jié)合自身經(jīng)驗，介紹了程序設(shè)計中搜索及其優(yōu)化的一般方法。開始介紹 搜索的方法及其存在的問題，然后重點介紹了作者歸納的一些解決方法，通過時間和空間兩部分加以分類。同時，在附錄里介紹了 PASCAL 對內(nèi)存空間的分配。一、 引言在一時找不出解決問題的更好途徑（指從數(shù)學(xué)上找到求解公式或規(guī)則）時，可以對問題的狀態(tài)進(jìn)行逐一的查找，直到找到目標(biāo)狀態(tài)或到達(dá)目標(biāo)狀態(tài)的過程。這種方法叫做“搜索”或“窮舉”。一般情況下，“搜索”是對于問題的狀態(tài)進(jìn)行基于隊列的廣度優(yōu)先的搜尋。由于它是對問題的所有狀態(tài)

2、進(jìn)行搜尋，所以它不易做錯，但這也帶來了一個問題：對運算的空間與時間帶來了很大的壓力。由于搜索要對問題的大部分甚至所有狀態(tài)進(jìn)行搜尋，要它們，必然需要極多的內(nèi)存空間。就拿“魔板問題”來說吧，它一共有 40320 種狀態(tài)，下，要全部搜索完，恐怕小小的 64K 數(shù)據(jù)段空間是遠(yuǎn)遠(yuǎn)不夠的。情況再則，搜索每一種狀態(tài)都需要時間，還說“魔板問題”，在情況下，即便一毫秒搜索兩種狀態(tài)，也要三分鐘多。這種等待往往讓人難以忍受，在大部分競賽中，這是拿不到分的。由于上述考慮，的問題。在程序中需要對搜索進(jìn)行優(yōu)化，以解決時間與空間不足二、 利用隊列進(jìn)行搜索的一般方法利用隊列進(jìn)行搜索一般是解決求一種狀態(tài)通過幾種規(guī)定的操作以最少

3、次數(shù)變換到另一種狀態(tài)的方法，本文也是以索用隊列的數(shù)據(jù)結(jié)構(gòu)如下：利用隊列進(jìn)行的搜索的優(yōu)化為主。搜隊列頭指針隊列尾指針由于找到目標(biāo)值后，還需根據(jù) PRE 值回溯得到由初始狀態(tài)到達(dá)目標(biāo)值的最短序列，所以還要準(zhǔn)備一個輔助棧，其元素類型與 DATA 或 OP 一樣。下面是利用隊列搜索的一般步驟（設(shè)共有 N 種變換操作）：DATA（狀態(tài)）初始狀態(tài)初始狀態(tài)經(jīng) A操作的結(jié)果初始狀態(tài)經(jīng) B操作的結(jié)果初始狀態(tài)經(jīng)兩次A 操作的結(jié)果OP（由何種操作變換而來）-ABAPRE（由何種狀態(tài)變換而來）0112初始狀態(tài)入隊。I:=1。對隊列首部的狀態(tài)進(jìn)行第 I 種操作，結(jié)果。檢查結(jié)果是否出現(xiàn)過，若未出現(xiàn)過，則此結(jié)果進(jìn)隊，DAT

4、A 記下此結(jié)果，OP 記下 I 的值，PRE 記下變換至此結(jié)果的元素（即當(dāng)前隊列首部元素）的位置（下標(biāo)）。若結(jié)果即為所求，至步驟若 I=N，隊列第一個元素出隊，至步驟；否則，I:=I+1,至步驟。 J:=當(dāng)前元素下標(biāo)隊列中第 J 個元素的 OP 或 DATA 進(jìn)輔助棧若 J1，J:=隊列中第 J 個元素的 PRE，至步驟。全部彈棧，按出棧順序輸出。不過，在搜索過程中，“出隊”的元素必須一直保留，不能刪除（最后回溯時要用到）。三、 空間的解決方案判重“判重”即指判斷一個新搜索到的狀態(tài)以前是否出現(xiàn)過，如出現(xiàn)過就去掉它。判重一般用于用隊列進(jìn)行搜索，而且用隊列進(jìn)行搜索的程序幾乎全都用到這種方法。雖然判

5、重需要增加時間，而且一次最多只能去掉一種狀態(tài)，但這種狀態(tài)所產(chǎn)生的眾多無用狀態(tài)所浪費的時間與空間將遠(yuǎn)遠(yuǎn)大于判重本身所需要的時間。利用“免費”資源這里的“免費”資源指的是那些不占用空間卻可以表示信息的。數(shù)組下標(biāo)就是一種完全不占空間的。往往可以用數(shù)組下標(biāo)來表示所有的狀態(tài)，這一狀態(tài)的信息就直接在下標(biāo)所對應(yīng)的數(shù)組元素里，方可空間。另外，內(nèi)存地址也是一種免費資源。不過，使用時須可能會產(chǎn)生意想不到的嚴(yán)重情況。重復(fù)利用，萬一動了系統(tǒng)的內(nèi)存，舉一個不恰當(dāng)?shù)睦樱涸跊]有通自來水的時候，大家用水桶從井里打水；通上了自來水，水桶不要了，可改成桶（盡管不太合適）。同理，有時候，變量重復(fù)利用，可節(jié)省不少空間。比如利用隊列

6、搜索，輔助棧會占去不少空間。如果不用輔助棧，將 PRE 再次利用，使它變化方向，反過來指向所變換成的元素，就等于進(jìn)行了回溯，也就不需輔助棧，節(jié)省了空間。但重復(fù)利用變量，往往會降低程序的可讀性。使用動態(tài)數(shù)據(jù)類型動態(tài)數(shù)據(jù)類型，其實就是指針類型。因為指針類型占用的是堆空間（有關(guān)PASCAL 的內(nèi)存管理請見附錄 PASCAL 的內(nèi)存分配），堆空間理論上0K之多（一般能用到 289K 左右），是?；驍?shù)據(jù)段空間的十倍，所以使用指針類型可大大緩解空間緊張問題。另外，指針類型可以根據(jù)實際需要分配內(nèi)存空間，比數(shù)組更靈活。但是，使用指針類型需要注意幾點：指針本身也占空間 不僅指針?biāo)赶虻馁Y料占空間，指針本身也是占

7、空間的。一個指針將占去堆空間是以八個字節(jié)為一個節(jié)的內(nèi)存空間。與硬盤用簇來作為文件的最小單位類似，Pascal 也將為每一個指針類型在堆中分配八的整倍數(shù)字節(jié)（例如 15 個字節(jié)的數(shù)據(jù)類型將占用 16 個字節(jié)的堆空間），無論指針指向的是字節(jié)類型還是數(shù)組類型。 利用文件如果其它方法都使用了，空間仍然不夠。那么就要考慮使用文件了。硬盤上幾十兆的空間任你用，空間問題自然是迎刃而解。但硬盤的速度要比內(nèi)存慢的多，這又容易造成時間不夠，所以不到必要時候，不要使用文件。程序中一般是使用類型文件，這是因為類型文件具有較好的靈活性，可以象數(shù)組一樣快速定位文件內(nèi)容，可以任何除文件類型或包含文件類型的構(gòu)造類型外的任何一

8、種類型。當(dāng)然，也可使用無類型文件。它的特點是可以從中一次一批資料至所需的任何數(shù)據(jù)類型，適用于高速輸入輸出及在文件中多種數(shù)據(jù)類型的場合。四、 時間的解決方案判重就是前面的那個判重。它減少了所需的狀態(tài)，自然減少了搜索的時間。判重是一種既節(jié)省空間，又節(jié)省時間的算法，應(yīng)此成為了每個搜索程序中都用到的算法。分枝定界在搜索中用一些約束條件將一些不必要的狀態(tài)去掉，以去掉這個狀態(tài)可能涎生的許許多多種分枝狀態(tài)，就象砍樹一樣，故名“分枝定界”。它在深度優(yōu)先搜索中效果明顯。前面提到的判重實際也是分枝定界。分枝定界也是搜索程序中常用的算法之一。在使用分枝定界的時候， 有時候不但使用題目給出的約束條件，還要從問題中找出

9、隱含的約束條件。例如跳馬問題，表面上并未給出任何約束條件，實際上也有不少約束條件，比如棋盤上不能有一個完全封閉（跳不進(jìn)去）的點、不能同時出現(xiàn)兩個只有一個點可跳入的點等等。當(dāng)然，剪枝的過程也會增加一定時間，所以一個好的約束條件可以火上澆油。設(shè)計估價函數(shù)空間與時間，不好的也可能使空間緊張問題在搜索中，每一步都有很多狀態(tài)需要搜索，往往狀態(tài)選得好，就能減少搜索次數(shù)，也就減少搜索時間，這一點在深度優(yōu)先搜索中體現(xiàn)較明顯。究竟怎樣才能使程序自動選擇狀態(tài)呢？需要設(shè)計一個估價函數(shù)，用它來對每一步搜索作評價，選出應(yīng)先搜索哪些狀態(tài)，后搜索哪些狀態(tài)。怎樣設(shè)計估價函數(shù)是一個很值得探討的問題，它將廣泛涉及相關(guān)學(xué)科的知識，

10、特別是數(shù)學(xué)的基礎(chǔ)知識。深度優(yōu)先搜索中最常用的估價方法就是檢查分支數(shù)量，分支較少的就較優(yōu)。這是因為分支少，一般來說搜索的時間就較少。如果搜索不到，浪費的時間也比較少。它也適用于廣度優(yōu)先搜索，但效果不明顯。犧牲空間，換取時間這個方法一看就明白，不需多講。它一般通過犧牲空間減少計算量來取得時間。不過，使用這個方法有個小竅門，就是前面曾提到過，指針類型一占就是八個字節(jié)，不妨將變量定義成八（或八的倍數(shù)）個字節(jié)的指針類型，這樣既不浪費空間，又減少了時間。 其它的小方面 用遞歸代替多重循環(huán)雖然會增加程序可讀性，但會減慢程序運行速度。 如果多重循環(huán)用單層循環(huán)代替（不增加循環(huán)次數(shù)），可以提高程序速度。五、 結(jié)語

11、優(yōu)化搜索主要是求得減少時間和空間消耗的方案，本文就列舉出了幾種方案，它們可以幫助大家在搜索省不少時間和空間。當(dāng)然，還有許多種本文所沒有舉出的方案，它們需要讀者自己來發(fā)掘。我只希望這幾個方案能使大家的搜索程序更快一些、更好一些。當(dāng)然，要想徹底解決搜索所存在的種種問題，就要利用別的、更好的方法（例如動態(tài)規(guī)劃）替代搜索。這需要大家利用自己的知識與經(jīng)驗來尋求。六、 附錄 PASCAL 的內(nèi)存分配PASCAL 采用堆棧結(jié)構(gòu)管理內(nèi)存。其內(nèi)存分配映像略圖如下：最大 640K堆最大約 64K棧最大約 64K最大約 64K數(shù)據(jù)段代碼段PASCAL 內(nèi)存分配映像略圖如圖，PASCAL 將指針變量安排在堆中，箭頭表示堆向