资源描述：
《图的遍历和搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图的遍历和搜索算法搜索算法:利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。深度优先与广度优先深度优先的特点是在每一个多岔路口,如果能找到一条路往下走,就走,而不管别的路是否也能走下去，直到到达终点或无路可走时回溯。所以利用深度优先搜索，只要有路，总能找到，但找到的那条并不一定是最优的。广度优先的特点是在每一个多岔路口，都要把所有的路都尝试一下，直到到达终点。所以利用广度优先搜索，只要有路，也总能找到，而且一旦
2、找到，一定是最优解（也即最少步骤）。123546124563123465Dfs:Bfs:123546124563Dfs:123546123465Bfs:123645124356123645Dfs:Bfs:123645124356Dfs:123645123645Bfs:ABCEDAACABABCACDACEABCDABCEACDEACEDABCDEABCDEACDECACEDCABCDECABCDECACDECBACEDCBABCDECAABCDECAACDECBAACEDCBAABCEDvarf:text;data:array['A'.
3、.'Z','A'..'Z']ofinteger;s:string;n,m:integer;ans:boolean;begininit;main('A',1);ifansthenwriteln(f,'NO');close(f);end.procedureinit;vari:integer;ch1,ch2,ch3:char;beginforch1:='A'to'Z'doforch2:='A'to'Z'dodata[ch1,ch2]:=0;s:='A';ans:=true;assign(f,'wjx.in');reset(f);readln(
4、f,n,m);fori:=1tomdobeginreadln(f,ch1,ch2,ch3);data[ch1,ch3]:=1;data[ch3,ch1]:=1;end;close(f);assign(f,'wjx.out');rewrite(f);end;proceduremain(ch:char;step:integer);varr:char;beginforr:='A'tochr(64+n)dobeginifdata[ch,r]=1thenbegindata[ch,r]:=0;data[r,ch]:=0;s:=s+r;iflengt
5、h(s)-1=mthenprintelsemain(r,step+1);data[ch,r]:=1;data[r,ch]:=1;delete(s,length(s),1);end;end;end;procedureprint;beginwriteln(f,s);ans:=false;end;procedureprint;beginwriteln(f,s);ans:=false;end;深度优先与广度优先深度优先的特点是在每一个多岔路口,如果能找到一条路往下走,就走,而不管别的路是否也能走下去，直到到达终点或无路可走时回溯。所以利用深度优
6、先搜索，只要有路，总能找到，但找到的那条并不一定是最优的。广度优先的特点是在每一个多岔路口，都要把所有的路都尝试一下，直到到达终点。所以利用广度优先搜索，只要有路，也总能找到，而且一旦找到，一定是最优解（也即最少步骤）。产生式系统由3个基本要素组成：一个综合数据库(Globledatabase)，一组产生式规则(SettOf rules)和一个控制系统(Control System)。1．综合数据库 它是产生式系统所用的主要数据结构。它主要表示问题的状态，即初始状态、目标状态和中间状态，以及状态之间的关系等。它不是固定不变的，在
7、求解过程中，它的内容将越来越多，状态之间的关系也越来越复杂。 经常用来表示数据库的数据结构有串、集合、数组、树、表、记录、队列等。2．产生式规则 是对数据库进行操作的一系列规则。规则的一般形式是：IF条件THEN操作即满足应用的先决条件后，就对数据库实行后面的操作。3．控制策略 它规定了操作的顺序，即在什么条件下用什么规则进行操作，什么条件下停止运行，即它规定了问题求解的搜索策略和路线深度优先搜索算法深度优先搜索算法深度优先搜索法有两大基本特点:1．对已产生的结点按深度排序，深度大的先得到扩展，即先产生它的子结点
8、；2．深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”。因此用堆栈作为该算法的主要数据结构，存储产生的结点，先把产生的数入栈，产生栈顶（即深度最大的元素）子结点，子结点产生以后，出栈，再产生栈顶子结
