程序類競(jìng)賽中的搜索算法探討

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

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

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

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

文章編號(hào)：1009-3044（2022）12-0064-03

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

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

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

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

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

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

3.1 枚舉

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

例1[3]問題簡(jiǎn)述：游戲中存在兩種角色：1）好人：該角色只說真話。2）壞人：該角色可能說真話，也可能說假話。有一個(gè)下標(biāo)從0開始的二維整數(shù)數(shù)組statements，大小為 n * n ，表示n個(gè)玩家對(duì)彼此角色的陳述。具體來說，statements[i][j]可以是下述值之一：0表示i的陳述認(rèn)為j是壞人。1表示i的陳述認(rèn)為j是好人。2表示i沒有對(duì)j作出陳述。另外，玩家不會(huì)對(duì)自己進(jìn)行陳述。形式上，對(duì)所有0<=i<n ，都有 statements[i][i]=2 。根據(jù)這n個(gè)玩家的陳述，找出可以認(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)算模擬，每一個(gè)二進(jìn)制位表示一個(gè)人，第i位為1表示該人是好人，0表示是壞人。代碼如圖2所示。

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

深度優(yōu)先搜索（DFS）的思想是從某一個(gè)頂點(diǎn)p開始，一層一層往下走，走到底，如果發(fā)現(xiàn)不能到達(dá)目標(biāo)解，那就返回上一層的節(jié)點(diǎn)，然后選擇一條沒有走過的路徑開始走到底。通常還需要搭配適當(dāng)?shù)募糁Γ蕹舨缓侠淼慕猓顾阉鞯纳疃葴p少。通常的剪枝方法有可行性剪枝、最優(yōu)性剪枝。通過剪枝，可以省去大量的冗余計(jì)算。

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

由于需要找到二叉樹節(jié)點(diǎn)s到t的最短路徑，根據(jù)二叉樹性質(zhì)得出需要找出兩個(gè)節(jié)點(diǎn)的最近公共祖先，最短路徑為：s到最近公共祖先，再由最近公共祖先到t節(jié)點(diǎn)。可以記錄從根節(jié)點(diǎn)到s節(jié)點(diǎn)和到t節(jié)點(diǎn)的路徑path1和path2，易得出結(jié)論，兩路徑的最長(zhǎng)公共前綴為根節(jié)點(diǎn)到 s與t最近公共祖先節(jié)點(diǎn)的路徑對(duì)應(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]題目簡(jiǎn)描：有一個(gè)帶有四個(gè)圓形撥輪的轉(zhuǎn)盤鎖。每個(gè)撥輪都有10個(gè)數(shù)字：0，1，2，3，4，5，6，7，8，9。每個(gè)撥輪可以隨意旋轉(zhuǎn)：例如可以把1撥為0，或可以把1撥為2。每次旋轉(zhuǎn)可以旋轉(zhuǎn)鎖的其中一個(gè)撥輪。鎖的初始狀態(tài)為0000。有一個(gè)死亡數(shù)字列表deadends，一旦撥輪的數(shù)字和列表里的任何一個(gè)元素相同，這個(gè)鎖將永遠(yuǎn)無法被打開。字符串target代表該鎖的解鎖數(shù)字，找出解開該鎖的最小旋轉(zhuǎn)次數(shù)，如果該鎖不能被解鎖則該鎖的最小旋轉(zhuǎn)解鎖次數(shù)為-1，求出解開該鎖的最小旋轉(zhuǎn)次數(shù)。

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

3.4 記憶化搜索

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

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

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

3.5 二分搜索

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

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

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

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

搜索算法的思想在圖論中經(jīng)典的求最短路徑的Dijkstra算法中有體現(xiàn)。Dijkstra算法是一個(gè)基于貪心、廣度優(yōu)先搜索、動(dòng)態(tài)規(guī)劃于一體的求圖中一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法。該算法采用的是一種貪心策略，有一個(gè)描述起始點(diǎn)到其他所有點(diǎn)的目前已求得的最短路徑值的數(shù)組dis和標(biāo)記已找到最小路徑點(diǎn)的vis數(shù)組，找出所有與起始點(diǎn)相鄰的點(diǎn)，將它們與起始點(diǎn)的距離填入對(duì)應(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ī)律和流程，在程序類競(jìng)賽中被廣泛應(yīng)用，如果恰當(dāng)?shù)剡\(yùn)用搜索算法解決問題，不但問題得以很好解決，同時(shí)也能減少解題時(shí)間。所以為了在算法競(jìng)賽中取得更好的成績(jī)，搜索算法作為基礎(chǔ)算法的研究是必須的，還需要多加訓(xùn)練，深入思考搜索算法。

參考資料

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

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

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

[4] 2096. 從二叉樹一個(gè)節(jié)點(diǎn)到另一個(gè)節(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. 完成旅途的最少時(shí)間[EB/OL].[2021-06-24].https：//leetcode-cn.com/problems/minimum-time-to-complete-trips/.

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