算法合集之《搜索順序的選擇》

《算法合集之《搜索順序的選擇》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、搜索順序的選擇福州三中王知昆例：【間隔排列】問題題意簡(jiǎn)述：有2N個(gè)木塊，每個(gè)木塊標(biāo)上1到N的自然數(shù)中的一個(gè)，每個(gè)數(shù)字會(huì)出現(xiàn)在兩個(gè)木塊上。把這些木塊排成一排，要求是：標(biāo)號(hào)為i的兩個(gè)木塊之間要間隔i個(gè)其它木塊。比如說N=3的情況，下面就是一個(gè)可行的排列：3，1，2，1，3，2。編程實(shí)現(xiàn)，對(duì)給定的N(n<=40)，求出一個(gè)可行排列。運(yùn)行效果比較N從大到小搜索從小到大搜索110.00sec0.00sec150.00sec0.11sec200.00sec36.32sec320.00sec超時(shí)400.00sec超時(shí)選擇搜索順序的基本原則1、取值范圍小的搜索元素先搜

2、索。2、一個(gè)搜索元素確定以后對(duì)其它搜索元素取值范圍的影響稱為制約力。制約力較大的搜索元素先搜索。3、先搜索對(duì)解影響較大的元素可以使剪枝時(shí)的估價(jià)函數(shù)更準(zhǔn)確，使剪枝更加有效。例：【算符破譯】（NOI2000）題意簡(jiǎn)述：古梅算符由小寫字母a到m組成，分別對(duì)應(yīng)于現(xiàn)代算符中的0,1,2,3,4,5,6,7,8,9,+,*,=中的一個(gè)。給出一組古梅算符表示的等式，若存在滿足等式的對(duì)應(yīng)關(guān)系，則輸出所有能夠確定的古梅算符和現(xiàn)代算符的對(duì)應(yīng)關(guān)系；否則輸出‘noway’。三個(gè)最特殊的元素本題中有三個(gè)算符最特殊：‘=’、‘*’、‘+’，它們要滿足以下條件：1、這三個(gè)算符不能出

3、現(xiàn)在等式的最左端和最右端。2、這三個(gè)算符兩兩不能相鄰。3、‘＝’，這是最特殊的算符，它在任何一個(gè)等式中必須出現(xiàn)且僅出現(xiàn)一次。確定搜索順序從取值范圍方面考慮，‘＝’，‘＋’，‘*’的取值范圍在所有算符中是最小的；從制約力方面考慮，‘＝’和‘＋’，‘*’的制約力無疑都強(qiáng)于‘0’到‘9’這十個(gè)數(shù)字；從對(duì)剪枝有利的角度考慮，這三個(gè)算符對(duì)解的影響最大，因此‘＝’，‘＋’，‘*’這三個(gè)算符應(yīng)當(dāng)放在搜索序列的前面。對(duì)于這三個(gè)算符，由于‘＝’受到的限制更多，取值范圍更小，所以應(yīng)當(dāng)優(yōu)先搜索。由此得出的最優(yōu)搜索順序：先搜索‘＝’，其次是‘＋’，‘*’，最后是10個(gè)數(shù)字。減

4、小搜索樹規(guī)模的具體實(shí)現(xiàn)方法1、靜態(tài)優(yōu)化搜索順序例【質(zhì)數(shù)方陣】(IOI94),【修建柵欄】(USACOTRAINING)2、動(dòng)態(tài)調(diào)整搜索順序例【棋盤遍歷】,【籃球錦標(biāo)賽】(BOI98)靜態(tài)優(yōu)化搜索順序在一些問題中，搜索元素的制約力和取值范圍在搜索過程中變化不大，或變化對(duì)搜索效率影響不大。如果要?jiǎng)討B(tài)判斷元素的取值范圍和制約力需要花費(fèi)較大的代價(jià)，而且優(yōu)化效果不好。在這種情況下只需在搜索開始前確定搜索順序，而不必在搜索過程中再改變搜索順序。動(dòng)態(tài)調(diào)整搜索順序有時(shí)在搜索過程中元素的取值范圍和制約力會(huì)有較大的變化，而且這些變化直接影響到搜索樹的規(guī)模,因此需要?jiǎng)討B(tài)的調(diào)

