【聲明：本文為原創(chuàng)文章,未經(jīng)同意,嚴(yán)禁轉(zhuǎn)載和抄襲,違者將追究其法律責(zé)任】

/?寫在前面的話?/

蘇世機(jī)試小課堂，考研機(jī)試不再慌！

公主號(hào)：蘇世學(xué)社考研? 蘇世計(jì)算機(jī)考研

搜索是什么？

搜索是利用計(jì)算機(jī)的高性能來有目的地窮舉一個(gè)問題解空間的部分或所有的可能情況，從而求出問題的解的一種辦法。

利用搜索能干什么？

在大規(guī)模實(shí)驗(yàn)環(huán)境中，通常在搜索前，根據(jù)條件降低搜索規(guī)模；并根據(jù)問題的約束條件進(jìn)行剪枝；再利用搜索過程中的中間解，避免重復(fù)計(jì)算這幾種方法進(jìn)行優(yōu)化。

搜索常用內(nèi)容介紹

1

暴力枚舉

1.1 概念

暴力枚舉，也叫窮舉法。就是將所有的情況都列舉出來，依次判斷是否符合題目條件，合適就保留這一項(xiàng)，不合適就放棄這一項(xiàng)，最終得出一般結(jié)論。利用計(jì)算機(jī)運(yùn)算精確度高、速度快的特點(diǎn)，對(duì)該問題的所有可能情況挨個(gè)逐次檢驗(yàn)，從而篩選出符合題目要求的答案。其最大難點(diǎn)是應(yīng)該從一個(gè)什么樣的維度來進(jìn)行暴力枚舉。

?

1.2 基本條件

（1）時(shí)間方面：一般來說主流OJ中，1000ms時(shí)間限制下可以運(yùn)行操作數(shù)是10的7次方以內(nèi)的運(yùn)算，所以在枚舉的時(shí)候先看一下數(shù)據(jù)范圍，確保整個(gè)程序的執(zhí)行操作數(shù)不會(huì)超過這個(gè)量級(jí)，如果超過就要更換枚舉維度或者使用其他算法。

注意：當(dāng)范圍特別大的時(shí)候，用枚舉法明顯會(huì)超時(shí)。

（2）編程實(shí)現(xiàn)方面：一般需要枚舉范圍連續(xù)。如果離散，比較難用循環(huán)枚舉出所有狀態(tài)，也就不能保證解的完整性，但有些數(shù)據(jù)看似離散，實(shí)際上可以經(jīng)過處理變得連續(xù)，比如構(gòu)造數(shù)組。也需要枚舉內(nèi)容已知，不能在枚舉到某個(gè)地方的時(shí)候發(fā)現(xiàn)未知。

?

1.3?方法步驟

（1）確定枚舉變量、枚舉范圍（盡量縮?。┖兔杜e條件；

（2）根據(jù)題目要求循環(huán)檢驗(yàn)每一個(gè)解（盡量剪枝）。

?

1.4?典型例題

題目描述：

四平方和定理，又稱為拉格朗日定理：每個(gè)正整數(shù)都可以表示為至多4個(gè)正整數(shù)的平方和。如果把0包括進(jìn)去，就正好可以表示為4個(gè)數(shù)的平方和

比如：5 = 0^2 + 0^2 + 1^2 + 2^2

比如：7 = 1^2 + 1^2 + 1^2 + 2^2（^符號(hào)表示乘方的意思）

對(duì)于一個(gè)給定的正整數(shù)，可能存在多種平方和的表示法。

要求你對(duì)4個(gè)數(shù)排序：0 <= a<= b <= c <= d

并對(duì)所有的可能表示法按a,b,c,d 為聯(lián)合主鍵升序排列，最后輸出第一個(gè)表示法。

樣例輸入：5

樣例輸出：0 0 1 2

樣例輸入：12

樣例輸出：0 2 2 2

樣例輸入：773535

樣例輸出：1 1 267 838

輸入：程序輸入為一個(gè)正整數(shù)N(N<5000000)

輸出：要求輸出4個(gè)非負(fù)整數(shù)，按從小到大排序，中間用空格分開

本題思路：

第一眼看上去可以用四層循環(huán)暴力求解，但會(huì)超時(shí)，最后一層可以通過開平方求出來，可以省一層，5000000開平方大于2236，所以循環(huán)的最大值就設(shè)置為2237。

代碼實(shí)現(xiàn)：

運(yùn)行結(jié)果：

2

遞歸及其應(yīng)用

2.1?概念

