程序類競賽中的搜索算法探討

劉鍵沂 毛玉萃 劉逸飛 楊德勝

摘要：搜索問題在各類程序設(shè)計競賽中常常出現(xiàn)。文章首先簡單介紹了搜索算法，闡述了利用搜索解決實(shí)際問題的流程，并通過實(shí)例進(jìn)一步探討了如何運(yùn)用枚舉、深度優(yōu)先搜索、廣度優(yōu)先搜索、記憶化搜索、二分搜索算法解決問題。

關(guān)鍵詞：搜索算法;程序類競賽;實(shí)例

中圖分類號：TP311.52? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2022）12-0064-03

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

1 搜索算法的概述[1-2]

搜索算法是指有目的的窮舉一個問題的所有解或一部分可能解，從而得出問題的正確解的一種方法。常見搜索算法有枚舉搜素、深度優(yōu)先搜索、廣度優(yōu)先搜索、記憶化搜索、二分搜索等。通常的優(yōu)化方法有：在搜索的過程中通過問題的約束條件進(jìn)行剪枝葉或保存搜索過程中的中間解，避免重復(fù)求解相同的情況。

2 求解搜索問題的一般流程及相關(guān)概念

對于搜索問題，求解的一般流程如圖1所示;首先要根據(jù)問題給出的條件找出所有的可能解或生成所有可能解的算法，例如有的問題可以根據(jù)問題的描述找到解的極大值和極小值或有的題目可以選定一個初始狀態(tài)DFS（深度優(yōu)先搜索）或BFS（廣度優(yōu)先搜索）找到所有可能解。第二步找出驗(yàn)證每個可能解的方法，有的解可能不符合問題描述需要剔除，記錄下正確解。第三步找出可能的剪枝方案，例如題目需要求極小值，當(dāng)某個解在驗(yàn)證過程中已經(jīng)大于已有的極小值，則該解不可能是最終解，應(yīng)該通過剪枝剔除這種解，防止搜索的解過多造成程序復(fù)雜度過高。第四步，根據(jù)找到的所有正確解找出符合題目要求的解返回。

3 各類搜索的解題思路和應(yīng)用舉例

3.1 枚舉

枚舉是指搜索所有可能解，最終得到符合題目要求的解，時間復(fù)雜度通常為需要驗(yàn)證解的數(shù)量。

例1[3]問題簡述：游戲中存在兩種角色：1）好人：該角色只說真話。2）壞人：該角色可能說真話，也可能說假話。有一個下標(biāo)從0開始的二維整數(shù)數(shù)組statements，大小為 n * n ，表示n個玩家對彼此角色的陳述。具體來說，statements[i][j]可以是下述值之一：0表示i的陳述認(rèn)為j是壞人。1表示i的陳述認(rèn)為j是好人。2表示i沒有對j作出陳述。另外，玩家不會對自己進(jìn)行陳述。形式上，對所有0<=i<n ，都有 statements[i][i]=2 。根據(jù)這n個玩家的陳述，找出可以認(rèn)為是好人的最大數(shù)目。（2≤n≤15）

觀察數(shù)據(jù)范圍發(fā)現(xiàn)n的值很小，可以枚舉所有人是好人或壞人，然后進(jìn)行解的正確性驗(yàn)證：根據(jù)該情況下的好人的描述，因?yàn)楹萌酥荒苷f真話，所以好人描述的好人必須要在這種情況下是好人，壞人也必須是壞人，如果違反了則說明該解不可能發(fā)生，最后根據(jù)所有可能解找出最大的好人數(shù)。因?yàn)楸绢}只有好人和壞人兩種情況可以使用位運(yùn)算模擬，每一個二進(jìn)制位表示一個人，第i位為1表示該人是好人，0表示是壞人。代碼如圖2所示。

3.2 深度優(yōu)先搜索

