算法与数据结构讲义三（搜索算法）精品资料.doc

《算法与数据结构讲义三（搜索算法）精品资料.doc》由会员分享，可在线阅读，更多相关《算法与数据结构讲义三（搜索算法）精品资料.doc（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十三课 搜索算法12.0 搜索树12.1 搜索算法的基本原理12.2 广度优先搜索12.3 深度优先搜索12.4 练习12.0 搜索树引例：在一个4*4的棋盘上的左下角有一个马，按照国际象棋的规则，将这个马跳到右*上角。分析：首先建立棋盘的坐标，我们以左下角为(1,1)，以右上角、为(4,4)。按照马的移动规则，假定当前马的位置坐标为(x,y)，则移动方法有：（1）x=x+1; y=y+2（2）x=x+1; y=y-2;（3）x=x+2; y=y+1;（4）x=x+2; y=y-1;（5）x=x-1; y=y+2;（6）x=x-1; y=y-2;（7）x=x-2; y=y+1;（8）x=x-

2、2; y=y-1113223122113314424114244112332232343233234123243213244可以建立搜索树如下：图中表示：由(1,1)可以跳到(2,3)和(3,2)两个点(其它移动规则由于边界限制无法到达)；(2,3)又可以跳到(1,1)、(4,4)、(4,2)、(3,1)四个点，(3,2)可以跳达(1,1)、(1,3)、(2,4)、(4,4)四个点，。搜索树：按照数据元素的产生式规则建立起来的数据元素逻辑关系。特点：（1）数据之间的逻辑关系为一对多。 （2）每个结点数据的下一级子结点是由该结点的产生式规则生成。 （3）目标结点（答案数据）一定在搜索树中能够出现

3、。 （4）对于数据规模较大的问题，搜索树的结点将是海量的。 （5）搜索树可能是无穷无尽的（因为很多结点回重复出现）。12.1 搜索算法的基本原理：从搜索树中可以看出，一个问题从起始状态，通过穷举的方式建立起搜索树后，目标状态一定能在搜索树中出现。因此，只要建立起搜索树，就可以在其中搜索到目标状态（数据、路径、位置等）。搜索算法要解决的问题：产生式规则：由当前状态按照问题的需求和限制，生成新的状态的方法集合。搜索树的生成和存储：一般采用一边生成，一边搜索；存储方法有：集合、栈。搜索的方法：按行搜索：即从上到下，逐层搜索双向按行搜索：一边从上往下（起始状态到中间状态），一边从下往上逐层搜索（从目标

4、状态到中间状态），找到相同的中间状态即可。回朔法搜索：优先向更深层结点查找，走不通则换一条路，无法换则退回到上一层。搜索状态的减少：在生成搜索树时，对于已搜过的中间状态的再次出现，是否需要再次加入到树中重新搜索。12.2 广度优先搜索（bfs）又称宽度优先搜索，是一种从搜索树的根结点开始，沿着树的宽度遍历树的结点。如果所有节点均被访问，则算法中止。一般用于求从起始状态到目标状态所需的最少步骤数。算法过程：1、首先将根结点放入队列中。 2、从队首取出一个结点，按照产生式规则逐个生成新的结点数据，对新数据： 如果如果是目标结点，则结束算法并返回结果。 如果不是目标结点，则检查它是否已在搜索树中出现

5、过，未出现就将它作为尚未检查过的子结点加入到队列的队尾（特殊情况下，也有已出现过的结点重新入队的）。 3、重复步骤2。4、若队列为空，表示整张图都检查过了，即目标无法达到，结束算法并返回“找不到目标”的信息。 算法细化：1、 用哈希数组判断新生成的结点数据是否已出现过。2、 队列经常要多开一行，记录新结点的父亲（即该结点由上一层的哪个结点扩展而来），用于最后输出过程。3、 如数据规模过大，需要使用循环队列（后果是无法记录父亲）。算法框架：function creat(i)begin case i of 1:creat:=按照第一产生式规则生成新状态数据； 2:creat:=按照第二产生式规则生

