人工智能_八数码实验报告

1、本文格式为word版，下载可任意编辑人工智能_八数码实验报告 西安郵電高校 人工智能试验 报 告 书（三） 学院：自动化学院 专业：智能科学与技术 班级：智能 1403 姓名：刘忠强 时间：2021-3-29 一、试验目的 1. 熟识人工智能系统中的问题求解过程； 2. 熟识状态空间的盲目搜寻策略； 3.把握盲目收索算法，重点是宽度优先收索和深度优先收索。 二、试验算法 广度优先收索是一种先生成的节点先扩展的策略。它的过程是：从初始节点开头逐层向下扩展，再第 n 层节点还没有完全搜寻之前，不进如第 n+1 层节点。open 表中的节点总是按进入的先后排序，先进入的节点排在前面，够进入的排在后面

2、。 三、程序框图 四、试验结果及分析 初始状态： 目标状态： 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 st

3、ruct _node int digitrowcol; int dist; / 距离 int dep; / 深度 int index; / 索引值 node; node src, dest; vectornode node_v; / 储存节点 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) /推断节点是否与索引值指向

4、的节点相同 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 = 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 a

6、ssign(node node, int index) /猎取节点 for (int i = 0; i row; i+) for (int j = 0; j col; j+) node.digitij = node_vindex.digitij; int getminnode() /猎取启发值最小的节点 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

7、_vi.dist + node_vi.dep) dist) loc = i; 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(

8、int i = 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); v

9、oid processnode(int index) /绽开节点 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.di

10、gitxy, 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

11、_down.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 = maxdis

12、tance; 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, in

13、dex); 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_

14、vindex.dist = maxnum; int main() int number; cout 输入初始状态: 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 输入目标状态 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 初始状态： endl; cout src endl; printsteps(loc, rstep_v); cout 胜利! endl; break; else