搜索相关算法学案2

1、三深度优先搜索深度优先搜索所遵循的搜索策略是尽可能“深”的搜索树。在深搜中，对于当前发现的结点，若它还存在以此结点为起点而未探测到的边，就沿此边继续搜索下去。若当前结点的所有边都已被探寻过，则回溯到当前结点的父结点，继续上述的搜索过程直到所有结点都被探寻为止。深度优先搜索在树的遍历中也称作树的先序遍历。深搜递归算法：);ifdepth目标深度输出方案；深度可能决策范围doif决策i符合展开条件记录决策i；删除决策i；主程序调用：说明递归形式的程序符合思维习惯，编写起来较容易，但由于递归过程的调用借助较慢的系统栈空间传递参数和存放局部变量，故降低了执行效率。我们可以模拟递归，使用数组存放堆栈数据

2、，在管理指针和每层决策上不如递归容易编程，但一旦熟悉了程序框架，调试起来要比递归程序方便。深搜非递归算法：程序读入数据并初如化；if可以展开在中记录第一种决策；ifdepth=目标深度输出方案；endif可以选择新决策改写为新决策消除当前深度的尝试对其他变量的影响；程序终止化；例简单的背包问题。设有一个背包，可以放入的重量为。现有件物品，重量分别为，件物品中挑选若干件，使得放入背包的重量之和正好为。算法分析可以设定和和可重复的排列，或者是产生一个位的进制数。do判断目标函数表示位置，表示所放的值doifdoififv表示第个位置if若超界，一个排列完成,本次选择物品方案不成功，退出do在第个位

3、置上分别放到1ifi)判断所选物品之和是否大于等于否则处理第个位置小结深度搜索有一定固定模式，但其变种还很多，就其实质来说是“怎样构造一棵用来搜索的树(tree),然后对这棵树(tree)述的问题建立科学合理的数学模型。深搜算法要点（）边界条件：即在什）搜索范围：在当前状态下不满足边界条件的情况下，）约束条件：当前扩）恢复递归前状态：如果扩展表示当前状态，共有六种不同的倒酒容量为表示当前状态，共有六种不同的倒酒容量为的杯子为号，用三个酒杯中的酒的数量四广度优先搜索广搜在树中又叫按层次遍历。对于树而言，宽度优先搜索的思路可以描述为：访问根结点，依次访问根结点的每间复杂度是相同的，不同的仅仅在于结

4、点访问的顺序不同。有些问题上，比如求最优解，宽搜比深搜好。如倒酒问题：有三个酒杯，容量分别为、，开始时在容量为的酒杯中装满酒，另外两个酒杯为空杯，怎样用这三个酒杯以最少的倒酒次数分出的酒来？我们将三个酒杯分别编上号，容量为的杯子为号，容量为31方法，依次为从倒向，从倒向，从倒向，从倒向，从倒向，从倒向。如果用深搜，回溯的条件为当前状态在前面曾经出现过，继续搜索将成死循环。下面两个图分别描述了深搜与宽搜的全过程。入门例题：有升油在升的容器中，另有两个升和升的空容器，要求用这升和升的容器中各有输入：第行个整数，表示容器的容量；第行为油桶的初始状态；第行为油桶的目标状态。输出：倒油的次数vara:a

5、rray1.3ofinteger;每个容器的容量x:array1.1000,1.3ofshortint;存放已经出现过的状态y:array1.1000ofinteger;存放树(tree)的前缀层数,即当前倒油次数b:array1.3ofinteger;目标状态c:array1.3ofinteger;p1:integer;p2:integer;i,j,t:integer;pt:boolean;procedureinit;beginassign(input,xx1.txt);reset(input);readln(a1,a2,a3);readln(x1,1,x1,2,x1,3);读取初始状态re

6、adln(b1,b2,b3);读取目标状态close(input);end;procedureout;beginwriteln(yp1+1);halt;end;functionfind:boolean;vari:integer;beginfori:=1top2doif(c1=xi,1)and(c2=xi,2)and(c3=xi,3)thenbeginfind:=false;exit;end;find:=true;end;begininit;fillchar(y,sizeof(y),0);p1:=1;p2:=1;whilep1=p2dobeginfori:=1to3do对当前xp1状态，生成所有

7、有效分支forj:=1to3doifijthenbeginfort:=1to3doct:=xp1,t;pt:=false;ifci+cj=ajthen从i到j全部倒完begincj:=cj+ci;ci:=0;pt:=true;end;if(cj=0)and(pt=false)then只能倒一部分beginci:=ci-(aj-cj);cj:=aj;pt:=true;end;ifptthenbeginif(c1=b1)and(c2=b2)and(c3=b3)thenout;到达目标输出iffindthen判重begininc(p2);队列入列操作fort:=1to3doxp2,t:=ct;取得当前树的扩展层数,即：倒油次数yp2:=yp1+1;end;end;end;inc(p1);队列出列操作end;end.为产生子结点的规则数）BFS;初始化，初始状态存入表中：队列首指针尾指针head后移一位：指向待扩展结点doif子结点符合条件新结点入队；if新结点与原已产生的结点重复删去该结点（取消入队，减）if新结点是目标结点输出并退出；end练习给出一个由，组成的问最少经过多少次交换，可以到达另一个目标位数。例如：对于，最少经过两次交换，可以变成。练习一个农夫带着一头狼、一只羊和一捆草，要借助一条小船过河，船只能由农夫自己摆渡，并且船最多只能再装载