6、成新状态数据； . . . end;end;/procedure bfs;begin join(起始状态); while not(队空) do begin 当前处理状态:=deq; for i:=第一产生式规则 to 最大产生式规则 do begin 新状态:=creat(i); if 新状态=目标状态 then begin print; exit; end else if not(haxi新状态) then begin join(新状态); haxi新状态:=true; end; end; end;end;空间复杂度：线性队列：O(最大可能状态数)循环队列：O(最大可能状态数/2)时间复杂度

7、：最差情形下，BFS必须寻找所有到可能结点的所有路径。O(最大可能状态数)完全性：广度优先搜索算法具有完全性。只要目标存在，则BFS一定会找到。但是，若目标不存在，且问题规模为无限大，则BFS将不收敛（不会结束）。适用范围：广度优先搜索是找到第一个解的算法，即距离根结点的边数最少的解。如果所有边的权值都相等（即所有产生新状态的代价相同），则这个解也是最优解。例一：将一个马从M*N的棋盘的左下角跳到右上角，需要的最少步数是多少？分析：1、用一个1.2,1.m*n的数组作为工作队列，用于存储搜索树。 2、使用m*n的二维哈希数组判重。 3、生成搜索树的同时，记录父节点的序号和新结点的层数。 4、最

8、后从目标结点向起始结点回朔，用一个栈存储回朔的中间状态。例二：在一个2n+1的一维棋盘上，有n个黑色棋子和n个白色棋子，初始状态如图：规定棋子移动规则如下：1、 如果某棋子的旁边正好为空，这枚棋子可以移动到空位置上。2、 如果某棋子的一侧有棋子，二那枚棋子的另一侧为空位置，这枚棋子可以跳过那枚棋子到空位置上。问：最少经过多少步，可以将棋盘状态变成分析：1、 用2n+1位三进制数表示状态，如初始状态为：222201111，目标状态为111102222。转化为十进制进行存储，另记录空格位置。2、 产生式规则：将棋子移动转化为空格的移动。（1） 空格向左移动（2） 空格向右移动（3） 空格向左跳动（

9、4） 空格向右跳动3、 用一个1.32n+1的哈希数组判重。例三：八数码问题。在一个的九宫中有这个数及一个空格随机的摆放在其中的格子里，如图所示。现在要求实现这个问题：将该九宫格调整为如图2所示的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。 1238476512345678图一图二分析：1、字符串表达状态，另开一变量w记录空格位置。 2、空格移动规则：（1）向下移动：w=w+3。（2）向上移动：w=w-3。（3）向左移动：w=w-1。（4）向右移动：w=w+1。 3、用穷举法判重。（将来可以用排序二叉树判重）12.3 深度优先搜

10、索（dfs）深度优先搜索是从根结点出发，沿着树的深度遍历树的结点。如果当前新产生的结点还有以此为根的下一层结点，则沿此路继续下去，直到无法再深入访问时，回朔到上一层的结点，选另一条路继续深入访问。反复此过程，直到所有结点都被访问到为止。算法过程：1、 首先将根结点放入栈中。2、 取出栈顶结点，按照产生式规则生成新的结点数据，每产生一个：检查是否是目标结点，如果是且比保存的数据更优，刷新所保存的数据。检查该结点是否已搜过，如果是且比已保存的数据更优，则刷新所保存的数据，然后该结点进栈；如没有搜过，则保存数据并进栈。3、 转第二步。4、 如果栈空，则算法结束。细化说明：1、 一般用回朔法，利用递归

11、使用系统栈。2、 哈希数组不仅用于判断新结点是否出现过，还用于保存到达该结点时的中间数据。算法框架：procedure dfs(结点数据);var i:integer;begin for i:=产生式规则一 to 最大产生式规则 do begin 新结点数据:=creat(i); if (新结点数据没有搜到过)or(新结点数据虽已搜过但本次搜索结果更优) then begin更新新结点搜索结果;dfs(新结点数据); end;end;procedure dfs(结点数据);var i:longint;beginfor i:=1 to 最大产生式规则 dobegin新结点:=creat(i);i

