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

链表仅在需要时才为新的对象申请空间，至于它是如何工作的就不详细介绍了，到处都有此类的例子，你只要知道它确实在工作，它是一个可变尺寸的数组。链表实际上并不保存状态，而保存指向各个状态的指针，这是因为，链表将是一个等待膨胀的状态队列，当一个状态膨胀时，它将从链表中删除，然而，我们需要在内存中保存这个状态，用于可能发生的回退或是用于报告从最初状态到解决问题时的解决路径。

　　当我们实际编写主循环代码时，我们将把膨胀状态放入到第二个队列中，这样我们才能跟踪它们在那里，什么时候从内存中删除状态（防止内存泄露） 。

　　好了，从现在起回到C++代码，生成一个新的头文件"Llist.h"，输入如下代码：

//列举链表的两个末端； enum SIDE { LEFT, RIGHT }; // 链表由下面的Link结构对象组成； struct Link { 　Link *LeftLink; // 指向链表中左端LINK对象的指针； 　Link *RightLink; //指向链表中右端LINK对象的指针； 　CState *Data; // 指向状态数据的指针； }; // 链表类； class CLList { private: 　Link* LeftPointer; // 指向一个永远是空的，并且是末端的link对象； 　Link* RightPointer; //与上面的指针一样，但方向相反； 　double ListLen; // 链表的长度； 　// 清空内存； 　void EmptyUsedMemory() { 　　CState *temp; 　　while(!IsListEmpty()) { 　　　temp = Pop(LEFT); 　　　delete temp; 　　} 　} public: 　class ERROR_CANT_POP_EMPTY_LIST{}; // Error Exception 　CLList() { 　　// initialise all private variables 　　LeftPointer = new Link; 　　RightPointer = new Link; 　　ListLen = 0; 　　LeftPointer->LeftLink = 0; 　　LeftPointer->RightLink = RightPointer; 　　RightPointer->RightLink = 0; 　　RightPointer->LeftLink = LeftPointer; 　} 　~CLList() { 　　EmptyUsedMemory(); 　} 　inline double GetListLen() { 　　return ListLen; 　} 　inline bool IsListEmpty() { 　　return (LeftPointer->RightLink == RightPointer); 　} 　//从链表中弹出数据； 　CState* Pop(SIDE Side) { 　　Link ForReturn; 　　Link* ForDelete; 　　if (!IsListEmpty()) { 　　　ListLen--; 　　　if (Side == LEFT) { 　　　　ForReturn = *(LeftPointer->RightLink); 　　　　ForDelete = LeftPointer->RightLink; 　　　　LeftPointer->RightLink = ForReturn.RightLink; 　　　　ForReturn.RightLink->LeftLink = LeftPointer; 　　　} 　　　else { 　　　　ForReturn = *(RightPointer->LeftLink); 　　　　ForDelete = RightPointer->LeftLink; 　　　　RightPointer->LeftLink = ForReturn.LeftLink; 　　　　ForReturn.LeftLink->RightLink = RightPointer; 　　　} 　　　delete ForDelete; 　　　return ForReturn.Data; 　　} 　　return 0; 　} 　//向链表中压入数据 　void Push(SIDE Side, CState* What) { 　　Link* NewLink = new Link; 　　NewLink->Data = What; 　　ListLen++; 　　if (Side == LEFT) { 　　　NewLink->RightLink = LeftPointer->RightLink; 　　　NewLink->LeftLink = LeftPointer; 　　　LeftPointer->RightLink = NewLink; 　　　NewLink->RightLink->LeftLink = NewLink; 　　} 　　else { 　　　NewLink->RightLink = RightPointer; 　　　NewLink->LeftLink = RightPointer->LeftLink; 　　　RightPointer->LeftLink = NewLink; 　　　NewLink->LeftLink->RightLink = NewLink; 　　} 　} 　//启发式搜索过程中，从链表中搜寻最佳状态； 　CState* PopBestByHeuristics(HEURISTIC heuristic) { 　　int BestValue=9999; 　　int Temp=0; 　　Link* BestState = 0; 　　Link* Current = LeftPointer; 　　CState* ForReturn = 0; 　　if(!IsListEmpty()) { 　　　//启发式搜索可以使用MANHATTAN_DISTANCE或WrongTile方式来搜寻最佳状态 　　　while(Current->RightLink != RightPointer) { 　　　　Current = Current->RightLink; 　　　　if(heuristic == MANHATTAN_DISTANCE) { 　　　　　Temp = Current->Data->GetManhattanDistance(); 　　　　} 　　　　else { 　　　　　Temp = Current->Data->GetWrongTiles(); 　　　　} 　　　　if(Temp < BestValue) { 　　　　　BestValue = Temp; 　　　　　BestState = Current; 　　　　} 　　　} 　　　//从链表中删除最佳状态； 　　　BestState->RightLink->LeftLink = BestState->LeftLink; 　　　BestState->LeftLink->RightLink = BestState->RightLink; 　　　ForReturn = BestState->Data; 　　　delete BestState; 　　　return ForReturn; 　　} 　　return 0; 　} 　CState* PeekByBestHueristics(HEURISTIC heuristic) { 　　int BestValue=9999; 　　int Temp=0; 　　Link* BestState = 0; 　　Link* Current = LeftPointer; 　　CState* ForReturn = 0; 　　if(!IsListEmpty()) { 　　　// Find BEST State By Wrong tile number heuristic 　　　while(Current->RightLink != RightPointer) { 　　　　Current = Current->RightLink; 　　　　if(heuristic == MANHATTAN_DISTANCE) { 　　　　　Temp = Current->Data->GetManhattanDistance(); 　　　　} 　　　　else { 　　　　　Temp = Current->Data->GetWrongTiles(); 　　　　} 　　　　if(Temp < BestValue) { 　　　　　BestValue = Temp; 　　　　　BestState = Current; 　　　　} 　　　} 　　　ForReturn = BestState->Data; 　　　return ForReturn; 　　} 　　return 0; 　}

