10122157项镇敏实验6跳马问题ok

《10122157项镇敏实验6跳马问题ok》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析实验》实验报告实验指导教师沈云付学生姓名项镇敏学号10122157序号1实验时间周三7-9节课上海大学计算机工程与科学学院2016年11月3日实验六、跳马问题问题描述：给定8*8方格棋盘，实验目的：求棋盘上一只马从一个位置到达另一位置的最短路径长。算法思想：1．简单分析，说明原理或方法依旧是最短路径问题，不过此问题用回溯法来求解释比较好的。如下：一只马在棋盘的某一点，它可以朝8个方向前进，方向向量分别是：(2,1)、(2,-1)、(1,2)、(1,-2)、(-2,1)、(-2,-1)、(-1,2)、(-1,-2)

2、。从中任选择一个方向前进，到达新的位置。在从新的位置选择一个方向前进，继续，直到无法前进为止。无法前进可能有如下原因：下一位置超出边界、下一位置已经被访问过。当马已经无法前进时，就回退到上一位置，从新选择一个新的方向前进；如果还是无法前进，就再回退到上一位置……算法复杂度分析：在任何时刻，回溯算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2h(n))或O(h(n)!)内存空间。2．给出能正确运行的程序：

3、程序代码见附录。以下是输入输出要求以及实验结果截图：输入要求：输入有若干测试数据。每组测试数据仅1行，每行上有2个方格pos1、pos2，之间用一个空格隔开，每格方格表示棋盘上的一个位置，该位置由表示列的1个字母（a-h）及表示行的一个数字（1-8）构成，如“d7”表示第4列第7行。输出要求：对输入中每行上的2个方格pos1、pos2，输出马从位置pos1跳到pos2所需的最短路径长。如“a1==>a2:3moves”表示从位置a1跳到a2所需的最少步数是3。注意：按输出样例所示格式输出，如“a1==>a2:3moves”中冒号

4、后有一个空格，再跟着所需的最少步数。实验结果实验报告要求:3．设计、调试中的问题及实验体会。回溯法，我们要知道回溯法的基本思想，以及生成问题的基本方法。在一般情况下，用递归回溯法求解问题比较好。附录：#includeusingnamespacestd;classstack{private:inta[100],b[100];intposx;public:stack():posx(0){}voidpush(intx,inty){a[posx]=x;b[posx]=y;posx++;}voidpop(int&x,i

5、nt&y){posx--;x=a[posx];y=b[posx];}boolempty(){if(posx==0)returntrue;elsereturnfalse;}};voidjump(introw,intcol,inta[8][8]){intr,c;a[row][col]=0;r=row;c=col;stackst;st.push(r,c);while(!st.empty()){st.pop(r,c);//左上角if(r>0&&c>1&&a[r-1][c-2]==-1){a[r-1][c-2]=a[r][c]+1;st.

6、push(r-1,c-2);}elseif(r>0&&c>1&&a[r-1][c-2]>a[r][c]+1){a[r-1][c-2]=a[r][c]+1;st.push(r-1,c-2);}if(r>1&&c>0&&a[r-2][c-1]==-1){a[r-2][c-1]=a[r][c]+1;st.push(r-2,c-1);}elseif(r>1&&c>0&&a[r-2][c-1]>a[r][c]+1){a[r-2][c-1]=a[r][c]+1;st.push(r-2,c-1);}//右上角if(r>0&&c<6&&a[r-

7、1][c+2]==-1){a[r-1][c+2]=a[r][c]+1;st.push(r-1,c+2);}elseif(r>0&&c<6&&a[r-1][c+2]>a[r][c]+1){a[r-1][c+2]=a[r][c]+1;st.push(r-1,c+2);}if(r>1&&c<7&&a[r-2][c+1]==-1){a[r-2][c+1]=a[r][c]+1;st.push(r-2,c+1);}elseif(r>1&&c<7&&a[r-2][c+1]>a[r][c]+1){a[r-2][c+1]=a[r][c]+1;st

8、.push(r-2,c+1);}//左下角if(r<6&&c>0&&a[r+2][c-1]==-1){a[r+2][c-1]=a[r][c]+1;st.push(r+2,c-1);}elseif(r<6&&c>0&&a[r+2][c-1]>a[r][c]+1){