遞歸是直接或者間接調(diào)用自身，是一種解決問題的方法，具體來說就是把規(guī)模大的原問題分解為規(guī)模小的相似的子問題，持續(xù)分解，直到小到可以用非常簡(jiǎn)單直接的方式來解決。

?

2.2?基本條件

從概念中我們可以得到遞歸的基本條件：

（1）原問題可以分解為子問題。

（2）調(diào)用自身：通過遞歸調(diào)用來縮小問題的規(guī)模，并且子問題和原問題有相同的形式。

（3）子問題有窮，就是說分解次數(shù)是有限的。

（4）存在一種情況可以使遞歸退出，使問題得到解決。

?

2.3?怎么更好地理解遞歸

比如我們收到一個(gè)禮物盒，我們打開后發(fā)現(xiàn)又是一個(gè)禮物盒，打開后發(fā)現(xiàn)還是一個(gè)禮物盒，然后我們不斷地打開更小的禮物盒......直到發(fā)現(xiàn)一張紙條，上面寫著：若想考研成功，請(qǐng)把禮物盒包回到它最原始的狀態(tài)。然后我們又一層一層地把禮物盒包回去。

這個(gè)過程就是遞歸的完整過程，不斷地縮小問題規(guī)模，直到遇到一個(gè)情境或者邊界使問題結(jié)束，然后依次退出。

?

2.4?經(jīng)典問題

（1）斐波那契數(shù)列

0,1,1,2,3,5,8,13,21,34,55,89,144....

這樣的數(shù)列就是斐波那契數(shù)列，總之就是第N(N>2)個(gè)數(shù)等于第(N-1)個(gè)數(shù)和第(N-2)個(gè)數(shù)的和。

fib(N) = fib(N-1)+fib(N-2)

遞歸算法實(shí)現(xiàn)和運(yùn)行結(jié)果：

（2）階乘

階乘得到的是一個(gè)整數(shù)從1連續(xù)乘到它本身的結(jié)果。

比如：2的階乘為2! = 2 * 1

比如：5的階乘為5! = 5 * 4 *3 * 2 * 1

遞歸算法實(shí)現(xiàn)和運(yùn)行結(jié)果：

3

廣度/寬度優(yōu)先搜索

3.1?概念

廣度優(yōu)先搜索（寬度優(yōu)先搜索）又稱為BFS（Breadth First Search），是最簡(jiǎn)便的圖的搜索算法之一，是連通圖的一種遍歷策略，屬于一種盲目搜尋法，簡(jiǎn)言之就是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)以找尋結(jié)果。主要用到隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)。

?

3.2?算法思想

使用隊(duì)列來實(shí)現(xiàn)，整個(gè)過程可以看做一個(gè)倒立的樹形：

（1）把根節(jié)點(diǎn)放在隊(duì)列的末尾。

（2）每次從隊(duì)列的頭部取出一個(gè)元素，查看這個(gè)元素所有的下一級(jí)元素，把它們放到隊(duì)列的末尾，并把這個(gè)元素記為它下一級(jí)元素的前驅(qū)。

（3）找到所要找的元素時(shí)程序結(jié)束。

（4）如果遍歷整個(gè)樹還沒有找到，結(jié)束程序。

?

3.3?典型例題

題目描述

給定一個(gè)大小為N x M的迷宮。迷宮由通道和墻壁組成，每一步可以由鄰接的上下左右四格的通道移動(dòng)。請(qǐng)求出從起點(diǎn)到終點(diǎn)所需最小步數(shù)。

（’#’、’.’、‘S’、'G’分別表示墻壁、通道、起點(diǎn)、終點(diǎn)）

樣例輸入

??

樣例輸出

? ?22

代碼實(shí)現(xiàn)

運(yùn)行結(jié)果

4

深度優(yōu)先搜索

4.1?概念

深度優(yōu)先搜索又稱DFS（Depth First Search），是對(duì)每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問一次。換句話說，就是找一個(gè)起始結(jié)點(diǎn)，沿著這個(gè)起始結(jié)點(diǎn)一直找下去，直到找到最后一個(gè)滿足條件的分節(jié)點(diǎn)，然后再尋找另一條路徑，沿著一條路走不滿足時(shí)會(huì)自動(dòng)返回上一層節(jié)點(diǎn)繼續(xù)進(jìn)行判斷。

?

4.2?基本方法

（1）訪問頂點(diǎn)v；

（2）依次從v的未被訪問的鄰接點(diǎn)出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷，直至圖中和v有路徑相通的頂點(diǎn)都被訪問；