深度優(yōu)先搜索（DFS）的思想是從某一個頂點(diǎn)p開始，一層一層往下走，走到底，如果發(fā)現(xiàn)不能到達(dá)目標(biāo)解，那就返回上一層的節(jié)點(diǎn)，然后選擇一條沒有走過的路徑開始走到底。通常還需要搭配適當(dāng)?shù)募糁?，剔除掉不合理的解，使搜索的深度減少。通常的剪枝方法有可行性剪枝、最優(yōu)性剪枝。通過剪枝，可以省去大量的冗余計算。

例子2[4]問題簡述：有一棵二叉樹的根節(jié)點(diǎn)root，這棵二叉樹總共有n個節(jié)點(diǎn)。每個節(jié)點(diǎn)的值為1到n中的一個整數(shù)，且互不相同。有一個整數(shù)startValue，表示起點(diǎn)節(jié)點(diǎn)s的值，和另一個不同的整數(shù)destValue，表示終點(diǎn)節(jié)點(diǎn)t的值。請找到從節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑，并以字符串的形式返回每一步的方向。每一步用大寫字母L、R和U分別表示一種方向：L表示從一個節(jié)點(diǎn)前往它的左孩子節(jié)點(diǎn)。R表示從一個節(jié)點(diǎn)前往它的右孩子節(jié)點(diǎn)。U表示從一個節(jié)點(diǎn)前往它的父節(jié)點(diǎn)。返回從s到t最短路徑每一步的方向。

由于需要找到二叉樹節(jié)點(diǎn)s到t的最短路徑，根據(jù)二叉樹性質(zhì)得出需要找出兩個節(jié)點(diǎn)的最近公共祖先，最短路徑為：s到最近公共祖先，再由最近公共祖先到t節(jié)點(diǎn)?？梢杂涗洀母?jié)點(diǎn)到s節(jié)點(diǎn)和到t節(jié)點(diǎn)的路徑path1和path2，易得出結(jié)論，兩路徑的最長公共前綴為根節(jié)點(diǎn)到 s與t最近公共祖先節(jié)點(diǎn)的路徑對應(yīng)的方向字符串。所以題目需要的最短路徑為將path1的公共前綴部分去掉再將剩余路徑全改成U（s節(jié)點(diǎn)公共祖先節(jié)點(diǎn)路徑）再加上path2去掉公共前綴部分（從公共祖先節(jié)點(diǎn)到t節(jié)點(diǎn)路徑）。代碼如圖3所示。

3.3 廣度優(yōu)先搜索

廣度優(yōu)先搜索的核心思想是從起始點(diǎn)開始，訪問起始點(diǎn)的所有相鄰節(jié)點(diǎn)，再訪問起始點(diǎn)相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，一層一層地遍歷。

例3[5]題目簡描：有一個帶有四個圓形撥輪的轉(zhuǎn)盤鎖。每個撥輪都有10個數(shù)字：0，1，2，3，4，5，6，7，8，9。每個撥輪可以隨意旋轉(zhuǎn)：例如可以把1撥為0，或可以把1撥為2。每次旋轉(zhuǎn)可以旋轉(zhuǎn)鎖的其中一個撥輪。鎖的初始狀態(tài)為0000。有一個死亡數(shù)字列表deadends，一旦撥輪的數(shù)字和列表里的任何一個元素相同，這個鎖將永遠(yuǎn)無法被打開。字符串target代表該鎖的解鎖數(shù)字，找出解開該鎖的最小旋轉(zhuǎn)次數(shù)，如果該鎖不能被解鎖則該鎖的最小旋轉(zhuǎn)解鎖次數(shù)為-1，求出解開該鎖的最小旋轉(zhuǎn)次數(shù)。