12、f 新结点是目标结点 thenbegin传回新结点;t:=true;exit;end;if 新结点更优 thenbegin更新新结点数据;dfs(新结点);if t then exit;end;end;end;空间复杂度：O(最大状态数) （主要用于存储各结点搜索结果）时间复杂度：O(最大产生式规则数最大状态数)深度优先搜索的理论依据是建立在穷举基础上的，所以时间是几何级数级的，其优化剪枝是非常必要的，因此，深搜的主要算法设计是在于如何剪枝，如何既高效地抛弃不必要的子树，又不至于将最优解剪掉，将是深搜的最大难点。适用范围：在缺乏有效的数学方法、递推算法，不符合动态规划要求，也没有专用算法可以应

13、对，一般考虑使用深搜；得分情况将取决于优化剪枝的技巧（30-100分）。例一：有A、B、C、D、E 5本书，要分给张、王、刘、赵、钱5位同学，每人只能选1本。每个人都将自己喜爱的书填写在下表中。请你设计一个程序，打印出让每个人都满意的所有分书方案。 张00110 王11001 刘01100 赵00010 钱01001分析：1、朴素的穷举法：产生5本书的所有全排列，共有5！=120个，逐个检查各种排列是否符合所有人的要求，符合则输出，否则丢弃。穷举法的改进：例如产生一个全排列12345时，第一个数1表示将第一本书给小张。但从表中可以看出，这是不可能的，因为小张只喜欢第三、第四本书。也就是说，X

14、X X X这一类分法是不符合条件的。由此使我们想到，如果选定第一本书后，就立即检查一下是否符合条件，当发现第一个数的选择不符合条件时，就不必再产生后面的4个数了，这样做可以减少很多的运算量。换句话说，第一个数只在3和4中选择，这样就可以减少35的运算量。同理，在选定了第一个数后，其他4个数字的选择也可以用类似的方法处理，即选择第二个数后，立即检查是否符合条件。例如，第一个数选3，第二个数选4后，立即进行检查，发现不符合条件，就另选第二个数。这样就又把34XXX一类的分法删去了，从而又减少了一部分运算量。开始张钱赵王刘王刘王张王钱王赵王刘赵王刘张王刘钱王钱张王钱刘王钱赵王刘张赵王刘张钱王钱张赵王

15、钱张刘王钱赵张王钱赵刘王刘张赵钱3、 深搜法：建立如上搜索树，每一层分发一本书，未向下扩展的结点为当前层已不合理，故剪去。参考程序：program dfs1;const a:array1.5,1.5of boolean=(false,false,true,true,false), (true,true,false,false,true), (false,true,true,false,false), (false,false,false,true,false), (false,true,false,false,true);var outf:text; c:array1.5of integer;