（3）若此時(shí)圖中尚有頂點(diǎn)未被訪問，則從一個(gè)未被訪問的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點(diǎn)均被訪問過為止。

?

4.3?典型例題

題目描述

在一個(gè)給定形狀的棋盤（形狀可能是不規(guī)則的）上面擺放棋子，棋子沒有區(qū)別。要求擺放時(shí)任意的兩個(gè)棋子不能放在棋盤中的同一行或者同一列，請(qǐng)編程求解對(duì)于給定形狀和大小的棋盤，擺放k個(gè)棋子的所有可行的擺放方案C。

輸入

輸入含有多組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)的第一行是兩個(gè)正整數(shù)，n k，用一個(gè)空格隔開，表示了將在一個(gè)n*n的矩陣內(nèi)描述棋盤，以及擺放棋子的數(shù)目。n <= 8 , k <= n當(dāng)為-1 -1時(shí)表示輸入結(jié)束。隨后的n行描述了棋盤的形狀：每行有n個(gè)字符，其中 # 表示棋盤區(qū)域， . 表示空白區(qū)域（數(shù)據(jù)保證不出現(xiàn)多余的空白行或者空白列）。

輸出

對(duì)于每一組數(shù)據(jù)，給出一行輸出，輸出擺放的方案數(shù)目C （數(shù)據(jù)保證C<2^31）。

樣例輸入

?

樣例輸出

? ?2

? ?1

思路

按照每行來搜索，每一行都可以選擇放或者不放旗子,后期只需要考慮是否在同一列。

代碼實(shí)現(xiàn)

運(yùn)行結(jié)果

5

搜索剪枝技巧

5.1?概念

剪枝是提高搜索算法時(shí)空效率使算法大大優(yōu)化的技巧，因?yàn)樗阉魉惴ǖ臅r(shí)間復(fù)雜度多數(shù)是指數(shù)級(jí)的，難以滿足對(duì)程序運(yùn)行時(shí)間的限制要求，所以需要剪枝來降低時(shí)間復(fù)雜度。

形象點(diǎn)來說，剪枝就是通過一些判斷來避免不必要的遍歷的過程，這些過程可以理解為枝條。

有時(shí)暴力搜索過不了時(shí)間限制的算法，通過各種剪枝+優(yōu)化之后能成功通過，所以剪枝的重要性不言而喻。

?

5.2?剪枝技巧

（1）優(yōu)化搜索順序

一般來說搜索的順序是不固定的，在一個(gè)問題中，算法可以進(jìn)入搜索樹的任意一個(gè)節(jié)點(diǎn)，不同的搜索順序會(huì)產(chǎn)生不同的搜索樹形態(tài)，規(guī)模大小也相差很遠(yuǎn)，比如從一個(gè)節(jié)點(diǎn)開始搜搜到最后才可能出解，從另一個(gè)節(jié)點(diǎn)開始搜，一搜就能搜到，所以像這種存在單調(diào)性的搜索問題要和貪心思想結(jié)合，進(jìn)行順序剪枝，提高搜索效率。

（2）排除等效冗余

在搜索過程中，若能判斷從搜索樹當(dāng)前節(jié)點(diǎn)上沿著某幾條不同分支到達(dá)的子樹是相同的，那么只需要對(duì)其中一條分支執(zhí)行搜索。

（3）可行性剪枝

也叫上下界剪枝，在搜索過程中，及時(shí)對(duì)當(dāng)前進(jìn)行檢查，如果當(dāng)前狀態(tài)和題意不符，并且可以推出往后的情況和題意都不符，那么就可以進(jìn)行剪枝，直接把這種情況和后續(xù)的情況排除，立即回溯。

（4）最優(yōu)性剪枝

在最優(yōu)化問題的搜索過程中，如果當(dāng)前的結(jié)果不如當(dāng)前的最優(yōu)解，無論采取多么好的策略到達(dá)遞歸邊界都不能更新最優(yōu)解，那么應(yīng)該立即停止對(duì)當(dāng)前分支的搜索并進(jìn)行回溯。

（5）記憶化搜索

記錄搜索過程中的每一個(gè)狀態(tài)，當(dāng)重復(fù)搜索到相同的狀態(tài)時(shí)就直接回溯，換句話說就是搜到重復(fù)的直接返回。

蘇世學(xué)社旗下品牌，專注于計(jì)算機(jī)考研

計(jì)算機(jī)考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學(xué)習(xí)分享丨咨詢前輩丨個(gè)性化指導(dǎo)