八数码问题求解实验报告

八数码问题求解

（一）实验软件

TC2.0或VC6.0编程语言或其它编程语言

（二）实验目的

1. 熟悉人工智能系统中的问题求解过程；

2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；

3. 熟悉对八数码问题的建模，求解及编程语言的应用。

（三）实验内容

八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有一个方格是空的，要求对空格执行空格左移，空格右移，空格上移，空格下移这四个操作使得棋盘从初始状态到目标状态。输入初始状态和目标状态，输出从初始状态到目标状态的路径。

（四）实验代码

#include"stdafx.h"

#include

#include

#include

usingnamespace std;

constint ROW = 3;

constint COL = 3;

constint MAXDISTANCE = 10000;

constint MAXNUM = 10000;

typedefstruct _Node{

int digit[ROW][COL];

int dist; // distance between one state and the destination int dep; // the depth of node

// So the comment function = dist + dep.

int index; // point to the location of parent

} Node ;

Node src, dest;

vector node_v; // store the nodes

bool isEmptyOfOPEN() {

for (int i = 0; i

if (node_v[i].dist != MAXNUM)

returnfalse ;

}

returntrue ;

}

bool isEqual(int index , int digit [][COL]) {

for (int i = 0; i

for (int j = 0; j

if (node_v[index ].digit[i][j] != digit [i][j])

returnfalse ;

}

returntrue ;

}

ostream & operator

for (int i = 0; i

for (int j = 0; j

os

os

}

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

}

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

for (int j = 0; 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

if (node_v[i].dist == MAXNUM)

continue ;

elseif ((node_v[i].dist + node_v[i].dep)

loc = i;

dist = node_v[i].dist + node_v[i].dep;

}

}

return loc;

}

bool isExpandable(Node &node ) {

for (int i = 0; i

if (isEqual(i, node .digit))

returnfalse ;

}

returntrue ;

}//扩展

