宽度优先搜索(BFS)

宽度优先搜索引例1,12,33,21,54,41,32,45,32,53,44,55,5(1,1)(1,3)(1,5)(2,3)(2,4)(2,5)(3,2)(3,4)(3,5)(4,4)(4,5)(5,3)(5,5)11233215351324445325344555跳马搜索树（解答树）法3——BFS(宽度优先搜索)需引入数据结构——队列宽度优先搜索队列基本概念(queue)队列是限定在一端进行插入，在另一端进行删除的特殊的线性表。像食堂排队买饭，后来的人排在队尾（插入），队头上的人买完饭后出队（删除）。所有需要进队的数据项只能从队尾进入；所有需要出队的数据项只能从队头离开。先入队的元素先出队，这种表又称为先进先出表（FIFO表---firstinfirstout）。队列可用数组表示，在队列运算中要设两个指针：队头指针--------head

队尾指针--------tail假设我们约定:(1)head指向队列第一个元素的前一个单元;(2)tail指向队列最后一个元素;如下图状态：head=0;tail=5;显然，队列元素个数：n=tail-head;0123456123345671、初始化：head=tail=02、元素入队：tail++;q[tail]=data;01234560123456123、元素出队：head++;data=q[head];012345613124、判断队列空否：head>=tail?或元素个数为0否：tail-head==0?非空：head<tail012345612131617BFS框架1（仅供参考）int

bfs(){

队列初始化;

初始状态入队; while(队列不空) {

获取队头状态s;弹出队头状态s;

if(s是目标状态)

处理目标状态;

for(k=1;k<=扩展规则总数;k++)

{

利用扩展规则k扩展出s的子状态s’;

if(状态s’合法)

子状态s’入队;

} } return0;}BFS框架2（仅供参考）队列实现方法（1）用数组模拟队列，如上面的演示（2）使用C++标准模板库中的容器queue，详细用法见如下程序段：（见下页）#include<queue>………………structnode{ intx,y;//行列号}start,h,s;//声明三个状态对象queue<node>

q;//声明队列,<node>用来声明队列元素的类型intt[5][3]={{0,0,0},{0,-2,1},{0,-1,2},{0,1,2},{0,2,1}};//跳马规则,下一行是规则另外一种表示方式//inttx[5]={0,-2,-1,1,2};intty[5]={0,1,2,2,1};inthorse_bfs(){

start.x=1;start.y=1;//起始状态

q.push(start);//初始状态入队

while(!q.empty())//队列不空

{ h=q.front();q.pop();//获得队头状态后,让其出队

for(intk=1;k<=4;k++)

{

利用跳马规则k扩展出h的子状态s;

if(状态s合法)

if(s是目标状态)

处理目标状态;

else

q.push(s);//s状态入队;

} } return0;}练习

BFS基础练习1：跳马问题、骑士集结

跳马问题基础版：跳马跳数基础版跳马问题分析该问题遍历过程可以按照马前进的步数划分成若干阶段，每一个阶段的各个状态构成遍历树的某一层。某层某状态的最优值只与上一层的某些状体有关，无后效性体现的很明显。所以考虑用动态规划。由于只允许马向右跳，在二维数组中，某个状态所依赖的上一个阶段的那些状态都在该状态的左边两列，所以我们从左到右更新每一列即可保证每个状态的最优。跳马问题：法2——动态规划阶段x：马跳x步的可达状态，即解答树中第x层的状态；状态：f(i,j)表示（起点）到（i,j）的路径数；状态转移方程：f[i][j]+=f[i-2][j-1]+f[i-1][j-2]+f[i+1][j-2]+f[i+2][j-1];(