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

西安郵電大学

人工智能实验

报 告 书（三）

学院：自动化学院

专业：智能科学与技术

班级：智能1403

姓名：刘忠强

时间：2016-3-29

一、实验目的

1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索策略；

3.掌握盲目收索算法，重点是宽度优先收索和深度优先收索。 二、实验算法

广度优先收索是一种先生成的节点先扩展的策略。它的过程是：从初始节点开始逐层向下扩展，再第n层节点还没有完全搜索之前，不进如第n+1层节点。Open表中的节点总是按进入的先后排序，先进入的节点排在前面，够进入的排在后面。 三、程序框图

四、实验结果及分析

初始状态： 目标状态： 2 8 3 2 1 6 1 6 4 4 0 8 7 0 5 7 5 3

五、源程序及注释

#include #include #include

using namespace std;

const int ROW = 3; const int COL = 3;

const int MAXDISTANCE = 10000; const int MAXNUM = 10000;

int abs(int a) {

if (a>0) return a; else return -a; }

typedef struct _Node{ int digit[ROW][COL]; int dist; // 距离 int dep; // 深度

int index; // 索引值 } Node;

Node src, dest;

vector node_v; // 储存节点

bool isEmptyOfOPEN() { //判断Open表是否空 for (int i = 0; i < node_v.size(); i++) { if (node_v[i].dist != MAXNUM) return false; }

return true; }

bool isEqual(int index, int digit[][COL]) { //判断节点是否与索引值指向的节点相同

for (int i = 0; i < ROW; i++)

for (int j = 0; j < COL; j++) {

if (node_v[index].digit[i][j] != digit[i][j]) 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.digit[i][j] << ' '; os << endl; }

return os; }

void PrintSteps(int index, vector& rstep_v) { //rstep_v.push_back(node_v[index]); index = node_v[index].index; while (index != 0) {

rstep_v.push_back(node_v[index]); index = node_v[index].index; }

for (int i = rstep_v.size() - 1; i >= 0; i--) cout << \ << endl << rstep_v[i] << 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++) for (int j = 0; j < COL; j++)

node.digit[i][j] = node_v[index].digit[i][j]; }

int GetMinNode() { //获取启发值最小的节点 int dist = MAXNUM;

int loc; // the location of minimize node for (int i = 0; i < node_v.size(); i++) { if (node_v[i].dist == MAXNUM)

输出步骤