NOIP实用算法 3.搜索
3.搜索
a.复杂的模拟问题与利用相似性
b.函数的递归调用
c.栈与深度优先搜索
d.深度优先搜索的优化
e.队列与广度优先搜索
f.广度优先搜索的优化
a.复杂的模拟问题与利用相似性
在讲模拟方法时我们讲过利用相似性来简化算法。现在，我们继续关注这个问题。
搜索算法是一种“模拟”思维的算法，比较接近平常的思维。与模拟算法相比，它更深刻地利用了相似性。
为了更好地说明，下面举一个例子：
有一把有n位字母的密码锁，每一位上的字母都可从a到z选取。现密码被遗忘，开锁时，请给出一个方便的方法，使每个字母组合都被尝试过。
最容易想到的方法便是，按aa…aa，aa…ab，aa…ac，…，aa…az，aa…ba，…，zz…zy，zz…zz这样的字典序来尝试。
我们可以这样考虑：
先选定第一位，再选定第二位，……，直到选定第n位，形成一个完整的字母组合。
具体地，在每一位的选取时，都从a开始，到后面位的字母组合全部尝试过，再跳到下一个字母；若（非首位）已经跳到z而还需再跳一个字母时，就跳到a，同时让它的前一位跳到下一个字母。
例如，n=3时，形成的字母组合的顺序是
a a a - aaa b - aab c - aac ... z - aaz b a - aba b - abb ... z - abz c a - aca ...... z z - azz b a a - baa ...... z z - bzz c a a - caa ......... z z z - zzz |
以上描述的是一种常见的遍历方法。
我们注意到，选定每一位的过程是极其相似的。我们需要利用这种相似性。
b.函数的递归调用
结构化编程语言提供的最大好处无疑是函数的递归调用。
如果把函数看成解决某个问题的过程，那么递归就可以看成把问题变成相似而更小的问题的过程。注意这两个关键词：相似、更小。递归的本质是利用相似性。
我们接着讲上面提到的密码锁问题。现在我们要把尝试过的字母组合都输出到屏幕上。
我们用递归法来完成这个过程。写递归体一般分为两步：把大问题化成小问题、解决最小问题。
char string[1000],n; void code(int Left) //递归体，Left表示还需要决定的位数，这个值随问题的减小而递减。 { if(Left>=1) //把大问题化成小问题 for(string[n-Left]='a';string[n-Left]<='z';string[n-Left]++) code(Left-1); if(Left==0) //解决最小问题 printf("%s\n",string); } int main() { fscanf("%d",&n); string[n]='\0'; code(n); return 0; } |
分析这个方法，得知其时间复杂度为O(26^n)。
补充一句，上面的过程也可用n个for的嵌套来实现（你能做到吗？）。
c.栈与深度优先搜索
搜索分为深度优先搜索、广度优先搜索两种。下面用树区分这两种搜索方法。
对于树，从根节点开始，查找（遍历）各节点，分两种方式：
从某一节点向下扩展时，若先遍历其子节点，再查找其子节点的子节点——广度优先搜索。
从某一节点向下扩展时，若遇到子节点就“深入”到子节点的子节点，直到叶子节点再返回——深度优先搜索。
对于7顶点的完全二叉树，两种方式所到达的顶点顺序如下：
1 1 2 3 2 5 4 5 6 7 3 4 6 7 广度优先 深度优先 |
注意：搜索面对的数据结构往往不是树。
显然，深度优先搜索的扩展方式类似于上面叙述的函数递归。这里，我们先分析它。
深度优先搜索在实现时有两种方式：递归形式、非递归形式。
递归形式利用一个函数（以整型为例）int cal(…)：
int cal(…)
{
int n;
//运算
n=cal(…); //递归，常在循环体中
//运算
return n; //返回
}
非递归形式利用一个栈，它可以被看作是递归形式的一个改变：
当要递归地调用cal(…)时，不立即调用cal(…)，而是将其参数压入栈。等函数运行完，再从栈中弹出其参数并再次执行函数cal(…)。
这样，最后被调用的最先执行。由于后查找的是深度最大的，这样的结果是深度优先。
深度优先搜索往往采用递归方法。
一代算法宗师迪杰斯特拉（E. W. Dijkstra）极力推崇递归法。它编写方便、清晰，只是内存消耗略比非递归大。非递归法往往在担心内存溢出时使用。
深度优先搜索的巨大优势就是可以率先到达叶子节点。对于“找出一种方法”、“找出其中一个解”这样的问题有速度上的优势。这里举例分析。
八数码问题：九宫格里有八个分别填上了数字1-8，形成最初构型。每步只能把空格上下左右的数之一与空格对调。现要求找出一种方法，使若干步对调后呈现目标构型。例如：
5 7 2 1 2 3 4 _ 1 -> 4 5 6 6 3 8 7 8 _ |
思路：每次将一个构型变为另一个，再递归地检查后者能否到达目标构型。时间复杂度O(4^n)。
伪代码：
int EightNumbers(构型) 这里返回步骤数，若需要知道具体步骤，则用另用栈储存步骤。
{
同源构型则返回32767
同目标构型则返回0
n[1]=EightNumbers(变化出的构型1)
n[2]=EightNumbers(变化出的构型2)
n[3]=EightNumbers(变化出的构型3)
n[4]=EightNumbers(变化出的构型4)
step=n[1-4]最小值
step为32767则返回32767
返回step+1
}
d.深度优先搜索的优化
显然，以上代码是可以优化的。深搜的优化过程也叫“剪枝”。考虑到实用性，这里我们只讲最简单的剪枝方法。
对于上面的伪代码，将“同源构型则返回32767”改为“同已查找构型则返回32767”就可以显著提高效率。
但是这里需要开辟一个数组（栈），记录之前“经过”的构型。如果想避免遍历数组，可以做成哈希表，而且要压缩储存才行。
还有的简单方法，编写的时候自然会想到的。关键是要权衡，用这样的方法所增加的编写难度是否配得上所节省的运行时间。编写难度增大，调试的难度也会增大哦。
e.队列与广度优先搜索
上面讲过用栈来非递归地实现深搜。若是把栈改成队列呢？
经过分析，你会发现，这样修改后深搜变成了广搜！
用这样的方法可以实现广搜。
用数组实现队列时避免大量元素的移动。实现时，可以先算出队列元素的上限max，开辟a[max]，并设a[st]为队列起始（st初值为0），队列的第i项储存在a[(st+i-1)%max]。
这样，出队列只用将st=(++st%max)即可。
要注意的问题是，广搜类似于递推，往往需要开辟空间储存每一步“递推”所得到的值。
f.广度优先搜索的优化
广度优先搜索比较容易优化，运行时间往往比深搜短一些（不过内存占用比深搜大得多）。另外，广搜有时可以清晰地反映搜索深度。
若上面的八数码问题改为“现要求找出一种方法，使呈现目标构型经过的对调步数最少”，则用广搜更好。
广搜常用的优化方法：
哈希表法——记录队列中已有节点，用于判断是否需要扩展节点。
A*算法——构造估价函数。
双向广度优先搜索——从源节点、目标节点一起开始搜索。
由于NOIP提高组近年来几乎不出搜索题；可用搜索的题目，由于搜索时间复杂度太高，数据规模太大，搜索只能得部分分数。加之搜索思路较简单，搜索法这里不再详细叙述。若想了解，大家可以用搜索引擎搜索。
本章无附件
本文由 最后的叶子 创作，转载或引用前请联系我们。
相关文章：
[...] NOIP实用算法 3.搜索 [...]