广度优先搜索算法

广度优先搜索算法 例八数码难题 在3 3的棋盘上 摆有八个棋子 每个棋子上标有1至8的某一数字 棋盘中留有一个空格 空格周围的棋子可以移到空格中 要求解的问题是 给出一种初始布局 初始状态 和目标布局 目标状态 找到一种移动的方法 实现从初始布局到目标布局的转变 28316475 12384765 283164705 283164075 283164750 283104765 283064175 283014765 203184765 283140765 283164750 083264175 283604175 083214765 283714065 280143765 283145760 283106754 283163754 综合数据库 typenode recordch array 1 3 1 3 ofbyte si sj byte 空格的坐标 pnt dep word 父节点和深度 end Vardata array 1 2600 ofnode temp node 产生式规则 4条 空格向上 下 左 右四个方向移动生成结点的条件 1 新状态不出界 2 和已生成结点不重复ni temp si di k nj temp sj dj k withtempdobeginch si sj ch ni nj ch ni nj 0 si ni sj nj pnt head dep dep 1 end 搜索策略 BFS 框图 初始head 0Tail 0 练习 有两个无刻度标志的水壶 分别可装5升水和2升水 设另有一水缸 可用来向水壶灌水或倒出水 两水壶间 水也可以相互倾灌 已知5升壶为满壶 2升壶为空壶 问如何通过倒水或灌水操作 用最少步数能在2升壶中量出1升水来 编一程序解决问题 如图是六个城市之间道路联系的示意图 连线表示两城市间有道路相通 连线旁的数字表示路程 请编程序 由计算机找到从C1到C6的一条路径及路程总长度 要求求出经过城市最少的解和路程总长度最少的解 C6 3 4 4 8 4 9 2 2 6 4 C1 C2 C5 C4 C3 综合数据库 typenode recordcity integer 城市编号 flag setof 1 6 到根结点的路径 pnt integer 父节点 end Vardata array 1 1000 ofnode temp node 产生式规则 5条 向R R 2 6 城市移动生成结点的条件 1 城市R不在已走路径中 not Rindata head flag 2 当前城市到R有路 link x r 0 Data temp city R Data temp flag Data temp flag R Data temp pnt head 搜索策略 BFS 框图 初始head 0Tail 0 初始化INIT 初始结点入队 结点出队out temp temp1 tempchange temp Forr 2to6do 条件1and条件2 y n In temp Temp goal y n Print 打印 Exit 退出 Untilhead tail 翻币问题 有N个硬币 N 6 正面朝上排成一排 每次将5个硬币翻过来放在原来位置 直到最后全部硬币翻成反面朝上为止 编程让计算机找了步数最少的翻法 并把翻币过程及次数打印出来 用O表示正面 表示反面 综合数据库 typenode recordr integer 由父节点翻了几个正面朝上的硬币得到当前状态 num integer 当前状态中硬币朝上的个数 pnt integer 父节点位置 end Vardata array 1 1000 ofnode temp node 产生式规则 6条 即翻R个 R 0 1 2 3 4 5 正面朝上的硬币生成结点的条件 1 当前状态有多于R个正面朝上的硬币M R M表示当前结点正面朝上硬币的个数 否则出现负数 2 当前状态有多于5 R个反面朝上的硬币N M 5 R N表示硬币总数 例如当全部是正面时 R只能取5 不能取0 4 这时N M 只有R 5时 不等式才成立 3 当前状态已存在状态不重复新结点正面朝上硬币个数 M R 5 R 搜索策略 BFS 框图 初始head 0Tail 0 初始化INIT 初始结点入队 结点出队out temp1 temp temp1change temp