第四章

搜索算法中的優(yōu)化技巧4.1 搜索中的剪枝技巧4.2 選擇合適的搜索方向4.3 A*算法4.4 跳舞鏈4.5 搜索還是動(dòng)態(tài)規(guī)劃 搜索算法本質(zhì)上是沒有技巧性的，在搜索的過程中，大量不可能成為最優(yōu)解的子樹被遍歷，造成了時(shí)間上的浪費(fèi)，讓程序發(fā)現(xiàn)這些“無用”的節(jié)點(diǎn)，并在很早的時(shí)候就把它們剪去，可以顯著提高程序的效率。 在搜索算法進(jìn)行剪枝的過程中，必須注意以下幾點(diǎn)： （1）正確性：剪枝必須保證不能影響到結(jié)果的正確性。 （2）準(zhǔn)確性：能夠盡可能多的剪掉不會(huì)得到正確結(jié)果的枝條。 （3）高效性：在剪枝的過程中，會(huì)添加額外的計(jì)算過程，帶來額外的消耗，剪枝的過程中必須保證減少的計(jì)算量比這些計(jì)算的過程要多，以避免“得不償失”的剪枝結(jié)果。

【例4.1】輸入一個(gè)n·m的迷宮，以及一個(gè)時(shí)間t，‘x'代表障礙物，迷宮中起點(diǎn)和終點(diǎn)已知。移動(dòng)到相鄰的格子需要1秒的時(shí)間，并且走過的格子會(huì)塌陷掉，不能再次經(jīng)過，問：能否在時(shí)間t恰好到達(dá)終點(diǎn)? n、m≤6,t≤36。

【算法分析】看到數(shù)據(jù)范圍，應(yīng)聯(lián)想到此題的算法復(fù)雜度一定不低（因?yàn)槿绻袕?fù)雜度較低的算法，本題的數(shù)據(jù)范圍應(yīng)更大）。在網(wǎng)格上尋找路徑的典型算法有插頭dp和搜索，但本題中，使用插頭dp很難建立模型，因此，使用搜索算法是一個(gè)不錯(cuò)的選擇。 在本題中，需要記錄的狀態(tài)是這個(gè)迷宮的狀態(tài)，以及當(dāng)前的坐標(biāo)，使用寬度優(yōu)先搜索，每個(gè)節(jié)點(diǎn)需要記錄的空間大小太過龐大（每個(gè)節(jié)點(diǎn)需要至少n·m＋3的空間），所以本題使用深度優(yōu)先搜索更合適。 本題使用深度優(yōu)先搜索，代碼非常容易實(shí)現(xiàn)：4.1 搜索中的剪枝技巧 intdfs（inti，intj，intstep）

｛ if（isTarget（i，j，step）） return1；

if（step>t） return0；

∥枚舉四個(gè)方向 for（intfx=0；fx＜=3；fx＋＋）

｛ intnex=i＋dx[fx]； intney=j＋dy[fx]； if（can（nex，ney））

｛ vis[nex][ney]=1； if（dfs（nex，ney，step＋1）==1） return1； vis[nex][ney]=0；

｝

｝ return0；

｝4.1 搜索中的剪枝技巧 但這樣的暴力算法顯然不能滿足題目的時(shí)間要求，需要在此基礎(chǔ)上進(jìn)行優(yōu)化。 剪枝1： 每個(gè)格子在經(jīng)過之后就會(huì)塌陷，因此，只能在第t步到達(dá)終點(diǎn)，凡是在中間過程中經(jīng)過終點(diǎn)的，都不能夠成為最優(yōu)解：

if（i==tx﹠﹠j==ty﹠﹠step！=t）

returnO； 如此一來，凡是中間經(jīng)過了終點(diǎn)的路徑全部都在經(jīng)過終點(diǎn)的那一刻被剪掉。 剪枝2：