　　接下来，创建另外一个头文件"Eightpuzz.h"，这里，除了main()，我将放入所有的东西，这些代码阅读起来有一定的难度，所以你要坚持住：

void gotoxy(int x, int y); //函数原型，使用光标的xy坐标； // 枚举搜索的类型； enum TYPE {BREADTH_FIRST, DEPTH_FIRST }; // 类举可能的A* 启发式方法，第二种启发式使用深度； enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES}; // include the header files we are going to need #include<iostream.h> // for console i/o #include<windows.h> // for sleep() and gotoxy() #include"State.h" // for game state class #include"Llist.h" // for a linked list class CLList PrevStates; /* 用于跟踪以前的状态，程序结束时要及时删除，以免内存泄露*/ CLList MainQue; // 等待主队列； SIDE PushSide; SIDE PopSide; // 膨胀函数； CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic); // 膨胀的步数； double Expanded = 0; // 当发现解决方法后，该函数将结果显示在屏幕上； void ShowSolution(CState* Solution) { // 结果是回退得到的，所以实际结果应该是与之反向的，这时候可以使用后入先出的方法； CLList Reverse; bool EndLoop=false; while(!EndLoop) { 　Reverse.Push(LEFT, Solution); 　if(Solution->GetPrevState() != 0) { 　　Solution = Solution->GetPrevState(); 　} 　else { 　　EndLoop = true; 　} } int NewLine = 0; CState *Temp; cout << "\n"; while(!Reverse.IsListEmpty()) { 　Temp = Reverse.Pop(LEFT); 　NewLine++; 　if(NewLine > 10) { cout << "\n"; NewLine=0;} 　switch(Temp->GetLastOperator()) { 　　case NORTH: 　　　cout << "North, "; 　　　break; 　　case EAST: 　　　cout << "East, "; 　　　break; 　　case SOUTH: 　　　cout << "South, "; 　　　break; 　　case WEST: 　　　cout << "West, "; 　　　break; 　} } cout << "\n\n" << "Expanded: " << Expanded << endl; } } // 设置控制台i/o x,y坐标 void gotoxy(int x, int y) { 　// SET CONSOLE CURSOR POSITION. 　COORD coord = {x,y}; 　HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE); 　SetConsoleCursorPosition(handle,coord); } // 为主循环做准备； void GeneralSearch(TYPE Type, HEURISTIC heuristic) { 　CState *Solution; 　int DepthLimit=0; 　switch(heuristic) { 　　case NOT_USED: 　　　// Breadth First Queing Type 　　　if(Type == BREADTH_FIRST) { 　　　　PushSide = RIGHT; 　　　　PopSide = LEFT; 　　　} 　　　else { 　　　　// Depth First Search 　　　　cout << "Enter a Depth Limit :"; 　　　　cin >> DepthLimit; 　　　　PushSide = RIGHT; 　　　　PopSide = RIGHT; 　　　} 　　　break; 　　case MANHATTAN_DISTANCE: 　　　PushSide = RIGHT; 　　　PopSide = RIGHT; 　　　break; 　　case WRONG_TILES: 　　　PushSide = RIGHT; 　　　PopSide = RIGHT; 　} 　//将最初的状态放入链表中； 　MainQue.Push(PushSide, new CState()); 　//调用主循环 　Solution = GeneralExpand(DepthLimit, heuristic); 　// returns pointer to soution. 　// or null pointer (failure) 　if(Solution != 0) { 　　cout << "FOUND SOLUTION!" << endl; 　　ShowSolution(Solution); 　　cout << "DONE" << endl; 　} 　else { 　　//Fail 　　cout << "FAIL" << endl; 　} } // 主循环函数(YEP, it BITES !) CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic) { 　CState *CurrentState = 0; 　CState *TempState = 0; 　int LastDepth=-1; 　if(PushSide == PopSide) {cout << "THINKING...please wait." << endl;} 　　// Main loop 　　while(!MainQue.IsListEmpty()) { 　　　if(heuristic == NOT_USED) { 　　　　CurrentState = MainQue.Pop(PopSide); 　　　} 　　　else { 　　　　CurrentState = MainQue.PopBestByHeuristics(heuristic); 　　　} 　　　PrevStates.Push(RIGHT, CurrentState); 　　　//对取出的状态保持跟踪(需要防止内存) 　　　/*可以让用户规定结束游戏所需要移动的最大步数，这仅限于"breadth first only"方法*/ 　　　if(LastDepth < CurrentState->GetDepth() && PushSide != PopSide) { 　　　　　LastDepth = CurrentState->GetDepth(); 　　　　　cout << "EXPANDING LEVEL " << LastDepth << endl; 　　　} 　　　// 如果当前节点没有超出depth限制 　　　if((CurrentState->GetDepth() < DepthLimit) || (DepthLimit == 0 )) { 　　　　if((CurrentState->CanBlankMove(NORTH)) && (CurrentState->GetLastOperator() != SOUTH)) { 　　　　　TempState = new CState(CurrentState, NORTH); 　　　　　MainQue.Push(PushSide, TempState); 　　　　　Expanded++; 　　　　　if(TempState->Solution()) { 　　　　　　return TempState; 　　　　　} 　　　　} 　　　　if((CurrentState->CanBlankMove(EAST)) && (CurrentState->GetLastOperator() != WEST)) { 　　　　　TempState = new CState(CurrentState, EAST); 　　　　　MainQue.Push(PushSide, TempState); 　　　　　Expanded++; 　　　　　if(TempState->Solution()) { 　　　　　　return TempState; 　　　　　} 　　　　} 　　　if((CurrentState->CanBlankMove(SOUTH)) && (CurrentState->GetLastOperator() != NORTH)) { 　　　　TempState = new CState(CurrentState, SOUTH); 　　　　MainQue.Push(PushSide, TempState); 　　　　Expanded++; 　　　　if(TempState->Solution()) { 　　　　　return TempState; 　　　　} 　　　} 　　　if((CurrentState->CanBlankMove(WEST)) && (CurrentState->GetLastOperator() != EAST)) { 　　　　TempState = new CState(CurrentState, WEST); 　　　　MainQue.Push(PushSide, TempState); 　　　　Expanded++; 　　　　if(TempState->Solution()) { 　　　　　return TempState; 　　　　} 　　　} 　　} 　} 　return 0; }

