從起點 開始，把它加入到一個由方格組成的open list(開放列表) 中，這個open list像是一個購物清單。Open list里的格子是可能會是沿途經(jīng)過的，也有可能不經(jīng)過。因此可以將其看成一個待檢查的列表。查看與相鄰的8個方格 ，把其中可走的 (walkable) 或可到達(dá)的(reachable) 方格加入到open list中。并把起點 設(shè)置為這些方格的父節(jié)點 (parent node) 。然后把 起點 從open list中移除，加入到close list(封閉列表) 中，close list中的每個方格都是不需要再關(guān)注的。

需要從open list中選一個與起點相鄰的方格。但是到底選擇哪個方格好呢？選F值（F(n) = G + H 。G代表的是從初始位置A沿著已生成的路徑到指定待檢測格子的移動開銷。H指定待測格子到目標(biāo)節(jié)點B的估計移動開銷。H采用的是傳統(tǒng)的曼哈頓距離（Manhattan Distance），也就是橫縱向走的距離之和，并且忽略沿途的障礙。）最小的那個。

比較open list中節(jié)點的F值后，發(fā)現(xiàn)起點右側(cè)節(jié)點的F=40，值最小。選作當(dāng)前處理節(jié)點，并將這個點從Open List刪除，移到Close List中。

對這個節(jié)點周圍的8個格子進(jìn)行判斷，若是不可通過（比如墻，水，或是其他非法地形）或已經(jīng)在Close List中，則忽略。否則執(zhí)行以下步驟：

（1）若當(dāng)前處理節(jié)點的相鄰格子已經(jīng)在Open List中，則檢查這條路徑是否更優(yōu)，即計算經(jīng)由當(dāng)前處理節(jié)點到達(dá)那個方格是否具有更小的 G值。如果沒有，不做任何操作。相反，如果G值更小，則把那個方格的父節(jié)點設(shè)為當(dāng)前處理節(jié)點 ( 我們選中的方格 ) ，然后重新計算那個方格的 F 值和 G 值。（2）若當(dāng)前處理節(jié)點的相鄰格子不在Open List中，那么把它加入，并將它的父節(jié)點設(shè)置為該節(jié)點。

算法思想：

定義open表和close表，其中open表是用來存儲待查驗的節(jié)點，而close表是用來存儲已查驗過的節(jié)點（不需要再關(guān)注的節(jié)點）

把開始節(jié)點加入open表；

將開始節(jié)點拓展的子節(jié)點加入open表，將開始節(jié)點加入到close表；

將open表中的節(jié)點的耗散值也就是f進(jìn)行從小到大的排序，此時open表中的第一個節(jié)點的耗散值最小，對open表中的第一個節(jié)點進(jìn)行判斷，如果這個節(jié)點是目標(biāo)節(jié)點，則算法結(jié)束，無需進(jìn)行以下步驟；反之，如果這個節(jié)點不是目標(biāo)節(jié)點，則將這個節(jié)點進(jìn)行擴展，再進(jìn)行下一步；

判斷n的可擴展節(jié)點（相鄰節(jié)點）m，情況一：如果m在open表中，則說明初始節(jié)點到m節(jié)點出現(xiàn)了兩條路徑，此時需要判斷這兩條路徑的耗散值的大小如果是新路徑的耗散值小，則需要更改m節(jié)點的父節(jié)點，并將open表中的原的m節(jié)點加入close表，將現(xiàn)在的m節(jié)點加入open表，如果是新路徑的耗散值大，則不需要進(jìn)行任何操作；情況二：如果m在close表中，則說明初始節(jié)點該節(jié)點到m節(jié)點有兩條路徑，如果是新路徑的耗散值大，則不需要進(jìn)行任何操作如果是新路徑的耗散值小，需要將更改m節(jié)點的父節(jié)點，并將m節(jié)點從close表中取出，并放入open表中；情況三：m節(jié)點既不在open表中也不在close表中，直接將m節(jié)點加入到open表中即可；

