搜索的基础

这道题，我们首先看来就是一个经典的 N 皇后问题。还有的是这道题 先定了算法，只能采用回溯算法。N 皇后有它的构造方法，但是不适用。所以我 们来看如何就此问题运用最一般的方法求解。 我们对每一个限定条件进行分析。由于每一行都不能有两个跳棋，而跳棋有 N 个，所以每一行必有一个跳棋。由于它是要求每一行中跳棋的列，所以我们只 需搜索每一个行就可以了。根据分析，横轴我们已经不需要考虑，纵轴一共有 N 条，＼型轴 2N-1 条，／型轴也有 2N-1 条。 然后我们可以递归求解。如果符合条件，就可以把这个棋子放上去，三条轴 都须记上；当回溯的时候，就必须把它撤除，然后求得总数。 但是这种方法对于 N=13 时有致命弱点——慢！经过测试，大约需要 2 秒 多才能出解。这个在时间上是承受不了的。这道题有个特性是值得我们利用的， 那就是对称性。也就是说，需要搜 N，我们只需搜 N 的一半。比如 13，我们只 需搜到 6，然后根据对称性把搜得的结果乘以 2，然后再加上搜到的 7 的结果。 这样就轻松剪掉大约一半。 然后我们就有了解题的步骤：先搜到三个解—不记状态重新搜—输出。 这道题还有一个特性，那就是旋转。通过旋转还可以剪掉四分之一，但是似 乎很麻烦，所以笔者没有去试验过。 关于此题的其他方法，详见其他书籍（比如启发式修补法《算法艺术与信息 学竞赛》P195）。 [例题 5] 骑士的游历 1、2 设有一个 n*m 的棋盘，如下图，在棋盘上任一点有一个中国象棋马， 马走的规则为：1.马走日字 2.马只能向右走 即如下图所示: 任务 1:当 N,M 输入之后,找出一条从左下角到右上角的路径。（NOIP T97-3） 任务 2:如果是 n*n 的棋盘，取消马只能向右走的条件，找出一条路径使马 能够不重复地遍历每一个点。（《竞赛例题解析》） 1.题目也就是说，马能够朝着四个方向前进。而题目要求的是一条路径，所 以这道题是经典的深度优先的回溯算法。我们把四个方向用数组记录下来，然后 就可以开始先用第一种方向生成一条路径，然后回溯，直到有一次点停留在目标 顶点为止，输出路径。本题需要注意的是越界的判断与处理。 2.现在马摆脱了束缚，可以朝着八个方向走了。我们可以上小题所用的方法 来处理这个问题。在这个问题中，我们所要研究的不仅仅是到达一个点，而是遍 历棋盘。但是用哈希表判断是否到过的记录很麻烦，所以我们只要记录步数就可 以了，直到走过 步为止。我们回溯之前，要先建立一张空棋盘，然后判断2 1n − 第 12 页 共 25 页 Administrator 高亮 Administrator 高亮 Administrator 高亮 Administrator 高亮 Administrator 高亮 搜索基础 2006/01/23 版 By XT 要达到的是否是已经到过的，如果是则回溯，反之记录下来。最后输出这张棋盘 就可以了。 [例题 7] 卫星照片（USACO Contest NOV05） FJ 给他的农场买了 W*H 像素的卫星照片，希望找出最大的“连续的”（互相 连接的）牧场。任何一对像素，一个像素如果能横向的或纵向的与属于这个牧场 的另一个像素相连，这样的牧场称作是连续的。 每一张照片都数字化的抽象了，牧场区显示为“*”，非牧场区显示为“.”。 下面是一个 10*5 的卫星照片样例： ..*.....** .**..***** .*...*.... ..****.*** ..****.*** 这张照片显示了大小分别为 4、16、6 个像素的连续牧场区。帮助 FJ 在他的 每张卫星照片中找到最大的连续牧场。 在这里，我们介绍一种方法，称为 FloodFill。 FloodFill 是一种简单的染色法，通常译为种子填充法，一般用来求连续区 域的面积等。我们在这里先介绍一下这种方法。 FloodFill 可以有 2 种方法实现。 1. DFS。 使用普通 DFS 架构。先从一个点出发，向相连的方向（一般是四周）探 寻，如果四周有相连的点，则继续递归探查下一个点的四周方向。不过 这个需要避免的是搜索的重复，避免陷入死循环。 2. BFS。 使用普通 BFS 架构（下面会讲）。从一个点出发，向相连的方向扩展节 点。这种方法有效避免了搜索的重复，且 BFS 适用范围较广（比如限制 步数等），是可以推荐的。但是 BFS 编程比 DFS 略繁。 在这道题中，我们采用 DFS 来实现 FloodFill。 我们所需要做的一点细节处理是，每一个牧场区搜索到之后，就可以擦去， 以避免搜索重复和死循环。 [例题 8] 房间问题（IOI94） 图示出了一张建筑平面图，编程计算 1、该建筑中有多少个房间； 2、最大的房间有多大； 3、拆除建筑中的某一堵墙，以形成一个尽可能大的房间。指出该墙。 该建筑分成ｍ*ｎ个方块（m≤50，n≤50），每个方块可有 0～4 堵墙（0 表 示无墙）。 这道题也是典型的 FloodFill。 这里的 FloodFill 也是可以用 DFS/BFS 做的。为了避免重复计算，我们可 以用一个二维数组记录是否探查过这个地方，分成的是第几个房间。 第 13 页 共 25 页 搜索基础 2006/01/23 版 By XT 我们在 FloodFill 中就可以完美解决第 1、2 问，接下来就是第 3 个问题了。 我们可以枚举每一条边，来试验是否拆除的面积比原先记录的大（两边面积 之和）。这里我们只需要用到穷举。 我们在这里能够采用 FloodFill 作为架构。试想，如果把 FloodFill 推广到 无向图、有向图呢？有兴趣的读者可以自行研究，此处不再赘述。 [例题 9] 谷仓安全保护（USACO Contest NOV05） FJ 给谷仓安装了一个新的安全系统，并且要给牛群中的每一个奶牛安排一 个有效的密码。一个有效的密码由 L（3 <= L <= 15）个小写字母（来自传统的 拉丁字母集'a'...'z'）组成，至少有一个元音（'a', 'e', 'i', 'o', 'u'）， 至少两个辅音（除去元音以外的音节），并且有按字母表顺序出现的字母(例如， 'abc'是有效的，而'bac'不是) 。 给定一个长度 L和 C个小写字母，写一个程序，打印出所有的长度为 L、能 由这些字母组成的有效密码。密码必须按字母表顺序打印出来，一行一个。 这道题可以用比较基础的 DFS 回溯解决。 我们可以用一个字符串来当作答案数组（一个比较巧妙的方法），然后层层 递归产生新的答案。当深度到达 L 时，判断是否满足元、辅音的要求，再输出。 然后回溯（PASCAL 中每一次回溯要去掉“尾巴”，C/C++由于语言优势不必 去除），以避免重复运算浪费时间。 这道题具体的搜索方法与前面我们所讲的一些题目别无二样，可见搜索算法 的通用性很强。由于这道题比较简单，在此也不详细说明了。 [例题 10] 水碗（USACO Contest JAN06） 有 20 个碗，正反状态用 0、1 表示（正=0，反=1），给出一组碗的状况，要 求用最少的操作次数使碗全部朝正面。一次操作就是以一个碗为中心，翻转它的 左边、右边以及它自己。（如果一个碗的左（右）边没有则不需要翻转这个碗的 左（右）边） 这道题拿到，需要一些敏锐的观察力。我们可以进行一些位处理。首先，我 们可以把 20 个碗的 0、1 值从二进制转化为一个长整数。可以发现，这个长整 数的范围在 0..1048575 之间，因此共 220种状态。这为我们下文的搜索做好了 铺垫。 我们转换完毕，然后我们考虑怎样从一个状态值翻动以产生新的状态值。我 们考虑多种位操作。其中异或（Pascal 中是 xor，C/C++中是^）操作无疑是 最好的。我们可以举个例子来说明怎么样翻转。 就以样例数据作为例子。我们把原状态转化为二进制。 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 3484 然后，我们假设要以左起第三个为中心翻转。则做异或运算： 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 3484 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 0 1 0 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 3474 是不是很神奇呢？我们可以把每一个点为中心翻转的异或操作的数保存起 来。产生规则： 第 14 页 共 25 页 搜索基础 2006/01/23 版 By XT 3（i=1） 7（i=2） Mask[i]= Mask[i-1]*2（3<=i<=19） 786432（i=20） 万事俱备，我们考虑怎么样搜索。我们首先想到的可能是 BFS。但是考虑 到以每一个点为中心翻 2 次等于不翻，因此我们考虑到 DFS 可能也可以。具体 框架不再叙述。 我们分析一下它们各自的时间效率。 DFS是稳定的，因为它不能直接求出最优解，因此我们必须遍历搜索树。每 一次运算稳定于运算 220次。（平均时效 0.077s） BFS时间效率差大，最少它一次就能够求出解，但是在队列中每一个节点必 须先扩展 20 次（也就是做 20 次运算），然后才能判重。因此当最不利情况下， BFS时效低，至多运算可达到 20*220次。根据计算得最不利时效可达到 1.54s。 而时限是 1s 的，但是极端数据也估计是不存在的。（处理得当的 BFS 对于 最大数据是 0.983s，处于危险边缘）我们经过如此的分析，还是推荐大家采用 DFS。 习题： 1. 《文件匹配》（NOI97）（*） 2. 《智慧珠游戏》（NOI2005）（*） 3. 《算符破译》（NOI2000）（**） 3.广度优先搜索 广度优先搜索（Breadth First Search），是一种与深度优先搜索不同的搜 索。这种搜索方法的通性是一般出现在最少多少步的情况。这种方法由于它搜索 顺序的特殊，使广度优先搜索能够保证搜到的是最小的。 还是上述的一棵树，比如我们要求找到 5 的最少步数。我们按层遍历，找 的顺序是根-1-2-3-4-5，是 3 步。而 DFS 的顺序则是根-1-3-6-7-8-4-2-5， 需要遍历一圈才能够确定最少步数，即使找到了 5 也需要遍历整棵树。也就是 说，BFS 其实是一种找出最优解的方法，而 DFS 则不是——只能找出一条路径， 但不能保证最优。 但是 DFS 能够以递归的方式或者别的方式轻松进行（不包括递归死循环状 态），而 BFS 似乎实现麻烦。我们可以以一种很常见的方法去实现它，那就是队 列。我们可以从头扩展，按照队列 FIFO（First In First Out）的顺序加入到队 尾。BFS 一般需要判断重复，如果是重复则不添加如队尾，这样有时候可以减 少处理的数据。判断重复一般有 2 种方法：从头搜节点与 HASH 表。前者时间 耗费巨大，后者空间耗费巨大。 判重、存节点导致了 BFS 有一些巨大的缺点。但是 BFS 不失为一种优秀的 搜索方法，我们用例题来证明。 [例题 1] 救援行动（TOJ1051 By AngelForYou） Angel 被传说中神秘的邪恶的 Moligpy 人抓住了！他被关在一个迷宫中。迷 宫的长、宽不超过 200。迷宫中有不可以越过的墙以及监狱的看守。Angel 的朋 第 15 页 共 25 页 搜索基础 2006/01/23 版 By XT 友带了一些救援队来到了迷宫中。他们的任务是：接近 Angel。我们假设接近 Angel 就是到达 Angel 所在的位置。假设移动需要 1单位时间，杀死一个看守也 需要 1 单位时间。到达一个格子以后，如果该格子有看守，则一定要杀死（否则 会死的很难看的……只见那个看守开了 9 倍狙镜……）。交给你的任务是，最少 要多少单位时间，才能到达 Angel 所在的地方？（只能向上、下、左、右 4 个方 向移动） 本题有两种方法：由救援队出发去搜与由 Angel 出发倒找救援队（这变成 谁救谁了？似乎救援队被困^_^）。这两种方法的好坏不能比较（完全看数据）， 只是由于数据的关系（传说有数据错误，有两支救援队），我们只能采用后者的 方法。 我们可以首先根据数据建图，然后从 Angel 出发，向四个方向探索，然后 建队列。由于位置一共只有 200*200=40000 种，所以我们只需要有数组模拟 链表，态做一个队列，然后由列表扩展。 应该说本题不难，但是请采用由 Angel 出发倒找救援队的方法才能 AC。（这 个是不是给我们提供了反向 BFS 的一种思路呢？） [例题 2] 瑰丽华尔兹（NOI2005） 题目太长，略。请到http://www.noi.cn看题目。 本题的做法是动态规划（Dynamic Programming），效率很高，但是 这里我们要介绍的是 BFS 算法。 算法的实质是求出每一个时间内是否走动而求出最长的不违反规定的时间。 所以我们可以用宽度优先来求出。作者比较推崇使用链表。我们可以新建一个队 列，做出起始，然后依次往后推出一步。由于没有无解，故可以不必判断重复， 其实并没有重复不重复可言。这种方法不是很好，算法时间复杂度是 O(2n)， 只能过掉 1 组数据。 我不推荐这种做法，若要正确解此题，请使用动态规划。 [例题 3] 倒水问题（经典问题） 有 2个没有刻度的杯子，容积分别是 V1、V2，另有一个无限大的水缸，里面 有无限多水。对这两个杯子可以进行如下操作： 1、从水缸里往一个杯子加满水； 2、把一个杯子里的水全部倒进水缸； 3、从一个杯子往另一个杯子里倒水，直到另一个杯子满或一个杯子空为止。 现在我们需要通过一定顺序的操作，使杯子 1、杯子 2或杯子 1+杯子 2中的 水的体积是 V3。（V1、V2、V3，0＜V1、V2＜2^7，0＜V3＜2^8） 这道题很经典的算法是 BFS。我们必须从开始状态推出后面状态。 有每一种状态，可以得出 6 种状态：（1）甲杯装满水；（2）乙杯装满水； （3）甲杯倒空水；（4）乙杯倒空水；（5）甲->乙；（6）乙->甲。其中（5）（6） 必须判断是一个先倒空还是一个先倒满。 在这里面只有 128*128=16384 种状态，所以我们设计 HASH，为 P(I,J)=128*I+J 第 16 页 共 25 页 搜索基础 2006/01/23 版 By XT 于是我们用静态数组模拟队列，用 HASH 来进行判断，来进行 BFS。 [例题 4] 麻将游戏（SGOI） 在一种"麻将"游戏中，游戏是在一个有 W*H 格子的矩形平板上进行的。 每个格子可以放置一个麻将牌，也可以不放（如图所示）。玩家的目标是将 平板上的所有可通过一条路径相连的。两张相同的麻将牌，从平板上移去。最后 如果能将所有牌移出平板，则算过关。 这个游戏中的一个关键问题是：两张牌之间是否可以被一条路径所连接，该 路径满足以下两个特性： 1. 它由若干条线段组成，每条线段要么是水平方向，要么是垂直方向。 2. 这条路径不能横穿任何一个麻将牌 (但允许路径暂时离开平板)。 这是一个例子： 在（1，3）的牌和在(4, 4)的牌可以被连接。(2, 3)和(3, 4)不能被连接。 你的任务是编一个程序，检测两张牌是否能被一条符合以上规定的路径所连 接。 这道题是不难的 BFS。 读入数据后，我们可以先构造两个外框——内外框是可以通行的，最外框是 不可通行的。这样简化了问题本质。然后有一种方法——一路向外直接往外扩展 （似乎可以节省时间？），往队列后添加节点。这道题当然也要构造 HASH，但 是方法与上题相同。抓住了问题的本质，问题也就轻松解决了。 [例题 5] 拯救大兵瑞恩（CTSC99） 1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛， 营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但是幸 好麦克得到了迷宫的地形图。 第 17 页 共 25 页 搜索基础 2006/01/23 版 By XT 迷宫的外形是一个长方形，其在南北方向被划分为 N行，在东西方向被划分 为 M列，于是整个迷宫被划分为 N*M 个单元。我们用一个有序数对（单元的行号， 单元的列号）来表示单元位置。南北或东西方向相邻的两个单元之间可以互通， 或者存在一扇锁着的门，又或者存在一堵不可逾越的墙。迷宫中有一些单元存放 着钥匙，并且所有的门被分为 P类，打开同一类的门的钥匙相同，打开不同类的 门的钥匙不同。 大兵瑞恩被关押在迷宫的东南角，即（N,M）单元里，并已经昏迷。迷宫只 有一个入口，在西北角，也就是说，麦克可以直接进入(1,1)单元。另外，麦克 从一个单元移动到另一个相邻单元的时间为 1，拿取所在单元的钥匙的时间以及 用钥匙开门的时间忽略不计。 你的任务是帮助麦克以最快的方式抵达瑞恩所在单元，营救大兵瑞恩。 这道题目的 BFS 类型与往常所做的 BFS 类型大有不同，它属于典型的比较 简单的分层图 BFS。由于钥匙最多有 10 种，一把钥匙有得到和没有得到这两 种情况，所以我们可以得到这张图最多有 1024 种情况，也就是把这张图分成了 1024 层，在不同的情况下，我们要访问不同的图。由于一层图最多有 15*15=225 个节点，所以时空上面应该说问题不大。 首先我们根据题目的意思，按照输入文件的格式（按原题）去构造一张迷宫 图。我们采用边读边构造的方法。我们设 0 (x,y)与它 d 方向的格子互通 g[x,y,d]= -1 (x,y)与它 d 方向的格子不通 t (x,y)与它 d 方向的格子之间有 t 类门 这样可以方便我们构造迷宫地图，具体的构造方法就不详细叙述了。构造之 前，我们为了处理方便还通常在最外圈加上一圈围墙，方便判断越界的情况。 然后我们可以读入钥匙的坐标，并另外开一张地图记录钥匙存放情况。然后 这道题就已经转化为普通的 BFS 了，但是在访问节点的过程中遇到了钥匙要及 时地转化到另外的一张图上去，记得此时携带的钥匙是不同的。 [例题 6] 补丁 VS 错误（CTSC99） 一个程序总有个错误，公司经常发布补丁来修正这些错误，遗憾的是，每用 一个补丁，在修正某些错误的时候，同时会加入某些错误，每个补丁都有一定运 行时间。某公司发表了一个字处理软件，出现了 n个错误 B={b1,b2,b3,……bn}， 于是该公司发布了 m 个补丁，每个补丁的应用都是有条件的（即哪些错误必须 第 18 页 共 25 页 搜索基础 2006/01/23 版 By XT 存在，哪些错误不能存在）。求最少需要多少时间可全部修正这些错误。 （1<=n<=20，1<=m<=100）（题目叙述采用 TOJ1275 的叙述） 这道题目拿到后，我们首先想到的是动态规划的方法。仔细分析以后，就会 很容易发现，这道题目的叙述使者到题目的本质不符合动态规划的最优化递推原 理，所以不能使用动态规划。由于