5、整搜索順序，也就是啟發(fā)式搜索。啟發(fā)式搜索繼承了回溯法占用空間少，編程簡(jiǎn)單的優(yōu)點(diǎn)，而啟發(fā)式搜索的最大優(yōu)點(diǎn)是可以在較短的時(shí)間內(nèi)找到一組可行解，這最適合解決一類只需要求出一組可行解的搜索問題。例：【質(zhì)數(shù)方陣】（IOI94）題意簡(jiǎn)述：在一個(gè)5*5的方陣中填入數(shù)字，使得沿行，沿列及兩個(gè)對(duì)角線的5個(gè)數(shù)字都能構(gòu)成一個(gè)5位質(zhì)數(shù)（5位質(zhì)數(shù)的首位不為0）。所有質(zhì)數(shù)的各位數(shù)字之和必須等于一個(gè)常數(shù)。這個(gè)常數(shù)和方陣左上角中的數(shù)字預(yù)先給出。若存在多個(gè)解，必須全部得出。搜索元素的性質(zhì)1、最后一行和最后一列：可以填的數(shù)字只有{1，3，7，9}。2、兩條對(duì)角線：與方陣中的所有五位素?cái)?shù)有

6、關(guān)。3、其他行列：特殊性取決于行列中已經(jīng)確定的格子個(gè)數(shù)。根據(jù)元素取值范圍和制約力確定搜索順序1、最后一行和最后一列是取值范圍最小的搜索元素，而且它們對(duì)其他所有的元素都有一定的制約力，因此要放在搜索序列的最前面。2、兩條對(duì)角線同樣影響到其他所有的搜索元素，制約力在剩下的格子中是最大的，因此也應(yīng)當(dāng)優(yōu)先搜索。3、剩下的行列依據(jù)它們?nèi)≈捣秶拇笮〈_定搜索順序。例:【籃球錦標(biāo)賽】（BOI98）題意簡(jiǎn)述：有5支球隊(duì)參加一次籃球錦標(biāo)賽。比賽采用單循環(huán)，每?jī)芍蜿?duì)比賽一次。已知每個(gè)隊(duì)最終的獲勝場(chǎng)次數(shù)，失敗場(chǎng)次數(shù)，總得分以及總失分，并給出所有場(chǎng)次得分的列表，要求出可能的

7、比賽的情況。（每一隊(duì)每場(chǎng)比賽的得分組成的戰(zhàn)績(jī)表）。動(dòng)態(tài)調(diào)整搜索順序的依據(jù)搜索元素（即每場(chǎng)的比分）之間的制約力大小很難確定。本題中，元素的取值范圍定義為某一場(chǎng)中一個(gè)隊(duì)的比分可以有幾種可能的取值。由于比分的取值范圍在搜索中會(huì)有較大的變化，而且這種變化直接影響到搜索樹的規(guī)模，因此改變搜索順序的主要依據(jù)就是每一個(gè)比分取值范圍的大小。動(dòng)態(tài)判斷元素取值范圍的方法首先，我們要進(jìn)行一次預(yù)處理，求出所有n次得分的總和等于m的情況（可以用HASH表存儲(chǔ)以提高檢索效率）。在搜索的每一步中，根據(jù)已經(jīng)填過的比分，我們可以判斷出剩余的比分中哪些是不能填在某個(gè)位置的。此外，在已知i

8、和j比賽的輸贏情況和I在這場(chǎng)比賽中得到的分?jǐn)?shù)，則這場(chǎng)比賽中j對(duì)i贏的比分也要受到限制。由此，可