從0000開始，向周圍8個結(jié)點(diǎn)發(fā)散（各個撥輪向上或向下?lián)埽?，從無向圖中來看就是從核心向周圍不斷擴(kuò)散，同時記錄擴(kuò)散的圈數(shù)作為旋轉(zhuǎn)次數(shù)，如果遇到deadends直接跳過，或者達(dá)到target直接返回即可。為了避免搜索到死亡數(shù)字，可以使用哈希表存儲 deadends 中的所有元素，同時，用該哈希表所有搜索到的狀態(tài)，避免重復(fù)搜索。因?yàn)槿绻粋€狀態(tài)如果在前面的步數(shù)中已經(jīng)搜索過則說明就算這個狀態(tài)能到達(dá)target需要的步數(shù)也不是最小的，直接跳過該狀態(tài)即可。代碼如圖4所示。

3.4 記憶化搜索

搜索通常會重復(fù)處理相同的子問題從而導(dǎo)致代碼運(yùn)行時間過長，可以用記憶化搜索進(jìn)行優(yōu)化，以解決重復(fù)計算;它的核心思想是在搜索中搜索的子問題會反復(fù)出現(xiàn)時，這時可以記錄下該子問題的解，當(dāng)下次再次搜索相同子問題的時候可以直接獲取該子問題的解，類似于動態(tài)規(guī)劃，保存之前狀態(tài)的解用于后續(xù)狀態(tài)的求解。

例4[6]題目簡述：A和B兩個人在抽獎。現(xiàn)在有一個抽獎箱，里面有n張中獎票，m張不中獎票。A和B輪流從中抽一張獎票出來。如果有人抽到中獎票就結(jié)束，抽到中獎票的人勝利。抽過的獎票會被丟棄。額外地，B每次抽后，會再次抽取一張票并丟棄掉（這張票中獎不算B勝利）?，F(xiàn)在，A先抽，請問A的勝率，保留4位小數(shù)后輸出。如果兩人到最后也沒有抽到中獎票算作B勝利。

根據(jù)題意可得知使用深度優(yōu)先搜索，在剩下n張中獎票，m張不中獎票時，A獲勝的概率為他直接抽到中獎票加上B沒獲勝的概率乘上A在剩下的x張中獎票，y張不中獎票抽到中獎票的概率。但是直接暴力的深度優(yōu)先搜索復(fù)雜度太高，這時注意到在求B沒獲勝的概率乘以A在剩下的x張中獎票，y張不中獎票抽到中獎票的概率中反復(fù)計算在x張中獎票和y張不中獎票情況下A獲勝的概率p，這時可以用記憶化搜索優(yōu)化，記錄A在x張中獎票，y張不中獎票情況下獲勝的概率，避免重復(fù)計算相同情況下的獲勝概率。代碼如圖5所示。

3.5 二分搜索

在碰到取極值類搜索問題時，如果使用普通暴力搜索遍歷所有n個可能解，再對這n個可能解進(jìn)行驗(yàn)證，可能會導(dǎo)致運(yùn)行時間過長，這時可以使用二分搜索解，先設(shè)置好解的可能最大值和最小值，再對解進(jìn)行二分，根據(jù)解的驗(yàn)證結(jié)果決定二分的方向，只需要驗(yàn)證logN個可能解，比驗(yàn)證n個解的復(fù)雜度要低不少。

例子5[7]一個數(shù)組time，其中time[i]表示第i輛公交車完成一趟旅途所需要花費(fèi)的時間。每輛公交車可以連續(xù)完成多趟旅途，也就是說，一輛公交車當(dāng)前旅途完成后，可以立馬開始下一趟旅途。每輛公交車獨(dú)立運(yùn)行，也就是說可以同時有多輛公交車在運(yùn)行且互不影響。有一個整數(shù)totalTrips，表示所有公交車總共需要完成的旅途數(shù)目。請你返回完成至少totalTrips趟旅途需要花費(fèi)的最少時間。

