人工智能(A星算法)

1、人工智能A*算法實驗報告實驗?zāi)康?熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程2. 學(xué)會利用A*算法求解N數(shù)碼難題3. 理解求解流程和搜索順序?qū)嶒炘鞟*算法是一種有序搜索算法，其特點在于對估價函數(shù)的定義上。對于一般的有序搜索，總是選擇f值最小的節(jié)點作為擴展節(jié)點。因此，f是根據(jù)需要找到一條最小代價路徑的觀點來估算節(jié)點的，所以，可考慮每個節(jié)點n的估價函數(shù)值為兩個分量：從起始節(jié)點到節(jié)點n的代價以及從節(jié)點n到達目標節(jié)點的代價。實驗條件1. Window NT/xp/7及以上的操作系統(tǒng)2. 內(nèi)存在512M以上3. CPU在奔騰II以上實驗內(nèi)容1. 分別以8數(shù)碼和15數(shù)碼為例實際求解A*算法2. 畫出

2、A*算法求解框圖3. 分析估價函數(shù)對搜索算法的影響4. 分析A*算法的特點實驗分析1. A*算法基本步驟1）生成一個只包含開始節(jié)點n0的搜索圖G，把n0放在一個叫OPEN的列表上。2）生成一個列表CLOSED，它的初始值為空。3）如果OPEN表為空，則失敗退出。4）選擇OPEN上的第一個節(jié)點，把它從OPEN中移入CLPSED，稱該節(jié)點為n。5）如果n是目標節(jié)點，順著G中，從n到n0的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個搜索樹，在第7步建立）。6）擴展節(jié)點n，生成其后繼結(jié)點集M，在G中，n的祖先不能在M中。在G中安置M的成員，使他們成為n的后繼。7）從M的每一個不在G中的成

3、員建立一個指向n的指針（例如，既不在OPEN中，也不在CLOSED中）。把M1的這些成員加到OPEN中。對M的每一個已在OPEN中或CLOSED中的成員m，如果到目前為止找到的到達m的最好路徑通過n，就把它的指針指向n。對已在CLOSED中的M的每一個成員，重定向它在G中的每一個后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先。8）按遞增f*值，重排OPEN（相同最小f*值可根據(jù)搜索樹中的最深節(jié)點來解決）。9）返回第3步。在第7步中，如果搜索過程發(fā)現(xiàn)一條路徑到達一個節(jié)點的代價比現(xiàn)存的路徑代價低，就要重定向指向該節(jié)點的指針。已經(jīng)在CLOSED中的節(jié)點子孫的重定向保存了后面的搜索結(jié)果，但是

4、可能需要指數(shù)級的計算代價。實驗步驟算法流程圖開始讀入棋局初始狀態(tài)是否可解否o是o初始狀態(tài)加入open表在open表中找到評價值最小的節(jié)點，作為當前結(jié)點是目標節(jié)點是o否o擴展新狀態(tài)，把不重復(fù)的新狀態(tài)加入open表中當前結(jié)點從open表移除結(jié)束輸出結(jié)果程序代碼#include <iostream>#include <ctime>#include <vector>using namespace std;const int ROW = 3;/行數(shù)const int COL = 3;/列數(shù)const int MAXDISTANCE = 10000;/最多可以有的表的數(shù)

5、目const int MAXNUM = 10000;typedef struct _Node int digitROWCOL; int dist; /一個表和目的表的距離 int dep; / t深度 int index; /節(jié)點的位置 Node;Node src, dest;/ 父節(jié)表 目的表vector<Node> node_v; /存儲節(jié)點bool isEmptyOfOPEN() /open表是否為空 for (int i = 0; i < node_v.size(); i+) if (node_vi.dist != MAXNUM) return false; retu

