搜索算法在大学生程序设计竞赛中的应用

吕晓聪 赖启腾 徐海力

摘 要：在运用计算机技术时，如果出现了一些较为复杂的问题，那么我们就可以采用搜索算法来进行解决，这种方法在计算机技术中起着至关重要的作用，并且在相關的程序设计竞赛中，搜索算法也是考察的重点之一。运用简单却严密的算法来解决实际问题是锻炼一个人基本功和积累潜力最强有力的途径，深度优先搜索和广度优先搜索是搜索算法中最为关键的两部分，要想熟练的运用搜索算法，我们就必须了解这两种搜索算法。其次，探讨搜索算法的规律，根据不同问题的特点制定不同的搜索方案，这也是我们熟练运用搜索算法的必然工作之一。

关键词：深度优先搜索；广度优先搜索；剪枝；启发式搜索；程序设计

随着社会的发展，计算机技术水平也变得越来越高，现阶段，很多计算机都已经具备高性能的操作方法，而搜索算法在计算机技术中起着至关重要的作用，它可以利用计算机的高性能在一定的时间内有效的求出问题解决的方法，也正是因为这一点，很多学者都将目光放到了搜索算法当中，并且这种算法也得到了大多数人的关注。现在，越来越多的大学生都开始关注起计算机程序设计竞赛，参加到这类竞赛，可以让大学生提高利用编程解决实际问题的能力，同时也能将一些方法灵活地运用在不同的问题之中，总而言之，大学生积极的参加到这类竞赛中可以提高自己的编程能力。

1 搜索算法

搜索算法是利用计算机高性能的特点通过遍历每一种可能性来寻求解决问题的方案，一般包括枚举法、深度优先（DFS）、广度优先（BFS）、A*算法等等。本文主要探讨深度优先算法和广度优先算法这两种较通用的算法。

深度优先算法，顾名思义，以深度优先进行搜索，是图算法的一种。英文全称为Depth First Search。深度优先搜索的实质是从某个未被访问过的节点出发，不断访问与当前结点相邻且未被访问过的结点，如果不存在这样的结点，则返回上一个结点。这一特性与递归的思想十分一致，在当前所要做的事情和下一步所要做的事情是一致的，所以，深度优先搜索用递归实现十分简单，当然，用非递归的方法同样可以实现。当结点返回到上一结点之后，DFS就可以沿另外一个方向进行搜索，当其找到最终目标之后，搜索工作就会结束。深度优先搜索并不是完美无缺的，也存在一些问题，当数据规模比较大，求解问题所用的时间会很长，在不限制搜索深度的情况下，可能引起堆栈溢出，从而找不到解。而且，在找到解的情况下，也不能保证找到的是问题的最优解。

广度优先搜索，又称为宽度优先搜索，也是图算法的一种，有点类似于树中的层序遍历，从某个未被访问过的结点出发，假设每两个相邻结点的距离为1，先访问与起始结点距离为1的所有结点，再访问与起始结点距离为2且未被访问过的结点，以此类推，直至所有的结点都被访问过。广度优先搜索的搜索方式更为细致，当问题有解时，可以找到最优解，而且它会将每个出口的路径都记录下来，就算经过不同的路口，它也会按照同样的方式进行记录。但是在最后一层的搜索时，广度优先搜索可能会采取一次性输出可能情况的手段，这就导致所需的存储空间较大。而且相比于深度優先搜索而言，效率比较低。

一般来说，深度优先搜索和广度优先搜索可以解决大多数的搜索问题，但是有些情况下，它们会受到内存、时间等因素的限制，这就导致在实际问题中，这两种搜索方式无法找到最优的解决方案。针对这一问题，我们必须对这两种搜索方式进行一定的改进。

2 搜索算法的选择与优化

2.1 搜索策略选取原则

一般来说，深度优先搜索和广度优先搜索都能解决一些比较简单的问题，但由于深度优先搜索编写方便，而且状态管理也比较方便，所以通常采用深度优先搜索。如果遇到的问题需要用多个路径来进行问题求解，那么我们也可以选择深度优先搜索，因为深度优先搜索在得到一个路径之后就可以直接进行输出，所以选择它可以最快的将问题解决。但是对于广度优先搜索来说，如果用它来解决这种多路径的问题，那么就会消耗大量的时间，因为在搜索过程中，广度优先搜索会把路径的节点全部保存起来，直到最后一个节点之后才会进行输出，这样不仅浪费空间，还会影响效率。对于广度优先搜索来说，最优解的问题求解是最适合它的。

根据以上搜索策略的选取原则，我们在国内的一些OJ平台（杭电、洛谷、51nod等等）选取了一些题目进行分析验证，都取得了不错的效果。

2.2 优化搜索策略

由于深度优先搜索和广度优先搜索是两种比较通用的搜索方法，在编程时我们往往采用较固定的模板，这样一来，当我们面对较为复杂的问题，编写的程序执行效率显然不高。因此，我们往往需要根据不同的问题对算法进行优化。

剪枝是搜索算法中常常采用的一种优化方法，也是大学生程序设计竞赛中的重要考点之一，如果我们的程序在比赛中运行超时，不妨考虑一下剪枝优化。剪枝的思想十分简单，它是根据上一层已经得到的结果进行判断，如果在现有条件下有可能出现问题的解，则继续往下搜索，否则立即返回上一层。这样一来，就可以避免搜索一些肯定没有结果的分支，从而提高了程序的效率。

启发式搜索也是一种对搜索策略的优化，它引导搜索朝着最后可能的方向前进，以搜索算法中著名的八数码问题为例，要想将数码移动步数降到最低，那么我们千万不能采取深度优先搜索方式，因为这种运算方式中采用了太多没有意义的中间状态，它会使运算过程变得过于复杂。虽然广地优先搜索可以在运算过程中找到最短的路径，但由于八数码问题空间过高，运用广度优先搜索仍会消耗大量的时间以及存储空间，所以综合来看，这两种运算方式都不合适。然而，启发式搜索可以在搜索前对相应的位置进行评估，并且按照指定的方向进行搜索，通过比较我们可以得出一个结论，在进行复杂问题解决的时候，启发式搜索具有较大的优势，所以在解决八数码问题的时候，我们通常采用的搜索算法都是启发式搜索。

3 结语

综上所述我们可以看出，现在，计算机的发展和搜索算法有着密切的关联，两者缺一不可。而且随着社会的进步，搜索的应用也变得越来越广泛，现阶段，我们的学习目标主要就是如何运用简单的运算方法来解决问题，这样可以有效的增强我们的个人能力以及解决问题的能力。其次，在现有的计算机程序设计竞赛中，搜索问题所占的比例是极高的，这也说明了一个问题，搜索算法在计算机技术中起着极为关键的作用。搜索策略是搜索过程中最重要的一步，好的策略可以有效的解决问题，为我们节省时间。在面对不同的问题时，我们要学会选择不同的方式，合理的搜索策略不仅可以节省时间，同时还可以在很大程度上提高搜索效率。

参考文献

[1]曲大鹏，张迪，连秋雨，等.搜索算法在计算机程序设计竞赛中的研究[J].辽宁大学学报（自然科学版），2016，（3）：209-213.

[2]刘洋.点格棋博弈中UCT算法的研究与实现[D].安徽大学，2016.

[3]光洋.爱恩斯坦棋计算机博弈系统的研究与实现[D].安徽大学，2016.

（作者单位：1.江苏科技大学 计算机科学与工程学院；2.江苏科技大学 计算机学院；3.江苏科技大学 材料科学与工程学院）