假設(shè)當(dāng)前搜索到位置（x，y），已經(jīng)走了step步，終點(diǎn)是（tx，ty），那么，即使是最好的情況，也需要|tx—x|＋|ty—y|步才可以走到終點(diǎn)。如果|tx—x|＋|ty—y|滿足：

|tx—x|+|ty—y|＞t—step

顯然剩余的步數(shù)不能夠在第t步時(shí)到達(dá)終點(diǎn)，可以被剪去。 剪枝3：

考慮坐標(biāo)（x，y），每走一步，（x＋y）的奇偶性都會(huì)變化，從第一步到最后一步，奇偶性會(huì)變化t次，如果起點(diǎn)（sx，sy）在奇偶性變化t次后奇偶性與終點(diǎn)（tx，ty）不同，則永遠(yuǎn)不可能在第t步的時(shí)候到達(dá)終點(diǎn)，可以在搜索之前剪掉。 此優(yōu)化可以顯著提高搜索的效率，因?yàn)樗菑囊婚_始就把大量不可能有解的情況判斷出來，避免了搜索的過程。4.1 搜索中的剪枝技巧 剪枝4： 考慮剪枝2，使用|tx—x|＋|ty一y|只是一個(gè)粗略的估計(jì)，如果對(duì)于當(dāng)前的狀態(tài)，使用bfs求出從（x，y）到達(dá)（tx，ty）的最短路dis，如果dis＞t—step，則剪去，這樣剪枝力度更大。 由于這個(gè)剪枝需要用到一次bfs，時(shí)間復(fù)雜度是O（nm），因此本剪枝須慎重考慮。實(shí)際上，在本題目中，這個(gè)剪枝的效果是很明顯的。 在以上四個(gè)剪枝的基礎(chǔ)上實(shí)現(xiàn)代碼，此題目可以達(dá)到秒殺的效果，本書所附代碼只使用了優(yōu)化2、3，使用所有優(yōu)化的代碼請(qǐng)讀者自行實(shí)現(xiàn)。 【程序?qū)崿F(xiàn)】 /* prob:hdul010 lang∶c＋＋

*/ #include＜iostream＞ #include＜math.h＞ usingnamespacestd； chars[10][10]； intax，ay，bx，by，n，m，k； intt[4][2]=｛1，0，—1，0，0，1，0，—1｝，vist[10][10]，flag；4.1 搜索中的剪枝技巧4.1 搜索中的剪枝技巧4.1 搜索中的剪枝技巧4.1 搜索中的剪枝技巧4.1 搜索中的剪枝技巧

【例4.5】有N個(gè)糖果，M個(gè)小孩（1≤N，M≤13），給定一個(gè)like矩陣，like[i][j]=1表示第i個(gè)小孩喜歡第j個(gè)糖果，like[i][i]=0表示第i個(gè)小孩不喜歡第i個(gè)糖果。如果把第j個(gè)糖果給第i個(gè)小孩吃，他喜歡，則得到K（K不變且K≤10）的歡喜值，不喜歡則只得到1的歡喜值，問：是否能夠合理分配糖果，使得每個(gè)小孩的歡喜值超過B[i]?

