赞
踩
编写九宫重排问题的启发式搜索(A*算法)求解程序。
在3х3组成的九宫棋盘上,放置数码为1~8的8个棋子,棋盘中留有一个空格,空格周围的棋子可以移动到空格中,从而改变棋盘的布局。根据给定初始布局和目标布局,编程给出一个最优的走法序列。输出每个状态的棋盘
测试数据:初始状态:123456780 目标状态:012345678
【输入格式】
输入包含三行,每行3各整数,分别为0-8这九个数字,以空格符号隔开,标识问题的初始状态。0表示空格,例如:
2 0 3
1 8 4
7 6 5
对于九宫重排问题的解决,首先要考虑是否有答案。每一个状态可认为是一个1×9的矩阵,问题即通过矩阵的变换,可以变换为目标状态对应的矩阵。由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通过变换到达,否则,这两个状态不可达。这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。
如果初始状态可以到达目标状态,那么采取什么样的方法呢?常用的状态空间搜索有深度优先和广度优先。广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。由于九宫重排问题状态空间共有9!个状态,如果选定了初始状态和目标状态,有9!/2个状态要搜索,考虑到时间和空间的限制,在这里要求采用A算法求解。
A算法是启发式搜索算法,启发式搜索就是在状态空间中对每一个搜索分支进行评估,得到最好的分支,再从这个分支进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,利用当前与问题有关的信息作为启发式信息指导搜索,这些信息能够有效省略大量无谓的搜索路径,大大提高了搜索效率。
启发式搜索算法定义了一个估价函数f(n),与问题相关的启发式信息都被计算为一定的 f(n) 的值,引入到搜索过程中。f(n) = g(n) +h(n)其中f(n) 是节点n的估价函数,g(n)是在状态空间中从初始节点到节点n的实际代价,h(n)是从节点n到目标节点最佳路径的估计代价。 在九宫重排问题中,显然g(n)就是从初始状态变换到当前状态所移动的步数,估计函数h(n)估计的是节点n到目标节点的距离,我们可以用欧几里德距离、曼哈顿距离或是两节的状态中数字的错位数来估计。
1、存储结构的定义
typedef struct node//八数码结构体
{
int nine[N][N];//数码状态
int f;//估价值
int direct;//空格移动方向
struct node *parent;//父节点
}pNode;
2、启发式搜索算法的描述:
(1)把初始节点S0 放入Open表中,f(S0)=g(S0)+h(S0);
(2)如果Open表为空,则问题无解,失败退出;
(3)把Open表的第一个节点取出放入Closed表,并记该节点为n;
(4)考察节点n是否为目标节点。若是,则找到了问题的解,成功退出;
(5)若节点n不可扩展,则转到第(2)步;
(6)扩展节点n,生成子节点ni(i=1,2,……),计算每一个子节点的估价值f(ni) (i=1,2,……),并为每一个子节点设置指向父节点的指针,然后将这些子节点放入Open表中;
(7)根据各节点的估价函数值,对Open表中的全部节点按从小到大的顺序重新进行排序;
(8)转到第(2)步。
启发式搜索算法的工作过程:
struct Sudoku {
int s[N][N]; //九宫棋盘
int i, j; //空格的下标
int f; // f(n)的值
int father; //存储父节点的下标
};
在搜索路径的过程中,需要储存已出现的路径和已选择的路径,这就是OPEN和CLOSE表的作用。
struct List {
Sudoku a[max]; //存储九宫棋盘的数组
int length; //记录当前顺序表中的结点数
};
List OPEN;
List CLOSE;
A星算法的核心由两部分组成,一是g(n),一是h(n)。
估价函数f(n)=g(n)+h(n)
g(n)表示已走过的路径,它的值是已移动的步数。h(n)是估计代价,它表示预计将走到终点的距离。在本题九宫重排中,h(n)是八个点相对于正确位置的距离之和。之所以这么做,是由移动规则所确定的,因为一次只能由空格上下左右之一移动一格,所以要将八个数字移到正确的位置上,必须由空格一步步移动。
依据于f(n)=g(n)+h(n),便可以启发式搜索出最短路径。
该算法的核心流程如下:
(1)首先接受输入的矩阵,初始化各项数据,并直接存入CLOSE表。
(2)判断该矩阵是否有解。(通过有序序列的逆序值来判断,如果两者都是偶数或奇数,则可通过变换到达,否则,这个状态不可达。)若有解则继续,无解则输出无解后结束。
(3)进入循环,判断当前CLOSE表尾是否为解,若是则结束,不是则继续。
(4)根据CLOSE表最后一个结点扩展结点并按插入排序放入OPEN表。(依据f(n)的值由小到大)
(5)将OPEN表第一个结点放入CLOSE表尾。回到第(3)步。
(6)输出结果
代码表述如下:
void AStar() {
if (NoAnswer()) { //判断是否有解
cout << "该九宫格无解!" << endl;
return;
}
while (!IsAnswer()) { //判断是否为解
NextStep(); //扩展结点并插入排序
JoinClose(); //将OPEN表第一个放入CLOSE表中
}
ShowAnswer(); //输出解
}
注:有些函数中还调用了其它的函数,这些函数的实现将在后续的完整代码中给出。
(1)判断是否有解:NoAnswer()
bool NoAnswer() { int count = 0; bool once = 0; for (int p = 0; p < N; p++) for (int q = 0; q < N; q++) { for (int i = p; i < N; i++) for (int j = 0; j < N; j++) { if (p == i && once == 0) { j = q; once = 1; } if (CLOSE.a[0].s[i][j] == 0 || CLOSE.a[0].s[p][q] == 0) continue; if (CLOSE.a[0].s[p][q] > CLOSE.a[0].s[i][j]) count++; } once = 0; } if (count % 2 == 1) return false; return true; }
(2)判断是否为解:IsAnswer()
bool IsAnswer() {
if (CLOSE.a[CLOSE.length - 1].s[0][0] != 1|| CLOSE.a[CLOSE.length - 1].s[0][1] != 2
|| CLOSE.a[CLOSE.length - 1].s[0][2] != 3|| CLOSE.a[CLOSE.length - 1].s[1][0] != 8
|| CLOSE.a[CLOSE.length - 1].s[1][2] !=4|| CLOSE.a[CLOSE.length - 1].s[2][0] != 7
|| CLOSE.a[CLOSE.length - 1].s[2][1] != 6|| CLOSE.a[CLOSE.length - 1].s[2][2] != 5)
return false;
return true;
}
(3)根据CLOSE表最后一个结点扩展结点并按插入排序放入OPEN表:NextStep()
void NextStep() { Sudoku node; int i = CLOSE.a[CLOSE.length - 1].i; int j = CLOSE.a[CLOSE.length - 1].j; if (j + 1 <= N-1) { //将新结点加入OPEN表 node.i = i; //给node各数据赋值 node.j = j + 1; for(int p=0;p<N;p++) for (int q=0; q < N; q++) { node.s[p][q] = CLOSE.a[CLOSE.length - 1].s[p][q]; } node.s[i][j] = CLOSE.a[CLOSE.length - 1].s[i][j + 1]; node.s[i][j+1] = 0; node.father = CLOSE.length - 1; node.g = CLOSE.a[CLOSE.length - 1].g + 1; node.f = CLOSE.a[CLOSE.length - 1].f + 1 + Changeh(node,1); //求更改后h(n)的变化值,其中参数1,2,3,4分别表示空格向右,下,左,上移动 for (int p = 0; p <= OPEN.length; p++) { //将node按大小插入OPEN表中,这样可保证OPEN表由小到大有序 if (p == OPEN.length) { Insert(node, OPEN.length); break; } if (node.f < OPEN.a[p].f) { Insert(node, p); break; } } } if (j - 1 >= 0) { node.i = i; //给node各数据赋值 node.j = j - 1; for (int p=0; p < N; p++) for (int q=0; q < N; q++) { node.s[p][q] = CLOSE.a[CLOSE.length - 1].s[p][q]; } node.s[i][j] = CLOSE.a[CLOSE.length - 1].s[i][j - 1]; node.s[i][j-1] = 0; node.father = CLOSE.length - 1; node.g = CLOSE.a[CLOSE.length - 1].g + 1; node.f = CLOSE.a[CLOSE.length - 1].f + 1 + Changeh(node, 3); //求更改后h(n)的变化值,其中参数1,2,3,4分别表示空格向右,下,左,上移动 for (int p = 0; p <= OPEN.length; p++) { //将node按大小插入OPEN表中,这样可保证OPEN表由小到大有序 if (p == OPEN.length) { Insert(node, OPEN.length); break; } if (node.f < OPEN.a[p].f) { Insert(node, p); break; } } } if (i+ 1 <= N-1) { node.i = i+1; //给node各数据赋值 node.j = j; for (int p=0; p < N; p++) for (int q=0; q < N; q++) { node.s[p][q] = CLOSE.a[CLOSE.length - 1].s[p][q]; } node.s[i][j] = CLOSE.a[CLOSE.length - 1].s[i+1][j]; node.s[i+1][j] = 0; node.father = CLOSE.length - 1; node.g = CLOSE.a[CLOSE.length - 1].g + 1; node.f = CLOSE.a[CLOSE.length - 1].f + 1 + Changeh(node, 2); //求更改后h(n)的变化值,其中参数1,2,3,4分别表示空格向右,下,左,上移动 for (int p = 0; p <= OPEN.length; p++) { //将node按大小插入OPEN表中,这样可保证OPEN表由小到大有序 if (p == OPEN.length) { Insert(node, OPEN.length); break; } if (node.f < OPEN.a[p].f) { Insert(node, p); break; } } } if (i - 1 >= 0) { node.i = i-1; //给node各数据赋值 node.j = j; for (int p=0; p < N; p++) for (int q=0; q < N; q++) { node.s[p][q] = CLOSE.a[CLOSE.length - 1].s[p][q]; } node.s[i][j] = CLOSE.a[CLOSE.length - 1].s[i-1][j]; node.s[i-1][j] = 0; node.father = CLOSE.length - 1; node.g = CLOSE.a[CLOSE.length - 1].g + 1; node.f = CLOSE.a[CLOSE.length - 1].f + 1 + Changeh(node, 4); //求更改后h(n)的变化值,其中参数1,2,3,4分别表示空格向右,下,左,上移动 for (int p = 0; p <= OPEN.length; p++) { //将node按大小插入OPEN表中,这样可保证OPEN表由小到大有序 if (p == OPEN.length) { Insert(node, OPEN.length); break; } if (node.f < OPEN.a[p].f) { Insert(node, p); break; } } } }
(4)将OPEN表第一个结点放入CLOSE表尾:JoinClose()
void JoinClose() { //将OPEN表第一个加入CLOSE表中
CLOSE.a[CLOSE.length] = OPEN.a[0];
CLOSE.length++;
for (int i = 1; i < OPEN.length; i++) {
OPEN.a[i - 1] = OPEN.a[i];
}
OPEN.length--;
}
(5)输出结果:ShowAnswer()
void ShowAnswer() { Matrix m[max]; int count = 0; int z = CLOSE.length - 1; while (z != -1) { for(int i=0;i<N;i++) for (int j = 0; j < N; j++) { m[count].b[i][j] = CLOSE.a[z].s[i][j]; } count++; z = CLOSE.a[z].father; } cout << "九宫棋盘的移动过程如下:" << endl; for (int p = count - 2; p >= 0; p--) { cout << endl << " |" << endl << " |" << endl << "\\ /" << endl << endl; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << m[p].b[i][j] << " "; cout << endl; } } }
用矩阵 2 8 3 做测试输出如下:
1 6 4
7 0 5
#include <iostream> using namespace std; #define N 3 #define max 999 struct Sudoku { int s[N][N]; //九宫棋盘 int i, j; //空格的下标 int f,g; // f(n),g(n)的值 int father; //存储父节点的下标 }; struct List { Sudoku a[max]; //存储九宫棋盘的数组 int length; //记录当前顺序表中的结点数 }; struct Matrix { int b[N][N]; }; class GraphSearch { List OPEN; List CLOSE; int order[N][N]; public: GraphSearch() { cout << "请输入起始状态" << endl; OPEN.length = 0; CLOSE.length = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> CLOSE.a[0].s[i][j]; if (CLOSE.a[0].s[i][j] == 0) { CLOSE.a[0].i = i; CLOSE.a[0].j = j; } } } CLOSE.length++; CLOSE.a[0].father = -1; CLOSE.a[0].g = 0; CLOSE.a[0].f = CLOSE.a[0].g + Geth(CLOSE.a[0]); cout << "请输入目标状态:" << endl; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> order[i][j]; } } } void AStar() { int count = 0; if (NoAnswer()) { //判断是否有解 cout << "该九宫格无解!" << endl; return; } while (!IsAnswer()) { //判断是否为解 NextStep(); //扩展结点并插入排序 JoinClose(); //将OPEN表第一个放入CLOSE表中 count++; } cout << "到达目标状态所需步数为:" << count << endl; ShowAnswer(); //输出解 } int Geth(Sudoku S) { //求目标h(n)的值 int count = 0; for(int i=0;i<N;i++) for (int j = 0; j < N; j++) { if (S.i == i && S.j == j) continue; count += abs(Findx(S.s[i][j]) - i) + abs(Findy(S.s[i][j]) - j); } return count; } int Changeh(Sudoku S,int b) { //由于一次只会修改一个点的h(n),所以计算修改值是最快的 if (b == 1) { if (abs(Findy(S.s[S.i][S.j - 1]) - S.j + 1) > abs(Findy(S.s[S.i][S.j - 1]) - S.j)) return 1; else return -1; } if (b == 2) { if (abs(Findx(S.s[S.i - 1][S.j]) - S.i + 1) > abs(Findx(S.s[S.i - 1][S.j]) - S.i)) return 1; else return -1; } if (b == 3) { if (abs(Findy(S.s[S.i][S.j+1]) - S.j -1) > abs(Findy(S.s[S.i][S.j+1]) - S.j)) return 1; else return -1; } else { if (abs(Findx(S.s[S.i + 1][S.j]) - S.i - 1) > abs(Findx(S.s[S.i + 1][S.j]) - S.i)) return 1; else return -1; } } void JoinClose() { //将OPEN表第一个加入CLOSE表中 CLOSE.a[CLOSE.length] = OPEN.a[0]; CLOSE.length++; for (int i = 1; i < OPEN.length; i++) { OPEN.a[i - 1] = OPEN.a[i]; } OPEN.length--; } bool IsAnswer() { for(int i=0;i<N;i++) for (int j = 0; j < N; j++) { if (CLOSE.a[CLOSE.length - 1].s[i][j] != order[i][j]) return false; } return true; } void NextStep() { Sudoku node; int i = CLOSE.a[CLOSE.length - 1].i; int j = CLOSE.a[CLOSE.length - 1].j; if (j + 1 <= N-1) { //将新结点加入OPEN表 node.i = i; //给node各数据赋值 node.j = j + 1; for(int p=0;p<N;p++) for (int q=0; q < N; q++) { node.s[p][q] = CLOSE.a[CLOSE.length - 1].s[p][q]; } node.s[i][j] = CLOSE.a[CLOSE.length - 1].s[i][j + 1]; node.s[i][j+1] = 0; node.father = CLOSE.length - 1; node.g = CLOSE.a[CLOSE.length - 1].g + 1; node.f = CLOSE.a[CLOSE.length - 1].f + 1 + Changeh(node,1); //求更改后h(n)的变化值,其中参数1,2,3,4分别表示空格向右,下,左,上移动 for (int p = 0; p <= OPEN.length; p++) { //将node按大小插入OPEN表中,这样可保证OPEN表由小到大有序 if (p == OPEN.length) { Insert(node, OPEN.length); break; } if (node.f < OPEN.a[p].f) { Insert(node, p); break; } } } if (j - 1 >= 0) { node.i = i; //给node各数据赋值 node.j = j - 1; for (int p=0; p < N; p++) for (int q=0; q < N; q++) { node.s[p][q] = CLOSE.a[CLOSE.length - 1].s[p][q]; } node.s[i][j] = CLOSE.a[CLOSE.length - 1].s[i][j - 1]; node.s[i][j-1] = 0; node.father = CLOSE.length - 1; node.g = CLOSE.a[CLOSE.length - 1].g + 1; node.f = CLOSE.a[CLOSE.length - 1].f + 1 + Changeh(node, 3); //求更改后h(n)的变化值,其中参数1,2,3,4分别表示空格向右,下,左,上移动 for (int p = 0; p <= OPEN.length; p++) { //将node按大小插入OPEN表中,这样可保证OPEN表由小到大有序 if (p == OPEN.length) { Insert(node, OPEN.length); break; } if (node.f < OPEN.a[p].f) { Insert(node, p); break; } } } if (i+ 1 <= N-1) { node.i = i+1; //给node各数据赋值 node.j = j; for (int p=0; p < N; p++) for (int q=0; q < N; q++) { node.s[p][q] = CLOSE.a[CLOSE.length - 1].s[p][q]; } node.s[i][j] = CLOSE.a[CLOSE.length - 1].s[i+1][j]; node.s[i+1][j] = 0; node.father = CLOSE.length - 1; node.g = CLOSE.a[CLOSE.length - 1].g + 1; node.f = CLOSE.a[CLOSE.length - 1].f + 1 + Changeh(node, 2); //求更改后h(n)的变化值,其中参数1,2,3,4分别表示空格向右,下,左,上移动 for (int p = 0; p <= OPEN.length; p++) { //将node按大小插入OPEN表中,这样可保证OPEN表由小到大有序 if (p == OPEN.length) { Insert(node, OPEN.length); break; } if (node.f < OPEN.a[p].f) { Insert(node, p); break; } } } if (i - 1 >= 0) { node.i = i-1; //给node各数据赋值 node.j = j; for (int p=0; p < N; p++) for (int q=0; q < N; q++) { node.s[p][q] = CLOSE.a[CLOSE.length - 1].s[p][q]; } node.s[i][j] = CLOSE.a[CLOSE.length - 1].s[i-1][j]; node.s[i-1][j] = 0; node.father = CLOSE.length - 1; node.g = CLOSE.a[CLOSE.length - 1].g + 1; node.f = CLOSE.a[CLOSE.length - 1].f + 1 + Changeh(node, 4); //求更改后h(n)的变化值,其中参数1,2,3,4分别表示空格向右,下,左,上移动 for (int p = 0; p <= OPEN.length; p++) { //将node按大小插入OPEN表中,这样可保证OPEN表由小到大有序 if (p == OPEN.length) { Insert(node, OPEN.length); break; } if (node.f < OPEN.a[p].f) { Insert(node, p); break; } } } } int Findx(int x) { //查找x在图中目标的位置,行下标x for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { if (x == order[i][j]) return i; } } int Findy(int x) { //查找x在图中目标的位置,列下标y for(int i=0;i<N;i++) for (int j = 0; j < N; j++) { if (x == order[i][j]) return j; } } void Insert(Sudoku S,int x) { //插入函数,把结点S插入到OPEN表中下标为X的位置 for (int p = OPEN.length; p > x; p--) OPEN.a[p] = OPEN.a[p - 1]; OPEN.a[x] = S; OPEN.length++; } bool NoAnswer() { int count = 0; int count2 = 0; bool once = 0; for (int p = 0; p < N; p++) for (int q = 0; q < N; q++) { for (int i = p; i < N; i++) for (int j = 0; j < N; j++) { if (p == i && once == 0) { j = q; once = 1; } if (CLOSE.a[0].s[i][j] == 0 || CLOSE.a[0].s[p][q] == 0) continue; if (CLOSE.a[0].s[p][q] > CLOSE.a[0].s[i][j]) count++; } once = 0; } once = 0; for (int p = 0; p < N; p++) for (int q = 0; q < N; q++) { for (int i = p; i < N; i++) for (int j = 0; j < N; j++) { if (p == i && once == 0) { j = q; once = 1; } if (CLOSE.a[0].s[i][j] == 0 || CLOSE.a[0].s[p][q] == 0) continue; if (CLOSE.a[0].s[p][q] > CLOSE.a[0].s[i][j]) count2++; } once = 0; } if ((count % 2) ==(count2%2)) return false; return true; } void ShowAnswer() { Matrix m[max]; int count = 0; int z = CLOSE.length - 1; while (z != -1) { for(int i=0;i<N;i++) for (int j = 0; j < N; j++) { m[count].b[i][j] = CLOSE.a[z].s[i][j]; } count++; z = CLOSE.a[z].father; } cout << "九宫棋盘的移动过程如下:" << endl; for (int p = count - 1; p >= 0; p--) { cout << endl << " |" << endl << " |" << endl << "\\ /" << endl << endl; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) cout << m[p].b[i][j] << " "; cout << endl; } } } }; int main() { cout << "请输入九宫棋盘的数据(空格以0代替)" << endl; GraphSearch gs; gs.AStar(); return 0; }
以上就是用A星算法实现解九宫棋盘的全部内容,说实话,对于我一个小菜鸟来说这个实验还是有相当难度的,写了整整两天。喜欢的看官别忘了点个赞哦。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。