程序类竞赛中的搜索算法探讨

刘键沂 毛玉萃 刘逸飞 杨德胜

摘要：搜索问题在各类程序设计竞赛中常常出现。文章首先简单介绍了搜索算法，阐述了利用搜索解决实际问题的流程，并通过实例进一步探讨了如何运用枚举、深度优先搜索、广度优先搜索、记忆化搜索、二分搜索算法解决问题。

关键词：搜索算法;程序类竞赛;实例

中图分类号：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/.

【通联编辑：谢媛媛】