【算法分析】本題的正解是最大費(fèi)用最大流，此處只討論搜索做法。 顯而易見，本題目中，窮舉所有的分配方式，共有n×m種情況，極限情況下情況數(shù)是：302875106592253≈3×1014，顯然不能通過此題。 考慮真實(shí)的情況，老師在發(fā)糖果時(shí)，為了得到較好的結(jié)果，一定會(huì)盡量給每個(gè)小孩發(fā)他們喜歡的糖果吃?；诖?，在搜索的過程中，也應(yīng)該盡量先去搜索那些讓小孩吃到他們喜歡的糖果的情況。 因此，在搜索之前，可以對(duì)每個(gè)小孩，按照喜歡程度對(duì)每個(gè)小孩分別排序出一個(gè)糖果順序，喜歡的糖果在前，不喜歡的糖果在后。（優(yōu)化1） 用tang[i]表示喜歡糖果i的人數(shù)，用like[j][i]表示小孩j對(duì)糖果i的喜歡程度。那么，對(duì)于一個(gè)小孩j，like[j][i]是糖果i在小孩j中排序的第一關(guān)鍵字，tang[i]是第二關(guān)鍵字。（優(yōu)化2） 最后，應(yīng)用卡時(shí)的思想，在有限時(shí)間內(nèi)不能得到Y(jié)ES的結(jié)果，則認(rèn)為它不能得到正解，輸出NO。（優(yōu)化3）4.2 選擇合適的搜索方向4.2 選擇合適的搜索方向4.2 選擇合適的搜索方向4.2 選擇合適的搜索方向4.2 選擇合適的搜索方向4.2 選擇合適的搜索方向 A*搜尋算法俗稱A星算法。這是一種在圖形平面上，有多個(gè)節(jié)點(diǎn)的路徑，求出最低通過成本的算法。常用于游戲中NPC的移動(dòng)計(jì)算，或線上游戲中BOT的移動(dòng)計(jì)算上。A*算法的應(yīng)用非常廣泛，其思想可以應(yīng)用在搜索算法的每一個(gè)角落。要了解A*搜索，首先要學(xué)習(xí)以下幾個(gè)概念： 啟發(fā)式搜索算法： 普通的搜索算法，在搜索的過程中，只是窮舉每一個(gè)可能的選擇，在搜索的過程中并沒有選擇性，無論是“好”或“壞”的節(jié)點(diǎn)，都會(huì)搜索下去，使得算法的復(fù)雜度變得非常高。啟發(fā)式搜索算法，相當(dāng)于在搜索的過程中，人為的規(guī)定評(píng)定規(guī)則，對(duì)當(dāng)前的狀態(tài)進(jìn)行評(píng)估，讓程序只去搜索那些認(rèn)為“值得”去搜索的節(jié)點(diǎn)，犧牲了答案的絕對(duì)正確性，換來時(shí)間上的優(yōu)化，這樣的算法無法保證其正確性，但往往會(huì)得到正解。A*算法作為啟發(fā)式算法的一種，在保證正確性的前提條件下提高了搜索的效率。以下是在A*算法中經(jīng)常用到的概念。 估價(jià)函數(shù)： 估價(jià)函數(shù)是用來估計(jì)當(dāng)前狀態(tài)距離目標(biāo)狀態(tài)的距離的函數(shù)，通過好的估價(jià)函數(shù)，可以很好的看到每個(gè)節(jié)點(diǎn)產(chǎn)生最優(yōu)解的可能性，在搜索中有著極其重要的用途。 一種通用的估價(jià)函數(shù)是這樣的： 假設(shè)當(dāng)前狀態(tài)下，已經(jīng)使用的代價(jià)是g（n），到達(dá)目標(biāo)狀態(tài)的真實(shí)代價(jià)是h*（n），如果有一種方法估計(jì)當(dāng)前狀態(tài)距離目標(biāo)狀態(tài)的代價(jià)h（n）滿足

g（n）＋h（n）＜h*（n） 我們稱h（n）是一種滿足理想狀態(tài)情況下的估價(jià)。這樣的估價(jià)方式有非常重要的意義，在之后的例題中將會(huì)體現(xiàn)。4.3 A*

算法 A*搜索：

A*搜索本質(zhì)上是一種有序的啟發(fā)式算法，在寬度優(yōu)先搜索時(shí)，哪個(gè)節(jié)點(diǎn)先進(jìn)隊(duì)，就會(huì)先搜索那個(gè)節(jié)點(diǎn)，即使是相對(duì)“壞”的進(jìn)隊(duì)，也會(huì)不加考慮的去搜索它，造成大量“壞”的節(jié)點(diǎn)先被搜索完整棵子樹，浪費(fèi)了大量的時(shí)間。A*搜索會(huì)對(duì)擴(kuò)展出的每一個(gè)節(jié)點(diǎn)進(jìn)行排序，每次搜索時(shí)，優(yōu)先搜索那些我們認(rèn)為“好”的節(jié)點(diǎn)，使得答案向正確的方向逼近，及早找到目標(biāo)狀態(tài)。