　　下面是主文件"EightPuzz.cpp" 的代码：

#include"Eightpuzz.h" int main() { 　char Choice=0; 　cout << "Choose Search Method...\n" 　<< " [1] Blind Breadth First Search\n" 　<< " [2] Blind Depth First Search\n" 　<< " [3] A*(Tiles in the wrong position)\n" 　<< " [4] A*(Manhattan Distance)\n" << endl; 　cin >> Choice; 　switch(Choice) { 　　case ’1’: 　　　// call Blind Breadth First Search 　　　GeneralSearch(BREADTH_FIRST, NOT_USED); 　　　break; 　　case ’2’: 　　　// call Blind Depth First Search 　　　GeneralSearch(DEPTH_FIRST, NOT_USED); 　　　break; 　　case ’3’: 　　　// call A* with wrong tiles heuristic 　　　GeneralSearch(DEPTH_FIRST, WRONG_TILES); 　　　break; 　　case ’4’: 　　　// call A* with manhatten heuristic 　　　GeneralSearch(DEPTH_FIRST, MANHATTAN_DISTANCE); 　　　break; 　} 　return 0; }

　　正如我前面所说的，还是推荐你看完本文中的代码，下载程序的源代码，并用VC打开，仔细看一看整个程序的结构及流程。通过这个例子程序，你应该明白，编写一个AI程序，所需要做的是：

　　1、 一个存储状态的方法；

　　2、 一个膨胀状态的方法；

　　3、 一个回退到原始状态的方法；

　　4、 一个排序状态的方法；

　　5、 一个给状态评分的函数；

　　6、 一个主循环，将一个状态从链表中移出，并将其所有的子状态添加到链表中；

　　上面的每个步骤都很简单，但将它们组合在一起，并使它易读易懂却不那么容易了。

查看本文来源