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

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

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

關鍵詞：搜索算法;程序類競賽;實例

中圖分類號：TP311.52? ? ? 文獻標識碼：A

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

開放科學（資源服務）標識碼（OSID）：

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

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

2 求解搜索問題的一般流程及相關概念

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

3 各類搜索的解題思路和應用舉例

3.1 枚舉

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

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

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

3.2 深度優先搜索

深度優先搜索（DFS）的思想是從某一個頂點p開始，一層一層往下走，走到底，如果發現不能到達目標解，那就返回上一層的節點，然后選擇一條沒有走過的路徑開始走到底。通常還需要搭配適當的剪枝，剔除掉不合理的解，使搜索的深度減少。通常的剪枝方法有可行性剪枝、最優性剪枝。通過剪枝，可以省去大量的冗余計算。

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

由于需要找到二叉樹節點s到t的最短路徑，根據二叉樹性質得出需要找出兩個節點的最近公共祖先，最短路徑為：s到最近公共祖先，再由最近公共祖先到t節點。可以記錄從根節點到s節點和到t節點的路徑path1和path2，易得出結論，兩路徑的最長公共前綴為根節點到 s與t最近公共祖先節點的路徑對應的方向字符串。所以題目需要的最短路徑為將path1的公共前綴部分去掉再將剩余路徑全改成U（s節點公共祖先節點路徑）再加上path2去掉公共前綴部分（從公共祖先節點到t節點路徑）。代碼如圖3所示。

3.3 廣度優先搜索

廣度優先搜索的核心思想是從起始點開始，訪問起始點的所有相鄰節點，再訪問起始點相鄰節點的相鄰節點，一層一層地遍歷。

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

從0000開始，向周圍8個結點發散（各個撥輪向上或向下撥），從無向圖中來看就是從核心向周圍不斷擴散，同時記錄擴散的圈數作為旋轉次數，如果遇到deadends直接跳過，或者達到target直接返回即可。為了避免搜索到死亡數字，可以使用哈希表存儲 deadends 中的所有元素，同時，用該哈希表所有搜索到的狀態，避免重復搜索。因為如果一個狀態如果在前面的步數中已經搜索過則說明就算這個狀態能到達target需要的步數也不是最小的，直接跳過該狀態即可。代碼如圖4所示。

3.4 記憶化搜索

搜索通常會重復處理相同的子問題從而導致代碼運行時間過長，可以用記憶化搜索進行優化，以解決重復計算;它的核心思想是在搜索中搜索的子問題會反復出現時，這時可以記錄下該子問題的解，當下次再次搜索相同子問題的時候可以直接獲取該子問題的解，類似于動態規劃，保存之前狀態的解用于后續狀態的求解。

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

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

3.5 二分搜索

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

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

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

4 搜索算法思想在其他算法中的體現

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

5 結束語

搜索算法有其基本思想、解決問題的規律和流程，在程序類競賽中被廣泛應用，如果恰當地運用搜索算法解決問題，不但問題得以很好解決，同時也能減少解題時間。所以為了在算法競賽中取得更好的成績，搜索算法作為基礎算法的研究是必須的，還需要多加訓練，深入思考搜索算法。

參考資料

[1] Cormen T H.算法導論[M].殷建平，譯.北京：機械工業出版社，2013.

[2] 李煜東.算法競賽進階指南[M].鄭州：中原出版傳媒集團·河南電子音像出版社，2018.

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

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

[5] 打開轉盤鎖[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/.

【通聯編輯：謝媛媛】