人工智能(A星算法)

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

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

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

4、可能需要指數(shù)級(jí)的計(jì)算代價(jià)。實(shí)驗(yàn)步驟算法流程圖開(kāi)始讀入棋局初始狀態(tài)是否可解否o是o初始狀態(tài)加入open表在open表中找到評(píng)價(jià)值最小的節(jié)點(diǎn)，作為當(dāng)前結(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)是o否o擴(kuò)展新?tīng)顟B(tài)，把不重復(fù)的新?tīng)顟B(tài)加入open表中當(dāng)前結(jié)點(diǎn)從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; /一個(gè)表和目的表的距離 int dep; / t深度 int index; /節(jié)點(diǎn)的位置 Node;Node src, dest;/ 父節(jié)表 目的表vector<Node> node_v; /存儲(chǔ)節(jié)點(diǎn)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) /判斷這個(gè)最優(yōu)的節(jié)點(diǎn)是否和目的節(jié)點(diǎn)一樣 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)/輸出每一個(gè)遍歷的節(jié)點(diǎn) 深度遍歷 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-)/輸出每一步的探索過(guò)程 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é)點(diǎn)的位置 即最優(yōu)節(jié)點(diǎn) 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);/向上擴(kuò)展的節(jié)點(diǎn) 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);/向下擴(kuò)展的節(jié)點(diǎn) 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);/向左擴(kuò)展的節(jié)點(diǎn) 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、);/向右擴(kuò)展的節(jié)點(diǎn) 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);/在容器的尾部加一個(gè)數(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