題目是求完成totalTrips花費(fèi)的最少時間，想到將時間從1開始依次枚舉找到符合的第一個返回，但是[1， ans]這個區(qū)間依次都計算就會超時，需要通過二分查找來加速這個模擬過程。二分查找的L是1（時間的最小可能性），R是最小的time乘上totalTrips（最長的花費(fèi)時間），然后在判斷時依次將mid時間每輛公交車能完成的趟數(shù)計算累加起來，如果大于等于totalTrips則需要繼續(xù)往左查找，最后找到的L就是答案。代碼如圖6所示。

4 搜索算法思想在其他算法中的體現(xiàn)

搜索算法的思想在圖論中經(jīng)典的求最短路徑的Dijkstra算法中有體現(xiàn)。Dijkstra算法是一個基于貪心、廣度優(yōu)先搜索、動態(tài)規(guī)劃于一體的求圖中一個點(diǎn)到其他所有點(diǎn)的最短路徑的算法。該算法采用的是一種貪心策略，有一個描述起始點(diǎn)到其他所有點(diǎn)的目前已求得的最短路徑值的數(shù)組dis和標(biāo)記已找到最小路徑點(diǎn)的vis數(shù)組，找出所有與起始點(diǎn)相鄰的點(diǎn)，將它們與起始點(diǎn)的距離填入對應(yīng)的dis數(shù)組位，遍歷dis數(shù)組，找出最小路徑的點(diǎn)，則起始點(diǎn)到該點(diǎn)的最小距離為dis數(shù)組中的距離，將該點(diǎn)在vis數(shù)組中標(biāo)記，再以到該點(diǎn)的最短路徑距離加上從該點(diǎn)到其相鄰點(diǎn)的距離更新dis數(shù)組，再次遍歷dis數(shù)組，找出最小路徑的點(diǎn)，則起始點(diǎn)到該點(diǎn)的最小距離為dis數(shù)組中的距離，將該點(diǎn)在vis數(shù)組中標(biāo)記，再以到該點(diǎn)的最短路徑距離加上從該點(diǎn)到其相鄰點(diǎn)的距離更新dis數(shù)組重復(fù)上述步驟，直到找出到所有點(diǎn)的最短距離。代碼如圖7所示。

5 結(jié)束語

搜索算法有其基本思想、解決問題的規(guī)律和流程，在程序類競賽中被廣泛應(yīng)用，如果恰當(dāng)?shù)剡\(yùn)用搜索算法解決問題，不但問題得以很好解決，同時也能減少解題時間。所以為了在算法競賽中取得更好的成績，搜索算法作為基礎(chǔ)算法的研究是必須的，還需要多加訓(xùn)練，深入思考搜索算法。

參考資料

[1] Cormen T H.算法導(dǎo)論[M].殷建平，譯.北京：機(jī)械工業(yè)出版社，2013.

[2] 李煜東.算法競賽進(jìn)階指南[M].鄭州：中原出版?zhèn)髅郊瘓F(tuán)·河南電子音像出版社，2018.

[3] 2151. 基于陳述統(tǒng)計最多好人數(shù)[EB/OL].[2022-01-23]. https：//leetcode-cn.com/problems/maximum-good-people-based-on -statements/.

[4] 2096. 從二叉樹一個節(jié)點(diǎn)到另一個節(jié)點(diǎn)每一步的方向[EB/OL].[2021-12-05].https：//leetcode-cn.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/.

[5] 打開轉(zhuǎn)盤鎖[EB/OL].[2021-06-24].https：//leetcode-cn.com/problems/open-the-lock/solution/da-kai-zhuan-pan-suo-by-leetcode-solutio-l0xo/.

[6] 2020屆360春招筆試編程題[EB/OL].[2021-06-24].https：//blog.csdn.net/peakzzz/article/details/105082162/.

[7] 2187. 完成旅途的最少時間[EB/OL].[2021-06-24].https：//leetcode-cn.com/problems/minimum-time-to-complete-trips/.

【通聯(lián)編輯：謝媛媛】