6、rn true;bool isEqual(int index, int digitCOL) /判斷這個最優(yōu)的節(jié)點是否和目的節(jié)點一樣 for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) if (node_vindex.digitij != digitij) return false; return true;ostream& operator<<(ostream& os, Node& node) for (int i = 0; i < ROW; i+) for (int j =

7、0; j < COL; j+) os << node.digitij << ' ' os << endl; return os;void PrintSteps(int index, vector<Node>& rstep_v)/輸出每一個遍歷的節(jié)點 深度遍歷 rstep_v.push_back(node_vindex); index = node_vindex.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.i

8、ndex; for (int i = rstep_v.size() - 1; i >= 0; i-)/輸出每一步的探索過程 cout << "Step " << rstep_v.size() - i << endl << rstep_vi << endl;void Swap(int& a, int& b) int t; t = a; a = b; b = t;void Assign(Node& node, int index) for (int i = 0; i < ROW; i

9、+) for (int j = 0; j < COL; j+) node.digitij = node_vindex.digitij;int GetMinNode() /找到最小的節(jié)點的位置 即最優(yōu)節(jié)點 int dist = MAXNUM; int loc; / the location of minimize node for (int i = 0; i < node_v.size(); i+) if (node_vi.dist = MAXNUM) continue; else if (node_vi.dist + node_vi.dep) < dist) loc = i;

10、 dist = node_vi.dist + node_vi.dep; return loc;bool isExpandable(Node& node) for (int i = 0; i < node_v.size(); i+) if (isEqual(i, node.digit) return false; return true;int Distance(Node& node, int digitCOL) int distance = 0; bool flag = false; for(int i = 0; i < ROW; i+) for (int j =

11、0; j < COL; j+) for (int k = 0; k < ROW; k+) for (int l = 0; l < COL; l+) if (node.digitij = digitkl) distance += abs(i - k) + abs(j - l); flag = true; break; else flag = false; if (flag) break; return distance;int MinDistance(int a, int b) return (a < b ? a : b);void ProcessNode(int ind

12、ex) int x, y; bool flag; for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) if (node_vindex.digitij = 0) x =i; y = j; flag = true; break; else flag = false; if(flag) break; Node node_up; Assign(node_up, index);/向上擴展的節(jié)點 int dist_up = MAXDISTANCE; if (x > 0) Swap(node_up.digitxy, node_

13、up.digitx - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up; node_up.dep = node_vindex.dep + 1; node_v.push_back(node_up); Node node_down; Assign(node_down, index);/向下擴展的節(jié)點 int dist_down = MAXDISTANCE; if (x < 2) Swap(node_down

14、.digitxy, node_down.digitx + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, dest.digit); node_down.index = index; node_down.dist = dist_down; node_down.dep = node_vindex.dep + 1; node_v.push_back(node_down); Node node_left; Assign(node_left, index);/向左擴展的節(jié)點 int dist_left = MAXDISTA

15、NCE; if (y > 0) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpandable(node_left) dist_left = Distance(node_left, dest.digit); node_left.index = index; node_left.dist = dist_left; node_left.dep = node_vindex.dep + 1; node_v.push_back(node_left); Node node_right; Assign(node_right, index

16、);/向右擴展的節(jié)點 int dist_right = MAXDISTANCE; if (y < 2) Swap(node_right.digitxy, node_right.digitxy + 1); if (isExpandable(node_right) dist_right = Distance(node_right, dest.digit); node_right.index = index; node_right.dist = dist_right; node_right.dep = node_vindex.dep + 1; node_v.push_back(node_rig

17、ht); node_vindex.dist = MAXNUM;int main() / 主函數(shù) int number; cout << "Input source:" << endl; for (int i = 0; i < ROW; i+)/輸入初始的表 for (int j = 0; j < COL; j+) cin >> number; src.digitij = number; src.index = 0; src.dep = 1; cout << "Input destination:"

18、; << endl;/輸入目的表 for (int m = 0; m < ROW; m+) for (int n = 0; n < COL; n+) cin >> number; dest.digitmn = number; node_v.push_back(src);/在容器的尾部加一個數(shù)據(jù) cout << "Search." << endl; clock_t start = clock(); while (1) if (isEmptyOfOPEN() cout << "Cann't solve this statement!" << endl; return -1; else int loc; / the location of the minimiz