重復(fù)第4步，（算法結(jié)束的兩種情況，其一，當(dāng)前節(jié)點就是目標(biāo)節(jié)點，即找到
了最優(yōu)解；其二，open表為空，既無法找到到目標(biāo)節(jié)點的路徑，即無解。）

代碼實現(xiàn)

#include <iostream> #include <time.h> using namespace std;/* 定義結(jié)構(gòu)體 */ struct EightNum { //存儲八數(shù)碼int status[9];//存儲走的是第幾步(層數(shù))int G;//存儲不在位的格數(shù)(作為我們的啟發(fā)式函數(shù)）int H;//存儲估價函數(shù)的值int F;//存儲0數(shù)碼的位置int Zero;//存儲操作符（1左2右3上4下）int step;//父指針EightNum* Parent; };#define MAXLISTSIZE 10000 #define MAXSTEPSIZE 100 //聲明最終狀態(tài) int FinalStatus[9]; //定義OPEN表和CLOSE表,open和close是表中最后一個內(nèi)容的下一位序號 EightNum OPEN[MAXLISTSIZE]; EightNum CLOSE[MAXLISTSIZE]; int open = 0; int close = 0;EightNum* Node;/* 計算不在位的字格數(shù)H 返回 H */ int CountH(int* status) {int H = 0;int i;for (i = 0; i <= 8; i++){if (FinalStatus[i] != status[i]){H++;}}return H; }/* 判斷新生成的節(jié)點是否已經(jīng)存在于OPEN表或CLOSE表中 返回 表征是否存在于OPEN或CLOSE的值，值為0 均不在，值>0 只在OPEN表，值<0 只在CLOSE表，|值|-1表示所在列表中的位置 */ int Exist(EightNum* N) {int i, j;//計算不在位的字格數(shù)，如果為0，則證明給函數(shù)的節(jié)點在表中已存在int H = 0;int status[9];Node = new EightNum;Node = N;for (i = 0; i <= 8; i++){status[i] = Node->status[i];}//判斷是否在OPEN表for (i = 0; i <= open - 1; i++){for (j = 0; j <= 8; j++){if (status[j] != OPEN[i].status[j]){H++;}}//H=0證明在表中找到該節(jié)點if (H == 0){//如果在OPEN表中，返回i（節(jié)點在OPEN的位置）+ 1（在OPEN找到該節(jié)點）return i + 1;}//掃描完一個節(jié)點后重置HH = 0;}//判斷是否在CLOSE表for (i = 0; i <= close - 1; i++){for (j = 0; j <= 8; j++){if (status[j] != CLOSE[i].status[j]){H++;}}//H=0證明在表中找到該節(jié)點if (H == 0){//如果在CLOSE表中，返回-i（i為節(jié)點在CLOSE的位置）- 1（在CLOSE找到該節(jié)點）return (-i) - 1;}//掃描完一個節(jié)點后重置HH = 0;}return 0; }/* 初始化節(jié)點 返回 初始化后的節(jié)點Node */ EightNum* EightNumInit(int status[10], int zero, int g, EightNum* parent, int step) {int i;Node = new EightNum;for (i = 0; i <= 8; i++){Node->status[i] = status[i];}Node->Zero = zero;Node->G = g;Node->H = CountH(Node->status);Node->F = Node->G + Node->H;Node->Parent = parent;Node->step = step;return Node; }/* 左移后的變化 返回 左移后的狀態(tài) */ int* Left(int* s, int z) {int temp, i;static int status[9];for (i = 0; i <= 8; i++){status[i] = s[i];}//左移則是下標(biāo)減1，需要與前一個位置進(jìn)行值的交換temp = status[z - 1];status[z - 1] = 0;status[z] = temp;return status; }/* 右移后的變化 返回 右移后的狀態(tài) */ int* Right(int* s, int z) {int temp, i;static int status[9];for (i = 0; i <= 8; i++){status[i] = s[i];}temp = status[z + 1];status[z + 1] = 0;status[z] = temp;return status; }/* 上移后的變化 返回 上移后的狀態(tài) */ int* Up(int* s, int z) {int temp, i;static int status[9];for (i = 0; i <= 8; i++){status[i] = s[i];}temp = status[z - 3];status[z - 3] = 0;status[z] = temp;return status; }/* 下移后的變化 返回 下移后的狀態(tài) */ int* Down(int* s, int z) {int temp, i;static int status[9];for (i = 0; i <= 8; i++){status[i] = s[i];}temp = status[z + 3];status[z + 3] = 0;status[z] = temp;return status; }/* 判斷子節(jié)點是否在OPEN或CLOSE中，并進(jìn)行對應(yīng)的操作 返回值 NULL */ void ExistAndOperate(EightNum* N) {int i;//定義表示新生成節(jié)點是否在OPEN表或CLOSE表中, 值為0 均不在，值>0 只在OPEN表，值<0 只在CLOSE表int inList;Node = new EightNum;Node = N;//如果是第一步的節(jié)點，直接加入OPEN中，返回if (Node->G == 1){OPEN[open] = *Node;open++;return;}//判斷新節(jié)點是否在OPEN或CLOSE中inList = Exist(Node);//如果均不在兩個表中，將節(jié)點加入OPEN表中if (inList == 0){//將拓展出的新結(jié)點加入到OPEN表中OPEN[open] = *Node;open++;}//如果在OPEN中，說明從初始節(jié)點到該節(jié)點找到了不同路徑，保留耗散值短的那條路徑else if (inList > 0){//如果表內(nèi)節(jié)點F值大于新節(jié)點F值，用新節(jié)點代替表內(nèi)節(jié)點if (OPEN[inList - 1].F > Node->F){OPEN[inList - 1] = *Node;}}//如果在CLOSE中，說明初始節(jié)點到該節(jié)點有兩條路徑，如果新找到的路徑耗散值大，什么都不做，如果較小，將其從CLOSE中取出放入OPEN中 else if (inList < 0){inList = -inList;//如果較小if (CLOSE[inList - 1].F > Node->F){//將其取出放入OPENOPEN[open] = *Node;open++;}//將其在CLOSE中釋放for (i = inList - 1; i <= close - 1; i++){CLOSE[i] = CLOSE[i + 1];}close--;} }/* 尋找最佳路徑函數(shù) 返回 最后的節(jié)點Node */ EightNum* Search() {int* status;int i, j;EightNum* Temp;//一直循環(huán)知道找到解結(jié)束while (1){Temp = new EightNum;//用冒泡排序給OPEN表里面的節(jié)點按耗散值進(jìn)行排序for (i = open - 1; i > 0; i--){for (j = 0; j < i; j++){//從小到大進(jìn)行排序if (OPEN[j].F > OPEN[j + 1].F){//交換值*Temp = OPEN[j + 1];OPEN[j + 1] = OPEN[j];OPEN[j] = *Temp;}}}Node = new EightNum;//從OPEN表中取出第一個元素（F值最小）*Node = OPEN[0];//判斷該節(jié)點是否是目標(biāo)節(jié)點，若是，則不在位的格數(shù)為0，算法結(jié)束，若不是，則將該結(jié)點進(jìn)行擴展if (!CountH(Node->status)){break;}Temp = Node;//將擴展過的節(jié)點放入CLOSE CLOSE[close] = *Node;close++;//將擴展的節(jié)點從OPEN中釋放for (i = 0; i <= open - 1; i++){//相當(dāng)于是出棧OPEN[i] = OPEN[i + 1];}open--;//如果能左移，則進(jìn)行左移創(chuàng)造新結(jié)點，下標(biāo)為0，3，6則不能進(jìn)行左移if ((Temp->Zero) % 3 >= 1){//創(chuàng)造新結(jié)點Node = new EightNum;//得到新的狀態(tài)status = Left(Temp->status, Temp->Zero);//初始化新結(jié)點Node = EightNumInit(status, Temp->Zero - 1, (Temp->G) + 1, Temp, 1);//判斷子節(jié)點是否在OPEN或CLOSE中，并進(jìn)行對應(yīng)的操作ExistAndOperate(Node);}//如果能右移，則進(jìn)行右移創(chuàng)造新結(jié)點 ，下標(biāo)為2，5，8則不能if ((Temp->Zero) % 3 <= 1){ //創(chuàng)造新結(jié)點Node = new EightNum;//得到新的狀態(tài)status = Right(Temp->status, Temp->Zero);//初始化新結(jié)點Node = EightNumInit(status, Temp->Zero + 1, (Temp->G) + 1, Temp, 2);//判斷子節(jié)點是否在OPEN或CLOSE中，并進(jìn)行對應(yīng)的操作ExistAndOperate(Node);}//如果能上移，則進(jìn)行上移創(chuàng)造新結(jié)點 ，下標(biāo)為0，1，2則不可以if (Temp->Zero >= 3){Node = new EightNum;//得到新的狀態(tài)status = Up(Temp->status, Temp->Zero);//初始化新結(jié)點Node = EightNumInit(status, Temp->Zero - 3, (Temp->G) + 1, Temp, 3);//判斷子節(jié)點是否在OPEN或CLOSE中，并進(jìn)行對應(yīng)的操作ExistAndOperate(Node);}//如果能下移，則進(jìn)行下移創(chuàng)造新結(jié)點 ，下標(biāo)為6，7，8則不可以if (Temp->Zero <= 5){Node = new EightNum; //創(chuàng)造新結(jié)點status = Down(Temp->status, Temp->Zero); //得到新的狀態(tài)Node = EightNumInit(status, Temp->Zero + 3, (Temp->G) + 1, Temp, 4); //初始化新結(jié)點ExistAndOperate(Node); //判斷子節(jié)點是否在OPEN或CLOSE中，并進(jìn)行對應(yīng)的操作}//如果open=0， 證明算法失敗， 沒有解if (open == 0)return NULL;}return Node; }/* 展示具體步驟 返回 NULL */ void ShowStep(EightNum* Node) {int STEP[MAXSTEPSIZE];int STATUS[MAXSTEPSIZE][9];int step = 0;int i, j;int totalStep = Node->G;while (Node){STEP[step] = Node->step;for (i = 0; i <= 8; i++){STATUS[step][i] = Node->status[i];}step++;Node = Node->Parent;}cout << "----------------------" << endl;cout << "總步數(shù)：" << totalStep << endl;cout << "----------------------" << endl;for (i = step - 1; i >= 0; i--){if (STEP[i] == 1)cout << "向左走一步" << endl;else if (STEP[i] == 2)cout << "向右走一步" << endl;else if (STEP[i] == 3)cout << "向上走一步" << endl;else if (STEP[i] == 4)cout << "向下走一步" << endl;else if (STEP[i] == 0)cout << "開始：" << endl;for (j = 0; j <= 8; j++){cout << STATUS[i][j] << " ";//換行輸出if (j == 2 || j == 5 || j == 8)cout << endl;}cout << "----------------------" << endl;} } /* 主函數(shù) */ int main() {int fstatus[9];int i, beginTime, endTime;EightNum* FNode;EightNum* EndNode;//輸入初始狀態(tài)cout << "請輸入初始狀態(tài)：" << endl;for (i = 0; i <= 8; i++){cin >> fstatus[i];}cout << endl;//輸入最終狀態(tài)cout << "請輸入最終狀態(tài)：" << endl;for (i = 0; i <= 8; i++){cin >> FinalStatus[i];}beginTime = clock();//判斷0數(shù)碼的位置for (i = 0; i <= 8; i++){if (fstatus[i] == 0)break;}//獲得初始節(jié)點FNode = EightNumInit(fstatus, i, 0, NULL, 0);//將初始節(jié)點放入OPEN中OPEN[open] = *FNode;open++;//尋找最佳路徑EndNode = Search();if (!EndNode)cout << "無解" << endl;elseShowStep(EndNode); //展示步驟endTime = clock();cout << "Run Time:" << endTime - beginTime << "ms" << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的题目2：隐式图的搜索问题（A*算法解决八数码）代码实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。