八数码问题—A*搜索
先把问题简化一下吧：
在控制台显示这样一个矩阵
手动把它打乱，然后让程序将其复原。
和野人传教士问题类似，这也是一个对解空间进行搜索的问题，而且更为简单，这次采用可以缩减扩展节点的规模的A*启发式搜索算法。取节点深度为g(x)，错位的数字数为h(x)，由于问题很简单，所以与有序搜索算法类似，算法框图：
评价函数封装在类里，所以没显示在框图中。
ElemType类包括了对于状态节点所需的所有操作：显然的，用一个一维数组maze[9]保存这九个位置的数，评价函数evaluate()函 数返回当前状态的评价值，对节点进行操作的运算符">>"，判断是否是最终节点的isSuccess()，以及打乱初始节点的顺序的 disrupt()等等。
#include <iostream>
#include <conio.h>
#include <windows.h> //显示矩阵时需要延时，这里有Sleep()函数。
using namespace std;
//接收键盘时使用
const enum Input { UP = 0x048, DOWN = 0x050, LEFT = 0x04b, RIGHT = 0x04d, ENTER = 0xd };
//扩展时判断方向使用
const int U = 0;
const int D = 1;
const int L = 2;
const int R = 3;
class ElemType {
private:
int depth; //当前节点的深度（就是距离初始节点有多远）
int numWrong(); //有多少错位的数字
public:
int maze[9]; //保存矩阵用
ElemType* flag; //指向根节点
ElemType(); //创建初始节点
ElemType(int,int,int,int,int,int,int,int,int);
bool operator ==(ElemType e) {
for(int i = 0; i < 9; i++)
if(this->maze[i]!=e.maze[i])
return false;
return true;
}
void operator =(ElemType e) {
for(int i = 0; i < 9; i++)
this->maze[i] = e.maze[i];
this->depth = e.depth;
this->flag = e.flag;
this->numWrong();
}
ElemType friend operator >>(ElemType source, int direct) {
//这个运算符的重载是对于L，R，U，D四个方向作出的移动
ElemType result = source;
int i = result.locate0();
switch(direct) {
case U: if(i < 6) {
result.maze[i] = result.maze[i+3];
result.maze[i+3] = 0;
} break;
case D: if(i > 2) {
result.maze[i] = result.maze[i-3];
result.maze[i-3] = 0;
} break;
case L: if(i%3 != 2) {
result.maze[i] = result.maze[i+1];
result.maze[i+1] = 0;
} break;
case R: if(i%3 != 0) {
result.maze[i] = result.maze[i-1];
result.maze[i-1] = 0;
}
}
result.depth++;
return result;
}
int locate0(); //确定0所在的位置，其余方法要调用
bool isSuccess(); //判定当前节点是否是最终节点
评论