IDA*: IDA*是A*搜索在使用深度優(yōu)先搜索實(shí)現(xiàn)時(shí)的應(yīng)用，其特點(diǎn)是，每次枚舉搜索的深度，當(dāng)深度在1以內(nèi)時(shí)找不到結(jié)果，才會(huì)在深度為2以內(nèi)的子樹中尋找，避免了深度優(yōu)先搜索“一條路走到黑”的情況，同時(shí)，利用良好的估價(jià)函數(shù)，讓那些在本次深度限制下不可能到達(dá)目標(biāo)狀態(tài)的分支被剪掉，節(jié)省了大量的時(shí)間?！纠?.9】八數(shù)碼問題。 給定一個(gè)3×3的矩陣，矩陣上1～8恰好都出現(xiàn)了一次，x也出現(xiàn)了一次，x表示該位置是一個(gè)空格，每次操作可以將x與其上、下、左、右四個(gè)位置中的一個(gè)數(shù)字交換，當(dāng)所有的數(shù)字滿足如下排列時(shí)達(dá)到目標(biāo)：12345678x4.3 A*

算法 如果可能，輸出任意一種方案即可（用u、d、l、r表示上、下、左、右），如果不可能，輸出“unsolvable”。

【算法分析】本題是一道非常典型的搜索題目，使用BFS或者DFS都可以輕易的寫出窮舉的代碼，由于本題只需要一種方案即可，因此，只需要記錄每一個(gè)狀態(tài)是否遍歷過即可。對(duì)于本題目，常見的兩種哈希方法是：C＋＋中的map和康拓展開。 方法1：map

用x表示9，把這個(gè)3×3的矩陣當(dāng)做一個(gè)9位的10進(jìn)制數(shù)，例如題目中的目標(biāo)狀態(tài)是[123456780]，狀態(tài)中數(shù)值的范圍是[123456789～987654321]，在競(jìng)賽中，數(shù)組顯然不能開這么大，使用哈希表又會(huì)增加一定的編程復(fù)雜度，因此，可以退而求其次使用C＋＋STL中的map。

方法2：康拓展開 對(duì)于本題目，每個(gè)狀態(tài)實(shí)際上是自然數(shù)[1，9]的一個(gè)全排列，可以使用康拓展開?？低卣归_是一個(gè)把全排列和自然數(shù)構(gòu)建雙射的算法，它可以將一個(gè)全排列映射到一個(gè)自然數(shù)中去，并且這個(gè)自然數(shù)不會(huì)很大。公式如下：

X=a[n]×(n—1)!＋a[n—1]×(n—2)!＋…＋a[i]×(i—1)!＋…＋a[1]×0!

其中，a[n]表示的是還沒有出現(xiàn)過的數(shù)字中，比這個(gè)位置上的數(shù)字小的數(shù)字個(gè)數(shù)。 例如357412968，比3小的數(shù)字有2個(gè)，比5小的數(shù)字有（1，2，3，4）四個(gè)，但3已經(jīng)出現(xiàn)過，因此未出現(xiàn)的只有3個(gè)，同理，比7小還未出現(xiàn)過的數(shù)字有4個(gè)。4.3 A*

算法 按照這樣的方式計(jì)算：

X=2×8!＋3×7!＋4×6!＋2×5!＋0×4!＋0×3!＋2×2!＋0×1!＋0×0!=98884

康拓展開計(jì)算出的數(shù)，最大是： （n—1）×（n—1）!＋（n—2）×（n—2）!＋…＋（i—1）×（i—1）!＋…＋0×0!≈n!

