广度优先搜索

广度优先搜索动画广度优先搜索广度优先搜索动画2引入问题——whyqueue搜索——广度优先搜索队列的维护什么是队列？广度优先搜索动画3队列队列是限定在一端进行插入，另一端进行删除的特殊的线性表。删除的一端称为队首，插入的一端称为队尾。具体事例：排队买票，后来的人排在队尾（插入），队首的人离开（删除）。广度优先搜索动画4队列的特点线性队头读队尾写先进先出广度优先搜索动画5队列的定义静态—数组Typearr=array[1..n]ofinteger;queue=recordvec:arr;front,rear:integer;end;Varq:queue;Varqueue:arr;front,rear:integer;广度优先搜索动画6队列的基本操作操作静态数组(A,f,r)建立空队列测试队列是否为空入队(insert)出队(dele)尾插法F:=0;r:=0FrR:=r+1;a[r]:=x;Iff=0thenf:=1;X:=a[f];f:=f+1;和约定有关广度优先搜索动画7深度、广度优先搜索在搜索过程中，我们把每个状态看作是结点，把状态之间的联系看做是边，这样我们就可以得到一棵树，我们把这棵树称为“搜索树”。广度优先搜索动画8深度、广度优先搜索初始状态对应根结点，目标状态对应目标结点。问题的一个解就是一条从根结点到目标结点的路径。对“搜索树”的搜索算法类似于树的遍历，通常有两种不同的实现方法：广度优先搜索(BFS)深度优先搜索(DFS)广度优先搜索动画9广度优先搜索BFS每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层，因此也被称作“按层搜索”。广度优先搜索动画10广度优先搜索一般来说，BFS使用队列来实现。BFS一般用来求最优解。在存储数据时，除了需要存储当前状态外，还需要存储当前状态的父状态以及由父状态转换过来所执行的操作。DataOPPre广度优先搜索动画11广度优先搜索算法初始状态入队op:=1对队首状态进行操作op，得到新状态；检查此状态是否出现过，如未出现则将此状态入队；如果此状态为目标状态，则输出；如所有操作都已完成，则队首出队，否则op:=op+1，返回(3)。广度优先搜索动画12广度优先搜索算法描述ProgramBfs；初始化，初始状态存入OPEN表(即队列)；队列首指针head:=0;尾指针tail:=1；repeat指针head后移一位，指向待扩展结点；forI=1tomaxdo{max为产生子结点的规则数}beginif子结点符合条件thenbegintail指针增1，把新结点存入列尾；if新结点与原已产生结点重复then删去该结点（取消入队，tail减1）elseif新结点是目标结点then输出并退出；end;end;until(head=tail);{队列空}广度优先搜索动画13初始化LIST取消在N中结点的所有标记;标记结点s1245369781pred(1)=0next:=1order(next)=1LIST:={1}next112453697811广度优先搜索动画14在LIST中选择结点iLIST在广度优先搜索中，i是在LIST中的第一个结点12453697811next111广度优先搜索动画15如果结点i和一条可进入弧关联…LIST选择一条可进入弧(i,j)12453697811next1211标记结点jpred(j):=i2Next:=Next+1order(j):=next把j添加到LIST22广度优先搜索动画16如果结点i和一条可进入的弧关联…LIST选择一条可进入弧(i,j)124536978311next2311标记结点jpred(j):=i2Next:=Next+1order(j):=next把j添加到LIST2255广度优先搜索动画174如果结点i和一条可进入的弧关联…LIST选择一条可进入弧(i,j)124536978311next2311标记结点jpred(j):=i2Next:=Next+1order(j):=next把j添加到LIST2255343广度优先搜索动画184如果结点i和一条可进入的弧关联…LIST从LIST删除结点i124536978311next2311222553431广度优先搜索动画194选择结点iLIST在LIST上的第一个结点变成了结点i124536978311next23112225534312广度优先搜索动画2054如果结点i和一条可进入的弧关联…LIST124536978311next231222553432选择一条可进入弧arc(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST454广度优先搜索动画2154如果结点i和一条可进入的弧关联…LIST124536978311next231222553432从LIST删除结点i4542广度优先搜索动画2254选择一个结点LIST124536978311next231222553432454在LIST上的第一个结点变成了结点i5广度优先搜索动画23654如果结点i和一条可进入的弧关联…LIST124536978311next2312225534324545选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST666广度优先搜索动画24654如果结点i和一条可进入的弧关联…LIST124536978311next2312225534324545666从LIST中删除结点i5广度优先搜索动画25654选择结点3LIST124536978311next2312225534324545666结点3不和任何可进入弧关联53从LIST中删除结点i3广度优先搜索动画26654选择一个结点LIST124536978311next23122255343454666i:=44广度优先搜索动画277654如果结点i和一条可进入的弧关联…LIST124536978311next231222553434546664选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next把j添加到LIST878广度优先搜索动画287654如果结点i和一条可进入的弧关联…LIST124536978311next231222553434546664从LIST删除结点i8784广度优先搜索动画297654选择结点iLIST124536978311next23122255343454666i:=68786广度优先搜索动画3087654如果结点i和一条可进入的弧关联…LIST124536978311next231222553434546668786选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next添加j到LIST中787广度优先搜索动画31987654如果结点i和一条可进入的弧关联…LIST124536978311next231222553434546668786选择一条可进入弧(i,j)标记结点jpred(j):=iNext:=Next+1order(j):=next添加j到LIST中787999广度优先搜索动画32987654如果结点i和一条可进入的弧关联…LIST124536978311next231222553434546668786从LIST删除结点i7879969广度优先搜索动画33987654选择结点8LIST124536978311next231222553434546668786结点8不和任何可进入弧关联；从LIST中删除它787996988广度优先搜索动画34987654选择结点7LIST124536978311next231222553434546668786结点7不和可进入弧关联；从LIST中删除它787996977广度优先搜索动画35987654选择结点9LIST124536978311next231222553434546668786结点9不和可进入弧关联；从LIST中删除它787996999广度优先搜索动画36广度优先搜索动画37广度优先搜索动画38广度优先搜索动画39广度优先搜索动画40有10升油在10升的容器中，另有两个7升和3升的空容器，现要求用这三个容器倒油，使得最后在10升和7升的容器中各有5升油。[题解]三个容器可以看作三个变量C10，C7，C3，每次倒油的可能性只有如下六种情况：①C10向C7倒油②C10向C3倒油③C7向C10倒油④C7向C3倒油⑤C3向C10倒油⑥C3向C7倒油应用——倒油广度优先搜索动画41从一个容器状态（三个容器中油的容量）看，虽然有可能经过上述六种倒油的方法产生六种容器状态，但实际上这六种新产生的容器状态，许多是已经出现过的状态。例如初始状态（10,0,0）表示C10=10，C7=0，C3=0，经过上述六种倒油方法只能产生出两种新的容器状态（3,7,0）和（7,0,3）。123456789101112131415161718191037037646491912828507074343161607705250033300330031212300011223567891011121314151617C10C7C3PRE广度优先搜索动画42当倒油产生出第19个容器状态时已达到了题解的目的。这时只要根据pre中的状态号17可以回溯到第17个容器状态的pre值为15，依次可再获得13，11，9，7，5，2，1容器状态号，从而即可得到解题的倒油过程（共倒9次）。注意,从一个容器中向另一个容器中倒油,人操作是很直观的,对编程来说则必须考虑:1)有没有油可倒?2)究竟倒多少?可能要全部倒入另一容器,也可能只要倒一部分另一容器已经满了.广度优先搜索动画43例2在一个瓶中装有80毫升化学溶剂,实验中需要精确地平分成两份,没有量具,只有两个杯子,其中一个杯子的容量是50毫升,另一个是30毫升,试设计一个程序将化学溶剂对分成两个40毫升,并以最少步骤给出答案.分析：3个容器中水的初始状态为：80，0，0，生成新结点状态的方法为：将一个不空的杯子水倒入一个不满的杯子中，且结点状态不重复，直到生成目标结点为止。数据库：用数组d构成存放生成结点（杯子水状态）的队；数据p作为指向父结点的指针;t和S作为队头与队尾指针。广度优先搜索动画44结点的产生（1）将结点中不空的杯子倒入一个不满的杯子中，生成新的结点并记下父结点位置。（2）判断新结点是否已生成过，以避免死循环。（3）生成的结点若为目标结点，则输出。程序实现:typestatus=array[1..3]ofinteger;constv:array[1..3]ofinteger=(80,50,30);vard:array[1..200]ofstatus;//d数组构成队,用于存放每个结点中三个杯子的状态.p:array[1..200]ofinteger;//用于存放父结点位置t,s,i,j:integer;广度优先搜索动画45程序实现proceduredraw(f:integer);varm:array[1..20]ofinteger;i,j,k:integer;beginj:=0;whilef1do//根据之前p数组记录的父结点状态,逐个追溯直到回到开始结点,并且存入m数组,以便跟踪输出每个结点中三个杯子的状态.begininc(j);m[j]:=f;f:=p[f];end;writeln;writeln('start:',d[1,1]:3,d[1,2]:3,d[1,3]:3);fori:=jdownto1dobeginwrite('stepNo.',j+1-i,':');fork:=1to3dowrite(d[m[i],k]:3);writeln;end;writeln('end.');close(output);halt;end;广度优先搜索动画46functionexampas