隨著計(jì)算機(jī)技術(shù)的發(fā)展，人工智能（Artificial intelligence，下文簡(jiǎn)稱"AI"）已經(jīng)成為世界各國(guó)一個(gè)熱門的研究方向。對(duì)于這一領(lǐng)域的內(nèi)容，國(guó)內(nèi)起步較晚，目前雖然網(wǎng)絡(luò)上各種編程文章很多，但是關(guān)于如何編程解決人工智能問題的文章和資料少之又少。近日，筆者有幸在國(guó)外網(wǎng)站上發(fā)現(xiàn)了這一篇精彩文章，該文通過VC實(shí)例來說明如何解決及實(shí)現(xiàn)人工智能問題，例子程序雖然相對(duì)來說比較簡(jiǎn)單，但有一定的代表性，對(duì)有興趣研究這一領(lǐng)域的朋友們有借鑒意義。
一、"八迷宮"游戲簡(jiǎn)介
在大學(xué)進(jìn)行AI模塊開發(fā)的時(shí)候，我就開始著手寫這篇文章，目的是介紹我所了解到的一些讓人感興趣的問題。對(duì)于什么是人工智能，我想沒有任何人愿意花費(fèi)大量時(shí)間進(jìn)行爭(zhēng)論。
當(dāng)你讀到這里的時(shí)候，推薦你下源代碼，因?yàn)檎迟N和拷貝的代碼與源代碼的作用相比是遠(yuǎn)遠(yuǎn)不及的。在本文中，我將使用一個(gè)單人游戲"八迷宮"作為一個(gè)例子，這個(gè)游戲的規(guī)則如下：
有一個(gè)3X3的網(wǎng)格，包含1到8這幾個(gè)數(shù)（因此，有一個(gè)格子是空的），最初這8個(gè)數(shù)的排列是隨機(jī)的，例如，下面的排列是一種可能情況：
| 6 | 1 | 7 |
| 3 | 4 | |
| 5 | 8 | 2 |
游戲玩家可以向東、南、西、北等方向移動(dòng)這個(gè)空格，移動(dòng)空格時(shí)，空格所占位置的數(shù)字將填補(bǔ)到原來空格的位置。例如，對(duì)于上圖來說，如果向北移動(dòng)空格，游戲的狀態(tài)將如下圖所示：
| 6 | 1 | |
| 3 | 4 | 7 |
| 5 | 8 | 2 |
當(dāng)游戲狀態(tài)實(shí)現(xiàn)如下所示的狀態(tài)時(shí)，游戲結(jié)束。
| 1 | 2 | 3 |
| 8 | 4 | |
| 7 | 6 | 5 |
二、解決"八迷宮"問題的方法
解決上述問題的方法主要有以下幾種：
1、Breadth First Search（按照"橫向"原則搜索）.
2、Depth First Search（按照"深度"原則搜索）.
3、Heuristic Search（啟發(fā)式搜索）.
4、A* search.
實(shí)現(xiàn)這些方法的代碼非常相似，但是它們工作的方式是截然不同的。所有的上述方法都要使用一個(gè)鏈表，而且最初的鏈表都只有一個(gè)成員，它對(duì)應(yīng)著游戲網(wǎng)格的最初狀態(tài)。這個(gè)成員向它所有可能的子狀態(tài)進(jìn)行膨脹（每種移動(dòng)所產(chǎn)生的結(jié)果都被考慮了進(jìn)去），然后所有這些子狀態(tài)都被添加到鏈表中。這種處理將在一個(gè)循環(huán)中進(jìn)行持續(xù)處理，直到實(shí)現(xiàn)目標(biāo)狀態(tài)，也就是說直到游戲結(jié)束為止。
實(shí)現(xiàn)"八迷宮"單人游戲的偽代碼如下：
Do
Current_Item = Remove_Item_From_List
Child_State_Array = Expand (Current_State)
Add_to_List(Child_State_Array)
If child_State_Array Holds the solution then IsGameOver = true
Loop while (IsGameOver = false)
這個(gè)結(jié)構(gòu)的代碼可以在上述所有的人工智能方法中看到，各種方法的區(qū)別僅僅在于它們是如何在鏈表中進(jìn)行排序。
1、在 breadth first search方法中，各個(gè)成員都是按照某一固定的方向被添加到鏈表中，刪除時(shí)按相反方向進(jìn)行。
2、在 depth first search方法中，各個(gè)成員的添加和刪除都是在鏈表的同一個(gè)方向進(jìn)行。
3、在heuristic search方法中，各個(gè)成員可以在鏈表的任意方向進(jìn)行添加，然而，在從鏈表中刪除一個(gè)成員時(shí)，每一個(gè)成員被"heuristic"函數(shù)進(jìn)行打分（對(duì)于狀態(tài)來說，分?jǐn)?shù)越高越接近于最終狀態(tài)），得分最高的項(xiàng)目將被從鏈表中刪除。
4、A*方法使用兩個(gè)heuristic函數(shù)，并將最終的兩個(gè)得分加在一起。使用兩個(gè)heuristics函數(shù)極大地提高了程序發(fā)現(xiàn)下步最佳狀態(tài)的能力，但是卻降低了程序的運(yùn)行速度。
其實(shí)，三、四方法是第二種方法的延伸和變種，區(qū)別僅在于啟發(fā)式搜索的方式不同罷了，這一點(diǎn)讀者朋友們可以在后面的代碼中細(xì)細(xì)體味。實(shí)際上"八迷宮"這種游戲的heuristic函數(shù)的可以是這么一個(gè)函數(shù)，它計(jì)算擁有正確位置的網(wǎng)格個(gè)數(shù)，或是100-狀態(tài)深度。
使用啟發(fā)式的搜索有利有弊，在這個(gè)例子中，使用啟發(fā)式可能使程序的主循環(huán)降低10倍速度，然而，它降低了循環(huán)的次數(shù)，可能從6百萬次降低到了4000次，這節(jié)省了內(nèi)存的負(fù)荷，以及例子程序的運(yùn)行時(shí)間。（這提醒了我，我使用的最初的狀態(tài)使用了25步解決了問題），這看起來不是很多，但如果沒有啟發(fā)式搜索，搜索將1秒鐘處理300兆的內(nèi)存，除非你使用功能強(qiáng)大的處理機(jī)器，（我使用的是1.3G，256兆的機(jī)器），否則你可能需要減少結(jié)束游戲所需要的移動(dòng)次數(shù)，要低于10。
三、程序代碼
首先，要聲明的是，游戲網(wǎng)格在程序中對(duì)應(yīng)著一個(gè)擁有10個(gè)成員變量的數(shù)組，網(wǎng)格每個(gè)位置按照從左到右、從上到下的位置排序。對(duì)于網(wǎng)格狀態(tài)，可實(shí)現(xiàn)一個(gè)狀態(tài)類，它對(duì)應(yīng)著網(wǎng)格的各種狀態(tài)，并擁有所有操作網(wǎng)格時(shí)所需要的代碼和變量，這個(gè)類命名為CState，代碼如下：
/* 聲明網(wǎng)格中空格所有可能移動(dòng)的方向，至于為什么要包括"NONE"將在后面的代碼中顯現(xiàn)出來；*/
enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST };
// 聲明CState類
class CState {
private:
// 使用1 to 9號(hào)索引來對(duì)應(yīng)網(wǎng)格的每個(gè)位置, 定義為 char類型是為了節(jié)省內(nèi)存；
char Grid[10];
char Depth; //Depth變量對(duì)游戲的最初原始狀態(tài)演變到當(dāng)前狀態(tài)所經(jīng)歷的步數(shù)；
//我們需要記錄下父狀態(tài)是如何進(jìn)行移動(dòng)而得到當(dāng)前狀態(tài)的；
DIRECTION OperatorApplyed;
// 父狀態(tài)指針，當(dāng)程序結(jié)束時(shí)，我們可以利用它跟蹤所經(jīng)歷的狀態(tài)，從而給出答案；
CState *PrevState;
// 尋找當(dāng)前網(wǎng)格中的空格位置或某一個(gè)具體數(shù)字的位置，默認(rèn)狀態(tài)是尋找空格位置；
inline int FindBlank(char Search=0) {
int Blank=1;
while (Grid[Blank] != Search) {
Blank++;
}
return Blank;
}
// 按照規(guī)定的方向移動(dòng)空格；
void MoveBlank(DIRECTION Direction) {
int Blank = FindBlank();
// 我們需要記住本次操作所移動(dòng)的方向；
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;
}
}
/* 下面的函數(shù)將被用于第一種方法的heuristics函數(shù)的一部分，它得到兩個(gè)索引位置的直角距離，它還用于確定一個(gè)數(shù)字當(dāng)前位置與其應(yīng)該所在位置的直角距離；
int GetDistanceBetween(int Tile1, int Tile2) {
int X1, X2;
int Y1, Y2;
int temp=0;
// 將grid位置轉(zhuǎn)換為X,Y坐標(biāo)；
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; }
//為了確保距離值為正說，進(jìn)行必要的換位處理；
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函數(shù)；它代表了當(dāng)前狀態(tài)與前一狀態(tài)的距離；這個(gè)數(shù)值越小越好。
int GetDepth() {
return Depth;
}
// CState類構(gòu)造函數(shù)；
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;
/*由于還沒有以前移動(dòng)的操作，所以這就是為什么我們需要聲明NONE 變量的原因。*/
OperatorApplyed = NONE;
}
void SetPrevState(CState *Set) {
PrevState = Set;
}
CState* GetPrevState() {
return PrevState;
}
// 用于確定移動(dòng)操作是否合法
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;
}
/*該函數(shù)如果返回"true", 當(dāng)前狀態(tài)將是最終狀態(tài)，以前的狀態(tài)指針可以用來回退，從而得到解決問題的答案。*/
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];
}
}
// 含一個(gè)參數(shù)的構(gòu)造函數(shù)；
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;
}
// 兩個(gè)參數(shù)的構(gòu)造 函數(shù)；
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);
}
// 另外一個(gè)heuristic函數(shù)，它計(jì)算錯(cuò)誤網(wǎng)格的數(shù)量；
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是一個(gè)技術(shù)術(shù)語，它代表了所有當(dāng)前位置數(shù)字與其應(yīng)該處于的位置的直角距離之和*/
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;
}
};
正如你所看到的，這是一個(gè)很"巨大"的類，但是，它一點(diǎn)都不復(fù)雜，僅僅是一些簡(jiǎn)單的數(shù)據(jù)操作。比較難的部分是跟蹤各種狀態(tài)，并按照正確的順序操作它們，這將是我們下面要做的。
這部分與人工智能關(guān)系不大，但是人工智能程序不能沒有它。如果你不了解為什么我們使用鏈表而不用數(shù)組，那末這里告訴你原因，數(shù)組在設(shè)計(jì)時(shí)有固定的尺寸，在運(yùn)行時(shí)不能改變，所以如果程序一開始，你就擁有一個(gè)含有6 百萬個(gè)Cstates類對(duì)象的數(shù)組的話，而且這時(shí)你還不需要它，那將浪費(fèi)大量的內(nèi)存。
鏈表僅在需要時(shí)才為新的對(duì)象申請(qǐng)空間，至于它是如何工作的就不詳細(xì)介紹了，到處都有此類的例子，你只要知道它確實(shí)在工作，它是一個(gè)可變尺寸的數(shù)組。鏈表實(shí)際上并不保存狀態(tài)，而保存指向各個(gè)狀態(tài)的指針，這是因?yàn)?，鏈表將是一個(gè)等待膨脹的狀態(tài)隊(duì)列，當(dāng)一個(gè)狀態(tài)膨脹時(shí)，它將從鏈表中刪除，然而，我們需要在內(nèi)存中保存這個(gè)狀態(tài)，用于可能發(fā)生的回退或是用于報(bào)告從最初狀態(tài)到解決問題時(shí)的解決路徑。
當(dāng)我們實(shí)際編寫主循環(huán)代碼時(shí)，我們將把膨脹狀態(tài)放入到第二個(gè)隊(duì)列中，這樣我們才能跟蹤它們?cè)谀抢?，什么時(shí)候從內(nèi)存中刪除狀態(tài)（防止內(nèi)存泄露） 。
好了，從現(xiàn)在起回到C++代碼，生成一個(gè)新的頭文件"Llist.h"，輸入如下代碼：
//列舉鏈表的兩個(gè)末端；
enum SIDE { LEFT, RIGHT };
// 鏈表由下面的Link結(jié)構(gòu)對(duì)象組成；
struct Link {
Link *LeftLink; // 指向鏈表中左端LINK對(duì)象的指針；
Link *RightLink; //指向鏈表中右端LINK對(duì)象的指針；
CState *Data; // 指向狀態(tài)數(shù)據(jù)的指針；
};
// 鏈表類；
class CLList {
private:
Link* LeftPointer; // 指向一個(gè)永遠(yuǎn)是空的，并且是末端的link對(duì)象；
Link* RightPointer; //與上面的指針一樣，但方向相反；
double ListLen; // 鏈表的長(zhǎng)度；
// 清空內(nèi)存；
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);
}
//從鏈表中彈出數(shù)據(jù)；
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;
}
//向鏈表中壓入數(shù)據(jù)
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;
}
}
//啟發(fā)式搜索過程中，從鏈表中搜尋最佳狀態(tài)；
CState* PopBestByHeuristics(HEURISTIC heuristic) {
int BestValue=9999;
int Temp=0;
Link* BestState = 0;
Link* Current = LeftPointer;
CState* ForReturn = 0;
if(!IsListEmpty()) {
//啟發(fā)式搜索可以使用MANHATTAN_DISTANCE或WrongTile方式來搜尋最佳狀態(tài)
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;
}
}
//從鏈表中刪除最佳狀態(tài)；
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;
}接下來，創(chuàng)建另外一個(gè)頭文件"Eightpuzz.h"，這里，除了main()，我將放入所有的東西，這些代碼閱讀起來有一定的難度，所以你要堅(jiān)持?。?BR>
void gotoxy(int x, int y); //函數(shù)原型，使用光標(biāo)的xy坐標(biāo)；
// 枚舉搜索的類型；
enum TYPE {BREADTH_FIRST, DEPTH_FIRST };
// 類舉可能的A* 啟發(fā)式方法，第二種啟發(fā)式使用深度；
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; /* 用于跟蹤以前的狀態(tài)，程序結(jié)束時(shí)要及時(shí)刪除，以免內(nèi)存泄露*/
CLList MainQue; // 等待主隊(duì)列；
SIDE PushSide;
SIDE PopSide;
// 膨脹函數(shù)；
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic);
// 膨脹的步數(shù)；
double Expanded = 0;
// 當(dāng)發(fā)現(xiàn)解決方法后，該函數(shù)將結(jié)果顯示在屏幕上；
void ShowSolution(CState* Solution) {
// 結(jié)果是回退得到的，所以實(shí)際結(jié)果應(yīng)該是與之反向的，這時(shí)候可以使用后入先出的方法；
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;
}
}
// 設(shè)置控制臺(tái)i/o x,y坐標(biāo)
void gotoxy(int x, int y) {
// SET CONSOLE CURSOR POSITION.
COORD coord = {x,y};
HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(handle,coord);
}
// 為主循環(huán)做準(zhǔn)備；
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;
}
//將最初的狀態(tài)放入鏈表中；
MainQue.Push(PushSide, new CState());
//調(diào)用主循環(huán)
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;
}
}
// 主循環(huán)函數(shù)(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);
//對(duì)取出的狀態(tài)保持跟蹤(需要防止內(nèi)存)
/*可以讓用戶規(guī)定結(jié)束游戲所需要移動(dòng)的最大步數(shù)，這僅限于"breadth first only"方法*/
if(LastDepth < CurrentState->GetDepth() && PushSide != PopSide) {
LastDepth = CurrentState->GetDepth();
cout << "EXPANDING LEVEL " << LastDepth << endl;
}
// 如果當(dāng)前節(jié)點(diǎn)沒有超出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打開，仔細(xì)看一看整個(gè)程序的結(jié)構(gòu)及流程。通過這個(gè)例子程序，你應(yīng)該明白，編寫一個(gè)AI程序，所需要做的是：
1、 一個(gè)存儲(chǔ)狀態(tài)的方法；
2、 一個(gè)膨脹狀態(tài)的方法；
3、 一個(gè)回退到原始狀態(tài)的方法；
4、 一個(gè)排序狀態(tài)的方法；
5、 一個(gè)給狀態(tài)評(píng)分的函數(shù)；
6、 一個(gè)主循環(huán)，將一個(gè)狀態(tài)從鏈表中移出，并將其所有的子狀態(tài)添加到鏈表中；
上面的每個(gè)步驟都很簡(jiǎn)單，但將它們組合在一起，并使它易讀易懂卻不那么容易了。