當(dāng)n=9時(shí)，最大也只有約9!=362880，是完全可以接受的。需要注意的是，康拓展開的時(shí)間復(fù)雜度是O（n2），使用樹狀數(shù)組可以優(yōu)化到O（nlnn）。 在此基礎(chǔ)上，本題還要求記錄路徑，保存路徑的方法有兩種可供參考:

方法1：對(duì)于每一個(gè)狀態(tài)，把這個(gè)狀態(tài)所走過的路徑全部都保存在其對(duì)應(yīng)的空間下，例如，某狀態(tài)經(jīng)歷操作“urrlrrl”到達(dá)，則把這個(gè)字符串記錄在其對(duì)應(yīng)的狀態(tài)編號(hào)下。其可以通過d操作到達(dá)新的狀態(tài)，在新的狀態(tài)中，記錄路徑為“urrlrrl”＋“d”=“urrlrrld”。這樣的記錄方式很好理解，但效率卻很差。 方法2：考慮到對(duì)于任何兩個(gè)可以通過一步到達(dá)的狀態(tài)，它們記錄的字符串除了最后一個(gè)，全部都一樣，因此，可以使用一個(gè)數(shù)組pre來記錄每個(gè)狀態(tài)的前一個(gè)狀態(tài)是誰，action數(shù)組來記錄每個(gè)狀態(tài)的最后一次操作。在輸出結(jié)果時(shí)，只需要不停向前尋找，將路徑上的action倒序輸出，即是每次操作。這樣的做法，本質(zhì)上是構(gòu)建了一棵搜索樹，注明了每個(gè)狀態(tài)是由哪一個(gè)狀態(tài)轉(zhuǎn)移而來以及轉(zhuǎn)移的操作。在效率上，方法2要優(yōu)于方法1。4.3 A*

算法 解決了狀態(tài)表示和記錄路徑的問題，本題的代碼比較容易實(shí)現(xiàn)，提交后可以通過此題。但本題還有更好的做法。 考慮本題中的搜索樹：當(dāng)只走一步時(shí)，最多只會(huì)擴(kuò)展出4個(gè)不同的狀態(tài)；只走兩步時(shí)，最多會(huì)擴(kuò)展出4×4=16個(gè)不同的狀態(tài)；走k步時(shí)，最多會(huì)擴(kuò)展出4k個(gè)不同的狀態(tài)。每當(dāng)搜索樹深度增加一層，樹中可能的節(jié)點(diǎn)個(gè)數(shù)都要增加近4倍之多。而正確答案很可能就在深度很淺的位置，因此，使用深度優(yōu)先搜索會(huì)有概率遇到極端情況，耗費(fèi)大量時(shí)間。為解決這個(gè)問題，引入一個(gè)搜索算法的優(yōu)化：迭代加深搜索（InDepth-dfs）。 迭代加深算法的思想非常簡(jiǎn)單，是在每次進(jìn)行深度優(yōu)先搜索前，首先限制搜索的深度最大為1，超過此深度則直接返回，如果深度≤1的全部節(jié)點(diǎn)都不是答案，再限制搜索的深度最大為2，重復(fù)上述工作。如此擴(kuò)大搜索的最大深度直到搜索到答案或是無解為止。 這樣的做法看似很愚蠢，同一個(gè)節(jié)點(diǎn)被大量重復(fù)的訪問，但實(shí)際上卻能夠在同級(jí)別的時(shí)間復(fù)雜度下規(guī)避上面的情況，達(dá)到均攤復(fù)雜度提高的效果，一個(gè)簡(jiǎn)單的證明如下： 假設(shè)深度最小的答案節(jié)點(diǎn)深度為k，則枚舉的深度depth為[1，k]， 當(dāng)depth=1時(shí)，共遍歷最多X1=4個(gè)節(jié)點(diǎn)。 當(dāng)depth=2時(shí)，共遍歷最多X2=4＋4×4=20個(gè)節(jié)點(diǎn)。 當(dāng)depth=3時(shí)，共遍歷最多X3=4＋4×4＋4×4×4=84個(gè)節(jié)點(diǎn)。 當(dāng)depth=i時(shí)，共遍歷最多Xi=∑4i個(gè)節(jié)點(diǎn)。 顯而易見，Xi＞∑Xj（j＜i）。因此，ID-dfs算法時(shí)間復(fù)雜度不超過原算法的兩倍。4.3 A*

