资源描述：
《深度优先搜索搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、搜索算法从问题的某一种可能出发,搜索从这种情况出发所能达到的所有可能,当这一条路走到“尽头”而没达到目的地的时候,再倒回上一个出发点,从另一个可能出发,继续搜索.这种不断“倒回一步"寻找解的方法,称作"回溯法".回溯即是较简单、较常用的搜索策略,实质就是一种搜索策略.AB12345678910从A到B的路线:A---4---6---B如:找一条从A到B的路线深度优先搜索1.算法思想深度优先搜索的搜索策略是：尽可能“深”的搜索某一分支。在深度优先搜索中，对于最先发现的结点，如果还有以此为起点的未搜索边，则沿此边继续搜索下去。当结点V的所有边
2、都已经被探寻过，搜索将回溯到发现点V的那条边的始结点。重复此过程直至源结点可到达的所有结点为止。2.深度优先搜索的基本算法结构（1）递归实现。Proceduredfs_try(i);Fori:=1tomaxrdobeginif子结点mr符合条件thenbegin产生的子结点mr入栈；if子结点mr是目标结点then输出；elsedfs_try(i+1);栈顶元素出栈；End;End;1.、[问题描述]学校放暑假时，信息学辅导教师有n本书要分给参加培训的n个学生。如：A，B，C，D，E共5本书要分给参加培训的张、刘、王、李、孙5位学生，每人
3、只能选1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本，希望设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。ABCDE张YY王YY刘YY孙Y李YY输入格式：第一行一个数n（学生的个数，书的数量）以下共n行，每行n个0或1（由空格隔开），第I行数据表示第i个同学对所有书的喜爱情况。0表示不喜欢该书，1表示喜欢该书。输出格式：依次输出每个学生分到的书号。样例：输入：book.in50011011000011000001001001输出：book.out31245分析:a:array[1..maxn
4、,1..maxn]of0..1;b:array[1..maxn]ofinteger;{方案:b[i]是第i个人借第b[i]本书}book:array[1..maxn]ofboolean;{book[[i]:能否可以借第i本书,初始:true,一旦有人借了:就改为:false}算法设计:proceduretry(i:integer);{搜索第i个人可以借的书b[i]}varj:integer;beginifi=n+1then输出结果elseforj:=1tondoif第i个人可以借第j本书thenbegin记录下b[i];标记第j本数已被借
5、;try(i+1);删除书的被借标志;end;end;proceduretry(i:integer);varj:integer;beginifi=n+1thenprintelseforj:=1tondoifbook[j]and(a[i,j]=1)thenbeginb[i]:=j;book[j]:=false;try(i+1);book[j]:=true;b[i]:=0;end;end;procedureprint;vari:integer;beginfori:=1ton-1dowrite(b[i],'');writeln(B[N]);en
6、d;主程序:beginfillchar(b,sizeof(b),0);fillchar(book,sizeof(book),true);readln(n);fori:=1tondoforj:=1tondoread(a[i,j]);try(1);End.2.、[问题描述]house11.txt骑士的游历1设有下图所示的一个棋盘，在棋盘上的A点有一个中国象棋马，并约定马走的规则：1、马只向右走；2、马走“日“字。找出所有从A到B的路径。一种方法：(21)(40)(52)(60)(72)(84)1112345671231分析：1、马跳的方向：x
7、:array[1..4,1..2]ofinteger=((1,-2),(2,-1),(2,1),(1,2));4个方向横向和纵向的增量。2、记录马经过的位置坐标a:array[0..8,1..2]ofinteger;第i步所在的位置，1：横坐标2：纵坐标递归算法：proceduretry(i:integer);{搜索第i步:try(1);}varj:integer;beginforj:=1to4doif(a[i-1,1]+x[j,1]>=0)and(a[i-1,1]+x[j,1]<=8)and(a[i-1,2]+x[j,2]>=0)and
8、(a[i-1,2]+x[j,2]<=4)thenbegina[i,1]:=a[i-1,1]+x[j,1];a[i,2]:=a[i-1,2]+x[j,2];if(a[i,1]=8)and(a[i
