人工智能_八數(shù)碼實(shí)驗(yàn)報(bào)告

1、人工智能_八數(shù)碼實(shí)驗(yàn)報(bào)告 西安郵電大學(xué) 人工智能實(shí)驗(yàn) 報(bào) 告 書（三） 學(xué)院：自動(dòng)化學(xué)院 專業(yè)：智能科學(xué)與技術(shù) 班級(jí)：智能 1403 姓名：劉忠強(qiáng) 時(shí)間：2021-3-29 一、實(shí)驗(yàn)?zāi)康?1. 熟悉人工智能系統(tǒng)中的問題求解過程； 2. 熟悉狀態(tài)空間的盲目搜索策略； 3.掌握盲目收索算法，重點(diǎn)是寬度優(yōu)先收索和深度優(yōu)先收索。 二、實(shí)驗(yàn)算法 廣度優(yōu)先收索是一種先生成的節(jié)點(diǎn)先擴(kuò)展的策略。它的過程是：從初始節(jié)點(diǎn)開始逐層向下擴(kuò)展，再第 n 層節(jié)點(diǎn)還沒有完全搜索之前，不進(jìn)如第 n+1 層節(jié)點(diǎn)。open 表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，夠進(jìn)入的排在后面。 三、程序框圖 四、實(shí)驗(yàn)結(jié)果及分析

2、 初始狀態(tài)： 目標(biāo)狀態(tài)： 2 8 3 2 1 6 1 6 4 4 0 8 7 0 5 7 5 3 五、源程序及解釋 #include iostream #include ctime #include vector using namespace std; const int row = 3; const int col = 3; const int maxdistance = 10000; const int maxnum = 10000; int abs(int a) if (a0) return a; else return -a; typedef struct _node int dig

3、itrowcol; int dist; / 距離 int dep; / 深度 int index; / 索引值 node; node src, dest; vectornode 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; return true; bool isequal(int index, int digitcol) /判斷節(jié)點(diǎn)是否與索引值指向的節(jié)點(diǎn)相同 for (int i =

4、 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 = 0; j col; j+) os node.digitij " " os endl; return os; void printsteps(int index, vectornode rstep_v) /輸出步

5、驟 rstep_v.push_back(node_vindex); index = node_vindex.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.index; 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(

6、node node, int index) /獲取節(jié)點(diǎn) for (int i = 0; i row; i+) for (int j = 0; j col; j+) node.digitij = node_vindex.digitij; int getminnode() /獲取啟發(fā)值最小的節(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.di

7、st + node_vi.dep) dist) loc = i; dist = node_vi.dist + node_vi.dep; return loc; bool isexpandable(node node) /判斷是否可擴(kuò)展 for (int i = 0; i node_v.size(); i+) if (isequal(i, node.digit) return false; return true; int distance(node node, int digitcol) /計(jì)算距離 int distance = 0; bool flag = false; for(int i

8、= 0; i row; i+) for (int j = 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 pr

9、ocessnode(int index) /展開節(jié)點(diǎn) 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); int dist_up = maxdistance; if (x 0) swap(node_up.digitxy,

10、 node_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); int dist_down = maxdistance; if (x 2) swap(node_down.

11、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); int dist_left = maxdistance;

12、 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);

13、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_right); node_vindex

14、.dist = maxnum; int main() int number; cout 輸入初始狀態(tài): 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 輸入目標(biāo)狀態(tài) 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); while (1) if (isemptyofopen() cout 找不到解! endl; return -1; else int loc; / the location of the minimize node loc = getminnode(); if(isequal(loc, dest.digit) vectornode rstep_v; cout 初始狀態(tài)： endl; cout src endl; printsteps(loc, rstep_v); cout 成功! endl; b