int Distance(Node &node , int digit [][COL]) {

int distance = 0;

bool flag = false ;

for (int i = 0; i

for (int j = 0; j

for (int k = 0; k

for (int l = 0; l

if (node .digit[i][j] == digit [k][l]) {

distance += abs(i - k) + abs(j - l);//abs()求得是正数的绝对值。

flag = true ;

break ;

}

else

flag = false ;

}

if (flag)

break ;

}

return distance;

}

int MinDistance(int a , int b ) {

return (a

}

void ProcessNode(int index ) {

int x, y;

bool flag;

for (int i = 0; i

for (int j = 0; j

if (node_v[index ].digit[i][j] == 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.digit[x][y], node_up.digit[x - 1][y]); if (isExpandable(node_up)) {

dist_up = Distance(node_up, dest.digit);

node_up.index = index ;

node_up.dist = dist_up;

node_up.dep = node_v[index ].dep + 1;

node_v.push_back(node_up);

}

}

Node node_down;

Assign(node_down, index );

int dist_down = MAXDISTANCE;

if (x

Swap(node_down.digit[x][y], node_down.digit[x + 1][y]);

if (isExpandable(node_down)) {

dist_down = Distance(node_down, dest.digit); node_down.index = index ;

node_down.dist = dist_down;

node_down.dep = node_v[index ].dep + 1;

node_v.push_back(node_down);

} }

Node node_left;

Assign(node_left, index );

int dist_left = MAXDISTANCE;

if (y > 0) {

Swap(node_left.digit[x][y], node_left.digit[x][y - 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_v[index ].dep + 1;

node_v.push_back(node_left);

}

}

Node node_right;

Assign(node_right, index );

int dist_right = MAXDISTANCE;

if (y

Swap(node_right.digit[x][y], node_right.digit[x][y + 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_v[index ].dep + 1;

node_v.push_back(node_right);

}

}

node_v[index ].dist = MAXNUM;

}

int main() {

int number;

cout

for (int i = 0; i

for (int j = 0; j

cin >> number;

src.digit[i][j] = number;

}

src.index = 0;

src.dep = 1;

cout

for (int m = 0; m

for (int n = 0; n

cin >> number;

dest.digit[m][n] = number;

}

node_v.push_back(src);

cout

clock_t start = clock();

while (1) {

if (isEmptyOfOPEN()) {

cout

}

else {

int loc; // the location of the minimize node loc = GetMinNode();

if (isEqual(loc, dest.digit)) {

vector rstep_v;

cout

cout

PrintSteps(loc, rstep_v);

cout

cout

break ;

}

else

ProcessNode(loc);

}

}

system("Pause" );

}

（五）实验结果截图

八数码问题求解

（一）实验软件

TC2.0或VC6.0编程语言或其它编程语言

（二）实验目的

1. 熟悉人工智能系统中的问题求解过程；

2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；

3. 熟悉对八数码问题的建模，求解及编程语言的应用。

（三）实验内容

八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有一个方格是空的，要求对空格执行空格左移，空格右移，空格上移，空格下移这四个操作使得棋盘从初始状态到目标状态。输入初始状态和目标状态，输出从初始状态到目标状态的路径。

（四）实验代码

#include"stdafx.h"

#include

#include

#include

usingnamespace std;

constint ROW = 3;

constint COL = 3;

constint MAXDISTANCE = 10000;

constint MAXNUM = 10000;

typedefstruct _Node{

int digit[ROW][COL];

int dist; // distance between one state and the destination int dep; // the depth of node

// So the comment function = dist + dep.

int index; // point to the location of parent

} Node ;

Node src, dest;

vector node_v; // store the nodes

bool isEmptyOfOPEN() {

for (int i = 0; i

if (node_v[i].dist != MAXNUM)

returnfalse ;

}

returntrue ;

}

bool isEqual(int index , int digit [][COL]) {

for (int i = 0; i

for (int j = 0; j

if (node_v[index ].digit[i][j] != digit [i][j])

returnfalse ;

}

returntrue ;

}

ostream & operator

for (int i = 0; i

for (int j = 0; j

os

os

}

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

}

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

for (int j = 0; 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

if (node_v[i].dist == MAXNUM)

continue ;

elseif ((node_v[i].dist + node_v[i].dep)

loc = i;

dist = node_v[i].dist + node_v[i].dep;

}

}

return loc;

}

bool isExpandable(Node &node ) {

for (int i = 0; i

if (isEqual(i, node .digit))

returnfalse ;

}

returntrue ;

}//扩展

int Distance(Node &node , int digit [][COL]) {

int distance = 0;

bool flag = false ;

for (int i = 0; i

for (int j = 0; j

for (int k = 0; k

for (int l = 0; l

if (node .digit[i][j] == digit [k][l]) {

distance += abs(i - k) + abs(j - l);//abs()求得是正数的绝对值。

flag = true ;

break ;

}

else

flag = false ;

}

if (flag)

break ;

}

return distance;

}

int MinDistance(int a , int b ) {

return (a

}

void ProcessNode(int index ) {

int x, y;

bool flag;

for (int i = 0; i

for (int j = 0; j

if (node_v[index ].digit[i][j] == 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.digit[x][y], node_up.digit[x - 1][y]); if (isExpandable(node_up)) {

dist_up = Distance(node_up, dest.digit);

node_up.index = index ;

node_up.dist = dist_up;

node_up.dep = node_v[index ].dep + 1;

node_v.push_back(node_up);

}

}

Node node_down;

Assign(node_down, index );

int dist_down = MAXDISTANCE;

if (x

Swap(node_down.digit[x][y], node_down.digit[x + 1][y]);

if (isExpandable(node_down)) {

dist_down = Distance(node_down, dest.digit); node_down.index = index ;

node_down.dist = dist_down;

node_down.dep = node_v[index ].dep + 1;

node_v.push_back(node_down);

} }

Node node_left;

Assign(node_left, index );

int dist_left = MAXDISTANCE;

if (y > 0) {

Swap(node_left.digit[x][y], node_left.digit[x][y - 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_v[index ].dep + 1;

node_v.push_back(node_left);

}

}

Node node_right;

Assign(node_right, index );

int dist_right = MAXDISTANCE;

if (y

Swap(node_right.digit[x][y], node_right.digit[x][y + 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_v[index ].dep + 1;

node_v.push_back(node_right);

}

}

node_v[index ].dist = MAXNUM;

}

int main() {

int number;

cout

for (int i = 0; i

for (int j = 0; j

cin >> number;

src.digit[i][j] = number;

}

src.index = 0;

src.dep = 1;

cout

for (int m = 0; m

for (int n = 0; n

cin >> number;

dest.digit[m][n] = number;

}

node_v.push_back(src);

cout

clock_t start = clock();

while (1) {

if (isEmptyOfOPEN()) {

cout

}

else {

int loc; // the location of the minimize node loc = GetMinNode();

if (isEqual(loc, dest.digit)) {

vector rstep_v;

cout

cout

PrintSteps(loc, rstep_v);

cout

cout

break ;

}

else

ProcessNode(loc);

}

}

system("Pause" );

}

（五）实验结果截图


相关文章

  • 人工智能实验报告

    • 八数码以及十五数码问题 基于人工智能的状态空间搜索策略研究 --八数码问题求解 一.实验问题 八数码问题求解 二.实验软件 VC6.0 编程语言或其它编程语言 三.实验目的 1. 熟悉人工智能系统中的问题求解过程: 2. 熟悉状态空间的盲目 ...查看


  • 实验十二 信号卷积实验报告(有数据)

    • 实验十二 信号卷积实验 一.实验目的 1.理解卷积的概念及物理意义. 2. 通过实验的方法加深对卷积运算的图解方法及结果的理解. 二.实验仪器 1.双踪示波器 1台 2.信号源及频率计模块S2 1块 3.数字信号处理模块S4 1块 三.实验 ...查看


  • 五子棋开题报告

    • 一.选题的依据及意义 五子棋是一种两人对弈的纯策略型棋类游戏,是起源于中国古代的传统黑白棋种之一.发展于日本,流行于欧美.容易上手,老少皆宜,而且趣味横生,引人入胜:五子棋不仅能增强思维能力,提高智力,而且富含哲理,有助于修身养性.五子棋既 ...查看


  • 十五数码问题研究及实现

    • 2010年第2期福建电脑 73 十五数码问题研究及实现 闵文杰 (重庆交通大学重庆400047) [摘要]:十五数码问题是人工智能领域中的一个典型问题.本文对该问题进行了详细分析,并用启发式搜索解决了该问题,同时比较了3种不同评估函数的效率 ...查看


  • 遗传算法求解TSP问题实验报告

    • 人工智能实验报告 实验六 遗传算法实验II 一.实验目的: 熟悉和掌握遗传算法的原理.流程和编码策略,并利用遗传求解函数优化问题,理解求解TSP问题的流程并测试主要参数对结果的影响. 二.实验原理: 旅行商问题,即TSP问题(Traveli ...查看


  • 管理运筹学实验报告2

    • 管理运筹学实验报告 班级: 姓名: 学号: 10级物流管理一班 高雪盛 电子商务与物流管理学院 二○一二年九月 实验二 一. 实验名称:线性规划问题的建模及求解⑴ 二. 实验目的: ⑴通过本实验使学生掌握建立线性优化模型的方法和工作步骤: ...查看


  • 微机原理实验报告三 七段数码显示

    • 七段数码显示 一, 实验目的: 掌握接口芯片的编址方法,掌握8255的初始化设置,及数码管显示原理,掌握段控及位控的概念. 二, 实验内容: 1, 2, 3, 连接地址译码器与8255的接线及8255与数码管的连线. 在数据段中存放0到9的 ...查看


  • 物理:5.4[实验:研究平抛运动]教案(新人教必修2)

    • 5.4 实验:研究平抛运动 [教学目标] 知识与技能 1. 掌握平抛运动在竖直方向的运动特点. 2. 掌握平抛运动在水平方向的运动特点. 过程与方法 探究过程,体会平抛运动在竖直和水平方向的运动规律. 情感态度与价值观 设计平抛运动的轨迹, ...查看


  • 运筹学上机报告最短路问题的计算机求解

    • 运筹学上机实验报告单 20 14 -20 15 学年第 2 学期 实验名称 最短路问题的计算机求解 班级 实验 目的 姓名 日期:2015 年 5 学号 月 26 日 掌握最短路问题的计算机求解方法. 实验 内容 (1)最短路问题的 lin ...查看


热门内容