算法 在此基礎(chǔ)上，還有另一個(gè)基于A*思想的優(yōu)化： 用g（n）表示到達(dá)狀態(tài)n時(shí)，已經(jīng)走過的步數(shù)， 用h（n）表示到達(dá)狀態(tài)n時(shí)，理想情況下最少需要的步數(shù)， 用h*（n）表示到達(dá)狀態(tài)n時(shí)，實(shí)際的最少代價(jià)。 對(duì)于當(dāng)前枚舉的最大深度k，如果有：

h（n）＜=h×（n） 式1 g（n）＋h（n）＞k 式2

則將這個(gè)狀態(tài)剪掉，不再進(jìn)行搜索。式1限制了估計(jì)的理想狀態(tài)一定不能比實(shí)際狀態(tài)差，式2表示，如果當(dāng)前狀態(tài)在最理想的狀態(tài)下，都不能在深度k以內(nèi)完成，則將它剪枝，不再在當(dāng)前深度k下搜索。對(duì)于式2，g（n）和k都是已知量，需要設(shè)計(jì)一個(gè)滿足是理想情況，并且與事實(shí)相差并不太遠(yuǎn)的估價(jià)函數(shù)h（n）。 看下面一個(gè)樣例：312564789

它們距離目標(biāo)狀態(tài)位置的曼哈頓距離是（9作為交換位置，不統(tǒng)計(jì)）：21111200x4.3 A*

算法 每次交換操作，最多只有其中一個(gè)元素向自己的目標(biāo)近了1步，因此，在上述狀態(tài)中，最少要經(jīng)過2＋1＋1＋1＋1＋2=8次操作，才能夠?qū)⑦@個(gè)狀態(tài)變?yōu)槟繕?biāo)狀態(tài)。 更普遍的，對(duì)于任何一個(gè)當(dāng)前狀態(tài)，利用它們距離目標(biāo)狀態(tài)位置的曼哈頓距離之和作為h（n），作為到達(dá)目標(biāo)狀態(tài)的估價(jià)函數(shù)。顯然，這樣的估價(jià)一定不會(huì)比實(shí)際情況更快到達(dá)。結(jié)合ID和A*，該IDA*算法的流程如下:

（1）枚舉搜索的深度depth，進(jìn)行深度優(yōu)先搜索。 （2）對(duì)每一個(gè)狀態(tài)計(jì)算h（n），如果滿足h（n）＋g（n）＞depth，則剪去。 （3）枚舉四個(gè)方向可能的交換，進(jìn)行搜索。 【程序?qū)崿F(xiàn)】 /* PROB:hdu1043 LANG:c＋＋

*/ #include＜iostream＞ #include＜string.h＞ #include＜stdio.h＞ #include＜algorithm＞4.3 A*

算法4.3 A*

算法4.3 A*

算法4.3 A*

算法4.3 A*

算法4.3 A*

算法4.3 A*

算法 跳舞鏈（DancingLinks），又叫十字鏈表（以下簡(jiǎn)稱dlx），是一類搜索問題的通用優(yōu)化，可以高效解決精確覆蓋、重復(fù)覆蓋類的問題，其結(jié)構(gòu)如圖4.2所示。圖4.2跳舞鏈的結(jié)構(gòu)4.4 跳舞鏈 為引出dlx，請(qǐng)看如下一段代碼：

intdfs（）

｛ for（inti=1；i＜=n；i＋＋） if（!vis[i]）

｛ vis[i]=1； dfs（）； vis[i]=0；

｝

