跳马问题的广度优先搜索

《跳马问题的广度优先搜索》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、跳马问题的广度优先搜索1、问题描述找出国际象棋棋盘M*N上的一个骑士（马）从一个位置经过最少步数到达终止位置的路径。2、问题分析及原理（简述）在国际象棋中，棋盘数是M*N,马（骑士）的合法走法是：按纵向或是横向移动两个方格，再沿垂直的方向移动--格，但不能移出棋盘。其走法和中国象棋中的“马”的走法相似。故，任一方格上的马至多有8种走法。假定马的初始位置在1处，为了使马快速到达指定的点，求其最短距离。注意：走过的点就不能再走了。为了简化问题，我们假设棋盘数为3*3。马初始位置在1处，目标位置为4。对已出现的位置，不再对其搜索。1234567

2、89经过分析，可画出其状态空间图:广度优先搜索：设置两个空表，分别是open()和closed。表。首先令表open()={l},closed()={}。在求解最短路径时两个表的内容依次是：1)open()={l};closed()={}2)open()={6,8};closed()={l}3)open()={8,7};closed()={6,l}4)open()={7,3}；closed()={8,6,l}5)open()={3,2};closed()={7,8,6」}6)open()={2,4};closed()={3,7,8,6,1

3、}7)open()={4,9};closed()={2,3,7z8,6,l}===^成功。深度优先搜索：同样设置两个空表，分别是open()和closed。表。首先令表open()={l},closed()={}o在求解最短路径时两个表的内容依次是：1)open()={l};closed()={}1)open()={6,8};closed()={l}2)open()={7,8};closed()={6zl}3)open()={2,8};closed()={7/6,l}4)open()={9,8};closed()={2,7,6,1}5)o

4、pen()={4,8};closed()={9/2,7,6,l}6)open()={8};closed()={4,9,2,7,6,l}==-＞成功。所以，可以看出，深度搜索的路径并非最短路径，是不完备的。3、算法流程VI左X/V2、左/,XV7右上V34左下f/uV6右V4下V5右下Stepl从起始位置start第一个扩展Step2一次考虑“马”跳一次可到达的方格，标记并存入队列QStep3从队列取出一个结点a,做处理标记并存入队列Q1。再将所有从a结点一步可以到达的未被标记的方格勺存入到活结点队列QStep4如果Q不空并且未到达目

5、标方格finish,转step2执行。否则，结束搜索。将起点加入到open表（open表是采用队列的存储方式）在open表非空的情况下循环执行如下操作：{从open表中取一个结点a；从open表中删除a；a进入closed表；对结点a,进行上、下、左、右八个方向的扩展得到新的结点勺{如果（勺是终点）返回到达此格子的步数；如果（勺是一个新的结点，未曾出现过）将勺加入open表屮；}}4、算法实现说明建立一个队列，用于存放搜索到的位置，利用限界剪枝。解空间是一个N叉树。算法屮实现的函数：voidreaddata();voidinit(int)

6、;intsearch(int);intemptyopen();〃读入数据〃初始化〃广度优先搜索〃判栈是否为空：空：1；非空：Oolongtakeoutofopen();〃从栈中取出一个元素，并把该元素从栈中删除intcanmoveto(int’intjnt*,int*,int);intisaim(introw,intcol,intm);intused(int,int);voidaddtoopen(int,int);〃判能否移动到该方向，并带冋坐标(r,c)〃判断该点是否是目标〃判断该点是否已经走过〃把该点加入到open表算法实现的难点是队

7、列的实现和马最小移动位置坐标的输出。5、结果及输出比较结果输出的是“马”所有走过的路径，并在最后输出最小步数。例如输入起始位置11,终止位置45时，结果截图为：■注：行和列为0・5。