广度优先搜索(2)

产生子结点入栈；

if 子结点是目标结点 then 输出 else p:=true； else

if j>=max then 回溯 p:=false； endif；

until p=true； until step=0； 回溯过程如下： Procedure BACK； step:=step-1；

if step>0 then 栈顶结点出栈 else p:=true；

例如 八数码难题--已知８个数的起始状态如图1（ａ），要得到目标状态为图1(ｂ）。 ２ ８ ３ １ ２ ３ １ ６ ４ ８ ■ ４ ７ ■ ５ ７ ６ ５ （ａ） （ｂ） 图 1

求解时,首先要生成一棵结点的搜索树，按照深度优先搜索算法，我们可以生成图1的搜索树。图中，所有结点都用相应的数据库来标记，并按照结点扩展的顺序加以编号。其中，我们设置深度界限为５。粗线条路径表示求得的一个解。从图中可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，回溯一步，再继续往下搜索，直到找到目标状态或OPEN表为空为止。

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科广度优先搜索(2)全文阅读和word下载服务。