｝ 這一段代碼的復(fù)雜度是O（n!）。但是，其實(shí)際運(yùn)行時(shí)，復(fù)雜度卻比n!要高。原因是，其在每次枚舉時(shí)，只需要vis[i]=0的點(diǎn)，卻枚舉了所有的點(diǎn)來判斷其vis值。一種合理的優(yōu)化是：用鏈表來實(shí)現(xiàn)這個(gè)數(shù)組，每當(dāng)有一個(gè)元素被選擇，就把它從鏈表中刪掉，并進(jìn)行搜索，當(dāng)搜索完畢時(shí)，再將其恢復(fù)。由于鏈表的刪除和插入操作都是O（1）的，這樣的優(yōu)化可以使得每次枚舉只枚舉有效的點(diǎn)，而不是所有的點(diǎn)，代碼如下：4.4 跳舞鏈 intdfs（）

｛ for（inti=qhead；i—＞next!=null；i=i—＞next）

｛ delete（i）； dfs（）； resume（i）；

｝

｝ 這樣一來，該算法就是嚴(yán)格意義上的O（n!）。 現(xiàn)在把該問題從一維擴(kuò)展到二維。假設(shè)在一個(gè)矩陣中，每次選擇一行之后，一些對(duì)應(yīng)的行就不能再選了。那么在搜索的過程中，如果使用普通數(shù)組的方式實(shí)現(xiàn)，無用的枚舉代價(jià)會(huì)更大，造成算法效率的嚴(yán)重降低。dlx實(shí)質(zhì)上就是上述鏈表的二維實(shí)現(xiàn)，其是一個(gè)鏈表結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)有上、下、左、右四個(gè)方向的指針，其中，上、下指針中有一個(gè)指針用來刪除行，一個(gè)指針來恢復(fù)行，左、右指針中有—個(gè)指針用來刪除列，一個(gè)指針用來恢復(fù)列。通過這樣高效的刪除、恢復(fù)操作，優(yōu)化搜索的枚舉過程，提高搜索的效率。4.4 跳舞鏈 在很多時(shí)候會(huì)遇到這樣的題目：一眼望上去是一道搜索題目，但仔細(xì)分析又覺得搜索算法的復(fù)雜度并不能滿足題目的時(shí)間或空間要求，此時(shí)，就需要謹(jǐn)慎思考下一步的改進(jìn)策略。常常被誤認(rèn)為是暴力的搜索的題目往往可能是以下類型的題目：搜索＋剪枝、動(dòng)態(tài)規(guī)劃、動(dòng)態(tài)規(guī)劃＋搜索、網(wǎng)絡(luò)流。如何在第一時(shí)間想到搜索算法，并且當(dāng)該方法無法滿足題目時(shí)限要求時(shí)，如何改進(jìn)或修改算法是很重要的技能。本節(jié)將會(huì)給出很多例子，讓讀者在思考中循序漸進(jìn)的尋找更好的算法，來解決一道道難題。

【例4.13】Pills。一個(gè)瓶子里有n片藥，每次吃半片，從瓶子里可能取出整片，也可能取出半片，如果取到的藥是整片的，就把它分成兩半，吃掉其中的一半，另—半重新放入瓶中，如果取到半粒藥，則直接吃掉。問2n天內(nèi)吃完藥有多少種取法?n≤32。

【算法分析】這道題目，從數(shù)據(jù)范圍上看，顯然像是一道搜索題目，讀者可以很輕松的寫出如下的代碼： #include＜iostream＞ usingnamespacestd； longlongfun（intx，inty）

｛ longlongans＝0； if（y＝＝0）return1； if（x＝＝0）return1；4.5 搜索還是動(dòng)態(tài)規(guī)劃 ans＋＝fun（x—1，y＋1）； if（y） ans＋＝fun（x，y一1）； returnans；

｝ intmain（）

｛ inti，n； while（scanf（"%d"，﹠n）﹠﹠n）

｛ printf（"%I64d\n"，fun（n，O））；

｝ returnO；

｝ 其中，x表示剩余的完整藥片數(shù)量，y表示