16、 hx:array1.5of boolean;/procedure print;var i:integer;begin for i:=1 to 5 do case ciof 1:write(outf,张); 2:write(outf,王); 3:write(outf,刘); 4:write(outf,赵); 5:write(outf,钱); end;end;/procedure dfs(n:integer);var i:integer;begin for i:=1 to 5 do if (ai,n)and(not(hxi) then begin cn:=i; if n=5 then print

17、; hxi:=true; dfs(n+1); hxi:=false; end;end;/begin assign(outf,dfs_1.out); rewrite(outf); dfs(1); close(outf);end. 例二：跳马问题:在半张中国象棋盘上（5*9），有一匹马自左下角往右上角跳，今规定只许往右跳，不许往左跳。编程计算共有多少种不同的跳行路线，并将路线打印出来。 例三：0100001010000000111000010表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。 例四：有一个m*n的滑雪场，请找出最

18、长的滑雪道。比如：24 40 20 30 28 44 33 35 20 18 30 40 40 35 22 15 13 20 30 35 25 20 12 18 28 40 30 10 11 20 15 30 12 15 20 12从第一排开始下滑，只能向上、下、左、右四个方向，且下一个区域的高度必须低于当前区域的高度，找出一条滑动距离最长的路径，可以在任何区域停止。12.4 习题：1、营求（save）【问题描述】铁达尼号发出了求救信号。距离最近的哥伦比亚号收到了信号，必须尽快赶到那里。通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成nn个比较小的单位，其中用1标明的是陆地，用0标

19、明的是海洋。船只能从一个格子移到相邻的四个格子。为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。 【输入格式】第一行为n，下面是一个nn的0，1矩阵，表示海洋地图。 最后一行为四个小于等于n的整数，分别表示哥伦比亚和铁达尼号的位置。 【输出格式】哥伦比亚号到达铁达尼号的最短距离，答案精确到整数。【输入样例】save.in 3 001 101 1001 1 3 3 【输出样例】save.out 4 【数据范围】n=1000 2、硬币翻转（coin） 00000000000000*0000000*00*0000000*00*000*000*0*00*0*0*00*00*00*0*000*00

20、00*00000*000000000000【问题描述】在桌面上有一排硬币，共n枚，每一枚硬币均为正面向上。现在要把所有的硬币翻转成反面向上，规则是每次可翻转任意n1枚硬币（正面向上的翻转成向下，向下的翻转成向上）。求一个最短的操作序列（将每次翻转n1枚硬币定为一次操作）。 【输入格式】只有一行，包含一个自然数n（n为不大于100的偶数） 【输出格式】第一行包含一个整数s，表示最少需要的操作次数。接下来s行每行分别表示每次操作后桌上硬币的状态（一行包含n个整数（0或1），表示每个硬币的状态，0正面向上，1反面向上，不允许出现多余的空格）。对于有多种操作方案的情况，则只需输出一种。 【输入样例】c

21、oin.in4 【输出样例】coin.out40111110000011111 3、闭合曲线面积(area)【问题描述】编程计算由“*”号围城的下列图形的面积。面积计算方法是统计*号所围城的闭合曲线中水平线和垂直线交点的数目。如下图所示，在1010的二维数组中，有*围住了15点，因此面积为15。【输入样例】area.in 0000000000000011100000001001000000010010001000101001010100100100110110001000010000011111000000000000【输出样例】area.out15 4、细胞（cell） 【问题描述】一矩形阵

22、列由数字09组成，数字19代表细胞，细胞的定义是沿细胞数字上下左右如果还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。 如阵列： 0234500067 103456050020456006710000000089有4个细胞。 【输入格式】第一行为整数m，n，接着m行，每行n个数字 【输出格式】细胞的个数 【输入样例】cell.in 4 10 0234500067 1034560500 2045600671 0000000089 【输出样例】cell.out 4 5、最少转弯问题（turn） 【问题描述】给出一张地图，这张地图被分为nm（n，mn)，现在允许用量杯从水缸里取水或将水倒回水缸里

23、，而且两个量杯中的水也可以相互倾倒，试设计计算机程序求出在m升的量杯中准确量得k升(Nknm)所需的最少操作步数。 (每一个取水或倒水都算一个操作步数)【输入文件】ls.in仅一行，三个数，分别为m,n,k。【输出文件】ls.out仅一行，为最少步数。【样例数据】【输入】4 3 2【输出】6N8、 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 43#9865#045+8468#6633其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。现在，我们对问题做两个限制：首先，我们只

24、考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。如果这个算式是N进制的，我们就取英文字母表午的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1)。输入数据保证N个字母分别至少出现一次。BADC +CRDADCCC上面的算式是一个4进制的算式。很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算

25、式成立。输入数据保证有且仅有一组解，- 输入文件输入文件alpha.in包含4行。第一行有一个正整数N(N=26)，后面的3行每行有一个由大写字母组成的字符串，分别代表两个加数以及和。这3个字符串左右两端都没有空格，从高位到低位，并且恰好有N位。- 输出文件输出文件alpha.out包含一行。在这一行中，应当包含唯一的那组解。解是这样表示的：输出N个数字，分别表示A，B，C所代表的数字，相邻的两个数字用一个空格隔开，不能有多余的空格。- 样例输入5ABCEDBDACEEBBAA- 样例输出1 0 3 4 2- 数据规模对于30的数据，保证有N10；对于50的数据，保证有N15；对于全部的数据，

26、保证有N=26。附录资料:不需要的可以自行删除 libxml2应用实例Libxml2 是一个xml的c语言版的解析器，本来是为Gnome项目开发的工具，是一个基于MIT License的免费开源软件。它除了支持c语言版以外，还支持c+、PHP、Pascal、Ruby、Tcl等语言的绑定，能在Windows、Linux、Solaris、MacOsX等平台上运行。功能还是相当强大的，相信满足一般用户需求没有任何问题。二、 Libxml2安装：一般如果在安装系统的时候选中了所有开发库和开发工具的话(Fedora Core系列下)，应该不用安装，下面介绍一下手动安装： 1) 从xmlsoft站点或ft

