八数码问题—A*搜索 先把问题简化一下吧： 在控制台显示这样一个矩阵 [1][2][3] [8]   [4] [7][6][5] 手动把它打乱，然后让程序将其复原。 和野人传教士问题类似，这也是一个对解空间进行搜索的问题，而且更为简单，这次采用可以缩减扩展节点的规模的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();   //判定当前节点是否是最终节点  

评论