基于python的骑士游历问题解析

系统：windows
环境：codeblocks
语言：C++

一、需求分析

在棋盘上，骑士只能走日字（L 形）.假设骑士在（0,0），我们希望用最少的移动步数使他走到（x,y）（例如，从（0,0）到（1,1）需要两步，骑士可以移动到棋盘的负坐标处）。

要求：设计一个可采纳的启发式函数，来估计需要的最小移动步数值，保证结果足够地精确。用 A*算法和你的启发式函数来编程实现求解。结果输出详细过程。

证明你的函数是可采纳的。

二、问题重述

将路径长度规定为移动步数。
所得解路径必为哈密顿路径。
根据对称性，可以看出需要到达负坐标之后再到达目的地的路径，完全可以先到达对称处的正坐标点，再到达目的地。

如下图：

s --> t1：可以找到相应的对称点A1'；
s --> t2：可以找到相应的对称点B1'和B2'；

并且路径长度是相同的。

三、算法分析

3.1. 算法步骤

具体步骤：

把初始节点S0放入open表中，令f(S0)=0
如果open表为空，则问题无解，退出。
把open表中选取第一个节点（节点n）从open表中移到closed表中。
考察节点n是否为目标节点，若是则求得问题的解，并退出；否则继续.
如果节点n可扩展，则转6，否则转2
扩展节点n，对其后续节点集合M中的某一个节点m(xm,ym)，计算f(x,y)=g(x,y)+h(x,y) ，把open表中的节点按照f值从小到大排序。
其中g(x,y)是从S0（x0,y0）到当前状态m(xm,ym)的步数
初始条件

可根据父节点n(xn,yn)递推获得g(x,y)

h(x,y)是当前节点到目标状态T(tx,ty)的估计步数
先令

所以 h(x_n,y_n) 函数形式可写为：

为每个节点设置指向n的指针
转向第2步

3.2. 证明算法是A*

3.2.1 可采纳性

根据前人的定理，A*算法具有可采纳性，所以只需要证明本文算法为A*算法，所以只需证明两个条件：

对于评判函数

只需证明：

(1)式由于递推的关系容易知道是正确的，起点x为特例 g(x) = 0 。

对于(2)式，图上两点最短距离为曼哈顿距离dt，而L形走法每次最多走3步，而且因为是L形限制，可能会走更多的路，所以容易得到

可见该算法是A*算法，有可采纳性。

四、算法实现与优化

4.1. 相关变量的定义

4.1.1 bili类与pair 类

bili类

存储状态节点和估计函数，方便之后的open表进行比较

c++ struct bili { int x,y,l; // x,y代表横纵坐标，l代表耗估计函数f(x,y); bili() {} bili(int _x,int _y,int _l):x(_x),y(_y),l(_l) {} };

pair 类(pii)
pair
这里使用pii类是为了方便对状态（形如 (x,y) ）的管理，为了方便open表比较耗散值大小，所以写了一个bili类来重写“<”号。

c++ typedef pair<int, int> pii;

元素	功能
first	相当于x
second	相当于y
make_pair(x,y)	Construct pair object: pair

4.1.2 open表

c++ bili heap[maxn],open[maxn]; int sz = 0;

4.1.2.1 采用小根堆优化实现。

小根堆，又名最小堆，是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。

4.1.2.2 分析

如果用循环数组模拟open表，则每次都需要对数组进行排序，并且将估计耗散值最小的状态取出进行下一步操作。我会采用插入排序。

复杂度为：

而小根堆这个数据结构的功能采用堆排序的原理将一堆数据中估值最小的状态置于队列的顶端，方便取出和使用。

复杂度为：

4.1.3 closed表

c++ int g[maxm][maxm]; vector<pii> closed;

用数组g标记状态S是否已经路过，降低判断S是否已经路过时的复杂度。
closed用来存储使用过的状态，降低打印的复杂度。
判断复杂度：

打印复杂度：

总的复杂度：

4.1.4 设置指向n的指针

c++ pii pre[maxm][maxm]; //pre[x][y]表示（x,y）的上一个状态 //设置指向父节点的指针 pre[xx][yy] = make_pair(a.x, a.y);

具体实现逻辑请看代码。

4.1.5 估值函数h(x,y)

c++ int h(int x,int y) { int dt = abs(x-tx)+abs(y-ty); if (dt%3==0) { return dt/3; } return dt/3+1; }

4.1.6 打印函数

该函数存在的价值是打印每次 从open表取出父节点，扩展出子节点之后 的棋盘的状态，即可以展示每次增加了哪些子节点，具体效果请看使用说明书。

c++ void print_status(){ printf("\nboard:\nS: starting point, T: ending point;\nK : points that can be reached now, . :points that cannot be reached now.\n\n"); for (int i=0;i<m;i++){ for (int j=0;j<n;j++){ if(i==sx&&j==sy){ printf("S "); }else if (i==tx&&j==ty){ printf("T "); }else if (g[i][j]>0){ printf("K "); }else printf(". "); } printf("\n"); } printf("\nopen表:\n"); for (int i=0;i<sz;i++){ open[i] = heap[i]; } sort(open,open+sz,cmp); for (int i=0;i<sz;i++){ printf("(%d, %d) ",open[i].x,open[i].y); } printf("\nclosed表：\n"); for (int i=0;i<closed.size();i++){ printf("(%d, %d) ",closed[i].first,closed[i].second); } printf("\n"); system("pause"); }

4.1.7 其余变量解释

c++ const int maxm = 12; //棋盘最大尺寸 const int maxn = 150; //open表最大尺寸 int m,n,sx,sy,tx,ty,cnt=0; //cnt用于记录Step,比如Step 1 // m,n输入的棋盘尺寸 // sx,sy 起点, tx,ty 终点 int g[maxm][maxm]; // g(x,y) int dx[8] = { 1,2,2,1,-1,-2,-2,-1 }; int dy[8] = { 2,1,-1,-2,-2,-1,1,2 };

4.2. 整体实现

4.2.1 代码

c++ int bfs(int x,int y) { bili in(x,y,0); push(in); //closed.push_back(make_pair(x,y)); while(sz!=0) { bili a = pop(); closed.push_back(make_pair(a.x,a.y)); //printf("a: (%d,%d)",a.x,a.y); if (a.x == tx && a.y == ty) return g[tx][ty]; printf("\n-------------Step %d-------------\n",++cnt); for (int i=0;i<8;i++){ int xx = a.x+dx[i]; int yy = a.y+dy[i]; if (check(xx,yy)&&g[xx][yy]==0){ g[xx][yy] = g[a.x][a.y] + 1; bili nw(xx,yy,g[xx][yy] + h(xx,yy)); pre[xx][yy] = make_pair(a.x,a.y); push(nw); } } print_status(); } return -1; }