27、p(ftp.xmlsoft.org)站点下载libxml压缩包(libxml2-xxxx.tar.gz)2) 对压缩包进行解压缩 tar xvzf libxml2-xxxx.tar.gz3) 进入解压缩后的文件夹中运行 ./configure -prefix /home/user/myxml/xmlinst(此处为待安装的路径)或者直接使用 ./configure make make install 4) 添加路径 export PATH=/home/user/myxml/xmlinst/bin:$PATH 说明：为了结构清晰，最好将libxml2不安装在解压目录中。安装完成后就可以使用简单的

28、代码解析XML文件，包括本地和远程的文件，但是在编码上有一些问题。Libxml默认只支持UTF8的编码，无论输入输出都是UTF-8，所以如果你解析完一个XML得到的结果都是UTF8的，如果需要输出GB2312或者其它编码，需要ICONV来做转码(生成UTF8编码的文件也可以用它做),如果系统中没有安装iconv的话，需要安装libiconv。 1) 下载libiconv压缩包(例如libiconv-1.11.tar.gz) 2) 对压缩包进行解压缩tar xvzf libiconv-1.11.tar.gz 3) 进入解压缩后的文件夹中运行 ./configure make make insta

29、ll三、关于XML：在开始研究 Libxml2 库之前，先了解一下XML的相关基础。XML 是一种基于文本的格式，它可用来创建能够通过各种语言和平台访问的结构化数据。它包括一系列类似 HTML 的标记，并以树型结构来对这些标记进行排列。例如，可参见清单 1 中介绍的简单文档。为了更清楚地显示 XML 的一般概念，下面是一个简化的XML文件。清单 1. 一个简单的 XML 文件 root delete 10清单 1 中的第一行是 XML 声明，它告诉负责处理 XML 的应用程序，即解析器，将要处理的 XML 的版本。大部分的文件使用版本 1.0 编写，但也有少量的版本 1.1 的文件。它还定义了

30、所使用的编码。大部分文件使用 UTF-8，但是，XML 设计用来集成各种语言中的数据，包括那些不使用英语字母的语言。接下来出现的是元素。一个元素以开始标记 开始(如 )，并以结束标记 结束(如 )，其中使用斜线 (/) 来区别于开始标记。元素是 Node 的一种类型。XML 文档对象模型 (DOM) 定义了几种不同的 Nodes 类型，包括:Elements(如 files 或者 age)Attributes(如 units)Text(如 root 或者 10)元素可以具有子节点。例如，age 元素有一个子元素，即文本节点 10。XML 解析器可以利用这种父子结构来遍历文档，甚至修改文档的结构

31、或内容。LibXML2 是这样的解析器中的其中一种，并且文中的示例应用程序正是使用这种结构来实现该目的。对于各种不同的环境，有许多不同的解析器和库。LibXML2 是用于 UNIX 环境的解析器和库中最好的一种，并且经过扩展，它提供了对几种脚本语言的支持，如 Perl 和 Python。四、Libxml2中的数据类型和函数一个函数库中可能有几百种数据类型以及几千个函数，但是记住大师的话，90%的功能都是由30%的内容提供的。对于libxml2，我认为搞懂以下的数据类型和函数就足够了。1）内部字符类型xmlCharxmlChar是Libxml2中的字符类型，库中所有字符、字符串都是基于这个数据类

32、型。事实上它的定义是：xmlstring.htypedef unsigned char xmlChar;使用unsigned char作为内部字符格式是考虑到它能很好适应UTF-8编码，而UTF-8编码正是libxml2的内部编码，其它格式的编码要转换为这个编码才能在libxml2中使用。还经常可以看到使用xmlChar*作为字符串类型，很多函数会返回一个动态分配内存的xmlChar*变量，使用这样的函数时记得要手动删除内存。2） xmlChar相关函数如同标准c中的char类型一样，xmlChar也有动态内存分配、字符串操作等相关函数。例如xmlMalloc是动态分配内存的函数；xmlFree是配套的释放内存函数；x