VC中利用人工智能解决八迷宫问题

三、程序代码

　　首先，要声明的是，游戏网格在程序中对应着一个拥有10个成员变量的数组，网格每个位置按照从左到右、从上到下的位置排序。对于网格状态，可实现一个状态类，它对应着网格的各种状态，并拥有所有操作网格时所需要的代码和变量，这个类命名为CState，代码如下：

/* 声明网格中空格所有可能移动的方向，至于为什么要包括"NONE"将在后面的代码中显现出来；*/ enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST }; // 声明CState类 class CState { 　private: 　　// 使用1 to 9号索引来对应网格的每个位置, 定义为 char类型是为了节省内存； 　　char Grid[10]; 　　char Depth; //Depth变量对游戏的最初原始状态演变到当前状态所经历的步数； 　　//我们需要记录下父状态是如何进行移动而得到当前状态的； 　　DIRECTION OperatorApplyed; 　　// 父状态指针，当程序结束时，我们可以利用它跟踪所经历的状态，从而给出答案； 　　CState *PrevState; 　　// 寻找当前网格中的空格位置或某一个具体数字的位置，默认状态是寻找空格位置； 　　inline int FindBlank(char Search=0) { 　　　int Blank=1; 　　　while (Grid[Blank] != Search) { 　　　　Blank++; 　　　} 　　　return Blank; 　　} 　　// 按照规定的方向移动空格； 　　void MoveBlank(DIRECTION Direction) { 　　　int Blank = FindBlank(); 　　　// 我们需要记住本次操作所移动的方向； 　　　OperatorApplyed = Direction; 　　　switch (Direction) { 　　　　case NORTH: 　　　　　Grid[Blank] = Grid[Blank - 3]; 　　　　　Grid[Blank - 3] = 0; 　　　　　break; 　　　　case EAST: 　　　　　Grid[Blank] = Grid[Blank + 1]; 　　　　　Grid[Blank + 1] = 0; 　　　　　break; 　　　　case SOUTH: 　　　　　Grid[Blank] = Grid[Blank + 3]; 　　　　　Grid[Blank + 3] = 0; 　　　　　break; 　　　　case WEST: 　　　　　Grid[Blank] = Grid[Blank - 1]; 　　　　　Grid[Blank - 1] = 0; 　　　　　break; 　　　} 　　} 　　/* 下面的函数将被用于第一种方法的heuristics函数的一部分，它得到两个索引位置的直角距离，它还用于确定一个数字当前位置与其应该所在位置的直角距离； 　　int GetDistanceBetween(int Tile1, int Tile2) { 　　　int X1, X2; 　　　int Y1, Y2; 　　　int temp=0; 　　　// 将grid位置转换为X,Y坐标； 　　　Y1 = 1; 　　　Y2 = 2; 　　　X1 = Tile1; 　　　X2 = Tile2; 　　　if(Tile1 > 3) { Y1 = 2; X1 = Tile1 - 3; } 　　　if(Tile1 > 6) { Y1 = 3; X1 = Tile1 - 6; } 　　　if(Tile2 > 3) { Y2 = 2; X2 = Tile2 - 3; } 　　　if(Tile2 > 6) { Y2 = 3; X2 = Tile2 - 6; } 　　　//为了确保距离值为正说，进行必要的换位处理； 　　　if(Y1 - Y2 < 0) { 　　　　temp = Y1; 　　　　Y1 = Y2; 　　　　Y2 = temp; 　　　} 　　　if(X1 - X2 < 0) { 　　　　temp = X1; 　　　　X1 = X2; 　　　　X2 = temp; 　　　} 　　　return ((Y1 - Y2) + (X1 - X2)); 　　} 　public: 　　// 异常处理； 　　class ERROR_ILLEGAL_MOVE{}; 　　class ERROR_NO_MORE_DIRECTIONS{}; 　　class ERROR_OUT_OF_BOUNDS{}; 　　//用于heuristic函数；它代表了当前状态与前一状态的距离；这个数值越小越好。 　　int GetDepth() { 　　　return Depth; 　　} 　　// CState类构造函数； 　　CState() { 　　　Depth = 0; 　　　Grid[1] = 6; // for slower machines use 4 　　　Grid[2] = 1; // for slower machines use 1 　　　Grid[3] = 7; // for slower machines use 3 　　　Grid[4] = 3; // for slower machines use 2 　　　Grid[5] = 0; // for slower machines use 0 　　　Grid[6] = 4; // for slower machines use 5 　　　Grid[7] = 5; // for slower machines use 8 　　　Grid[8] = 8; // for slower machines use 7 　　　Grid[9] = 2; // for slower machines use 6 　　　PrevState = 0; 　　　/*由于还没有以前移动的操作，所以这就是为什么我们需要声明NONE 变量的原因。*/ 　　　OperatorApplyed = NONE; 　　} 　　void SetPrevState(CState *Set) { 　　　PrevState = Set; 　　} 　　CState* GetPrevState() { 　　　return PrevState; 　　} 　　// 用于确定移动操作是否合法 　　bool CanBlankMove(DIRECTION Direction) { 　　　int Blank = FindBlank(); 　　　switch (Direction) { 　　　　case NORTH: 　　　　　if (Blank > 3) { 　　　　　　return true; 　　　　　} 　　　　　else { 　　　　　　return false; 　　　　　} 　　　　　break; 　　　　case EAST: 　　　　　if (Blank != 3 && Blank != 6 && Blank != 9) { 　　　　　　return true; 　　　　　} 　　　　　else { 　　　　　　return false; 　　　　　} 　　　　　break; 　　　　case SOUTH: 　　　　　if (Blank < 7) { 　　　　　　return true; 　　　　　} 　　　　　else { 　　　　　　return false; 　　　　　} 　　　　　break; 　　　　case WEST: 　　　　　if (Blank != 1 && Blank != 4 && Blank != 7) { 　　　　　　return true; 　　　　　} 　　　　　else { 　　　　　　return false; 　　　　　} 　　　　　break; 　　　　default: 　　　　　return false; 　　　　　break; 　　　} 　　} 　　void setgrid(int index, int value) { 　　　Grid[index] = value; 　　} 　　/*该函数如果返回"true", 当前状态将是最终状态，以前的状态指针可以用来回退，从而得到解决问题的答案。*/ 　　bool Solution() { 　　　　if (Grid[1] == 1 && Grid[2] == 2 && Grid[3] == 3 && Grid[4] == 8 && Grid[5] == 0 && Grid[6] == 4 && Grid[7] == 7 && Grid[8] == 6 && Grid[9] == 5) 　　　　{ 　　　　　return true; 　　　　} 　　　　else { 　　　　　return false; 　　　　} 　　} 　　char GetGridValue(int Index) { 　　　if (Index < 1 || Index > 9) { 　　　　throw ERROR_OUT_OF_BOUNDS(); 　　　} 　　　else { 　　　　return Grid[Index]; 　　　} 　　} 　　// 含一个参数的构造函数； 　　CState(CState* Init) { 　　　Depth = (Init->GetDepth()); 　　　OperatorApplyed = Init->GetLastOperator(); 　　　PrevState = Init->GetPrevState(); 　　　for (int n=1; n<=9; n++) { 　　　　Grid[n] = Init->GetGridValue(n); 　　　} 　　} 　　DIRECTION GetLastOperator() { 　　　return OperatorApplyed; 　} 　// 两个参数的构造 函数； 　CState(CState* Init, DIRECTION Direction) { 　　int n; 　　PrevState = Init; 　　Depth = (Init->GetDepth() + 1); 　　for (n=1; n<=9; n++) { 　　　Grid[n] = Init->GetGridValue(n); 　　} 　　MoveBlank(Direction); 　} 　// 另外一个heuristic函数，它计算错误网格的数量； 　int GetWrongTiles() { 　　return ((Grid[1] != 1) + 　　(Grid[2] != 2) + 　　(Grid[3] != 3) + 　　(Grid[4] != 3) + 　　(Grid[5] != 3) + 　　(Grid[6] != 3) + 　　(Grid[7] != 3) + 　　(Grid[8] != 3) + 　　(Grid[9] != 3) + 　　(Depth )); // 也用于第二种heuristic (A*)的depth 　} 　/* ManhattanDistance是一个技术术语，它代表了所有当前位置数字与其应该处于的位置的直角距离之和*/ 　int GetManhattanDistance() { 　　int Result=0; 　　Result = GetDistanceBetween(1, FindBlank(1)); 　　Result = Result + GetDistanceBetween(2, FindBlank(2)); 　　Result = Result + GetDistanceBetween(3, FindBlank(3)); 　　Result = Result + GetDistanceBetween(4, FindBlank(8)); 　　Result = Result + GetDistanceBetween(5, FindBlank(0)); 　　Result = Result + GetDistanceBetween(6, FindBlank(4)); 　　Result = Result + GetDistanceBetween(7, FindBlank(7)); 　　Result = Result + GetDistanceBetween(8, FindBlank(6)); 　　Result = Result + GetDistanceBetween(9, FindBlank(5)); 　　Result = Result + Depth;// 也用于第二种heuristic (A*)的depth； 　　return Result; 　} };

　　正如你所看到的，这是一个很"巨大"的类，但是，它一点都不复杂，仅仅是一些简单的数据操作。比较难的部分是跟踪各种状态，并按照正确的顺序操作它们，这将是我们下面要做的。

　　这部分与人工智能关系不大，但是人工智能程序不能没有它。如果你不了解为什么我们使用链表而不用数组，那末这里告诉你原因，数组在设计时有固定的尺寸，在运行时不能改变，所以如果程序一开始，你就拥有一个含有6 百万个Cstates类对象的数组的话，而且这时你还不需要它，那将浪费大量的内存。