昆明理工大学人工智能八数码难题实验报告--八数码难题 本文关键词：难题，数码，昆明，人工智能，理工大学
昆明理工大学人工智能八数码难题实验报告--八数码难题 本文简介：昆明理工大学信息工程与自动化学院学生实验报告（2013—2014学年第1学期）课程名称：人工智能开课实验室：信自楼4452013年10月25日年级、专业、班计科113学号201110405314姓名周国映成绩实验项目名称八数码难题指导教师刘英莉教师评语该同学是否了解实验原理：A.了解□B.基本了解□
昆明理工大学人工智能八数码难题实验报告--八数码难题 本文内容：
昆明理工大学信息工程与自动化学院学生实验报告
（
2013
—
2014
学年
第
1
学期
）
课程名称：人工智能
开课实验室：信自楼445
2013
年10月
25日
年级、专业、班
计科113
学号
201110405314
姓名
周国映
成绩
实验项目名称
八数码难题
指导教师
刘英莉
教师评语
该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□
该同学的实验能力：A.强
□B.中等
□C.差
□
该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□
实验报告是否规范：A.规范□B.基本规范□C.不规范□
实验过程是否详细记录：A.详细□B.一般
□
C.没有
□
教师签名：*年*月*日
一、上机目的及内容
1.上机内容
用确定性推理算法求解教材65-66页介绍的八数码难题。
2.上机目的
（1）复习程序设计和数据结构课程的相关知识，实现课程间的平滑过渡；
（2）掌握并实现在小规模状态空间中进行图搜索的方法；
（3）理解并掌握图搜索的技术要点。
二、实验原理及基本技术路线图（方框原理图或程序流程图）
（1）设计并实现程序，求解出正确的解答路径；
（2）对所设计的算法采用大O符号进行时间复杂性和空间复杂性分析；
（3）对一般图搜索的技术要点和技术难点进行评述性分析。
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1台PC及VISUAL
C++6.0软件
四、实验方法、步骤（或：程序代码或操作过程）
1、先创建项目，新建Source
File文件：main.cpp。
#include
#include
“Node.h“#include
“Queue.h“#include
“Search.h“#include
“Tree.h“void
CreateNode1(std::vector
s.push_back(8);
s.push_back(3);
s.push_back(1);
s.push_back(0);
s.push_back(4);
s.push_back(7);
s.push_back(6);
s.push_back(5);
}
void
CreateNode4(std::vector
d.push_back(8);
d.push_back(3);
d.push_back(1);
d.push_back(6);
d.push_back(4);
d.push_back(7);
d.push_back(0);
d.push_back(5);
}
void
CreateNode8(std::vector
d.push_back(2);
d.push_back(3);
d.push_back(1);
d.push_back(8);
d.push_back(4);
d.push_back(7);
d.push_back(6);
d.push_back(5);
}
void
CreateNode20(std::vector
d.push_back(0);
d.push_back(8);
d.push_back(1);
d.push_back(4);
d.push_back(3);
d.push_back(7);
d.push_back(6);
d.push_back(5);
}
void
CreateNode27(std::vector
d.push_back(2);
d.push_back(3);
d.push_back(8);
d.push_back(0);
d.push_back(4);
d.push_back(7);
d.push_back(6);
d.push_back(5);
}
void
CreateNode_test1(std::vector
d.push_back(6);
d.push_back(5);
d.push_back(4);
d.push_back(0);
d.push_back(1);
d.push_back(3);
d.push_back(8);
d.push_back(2);
}
void
test_expand()
{
std::vector
s;
CreateNode1(s);
std::vector
d;
CreateNode4(d);
Node
source(s);
Node
dest(d);
source.Display();
Search
search(
std::cout
s;
CreateNode1(s);
std::vector
d;
CreateNode4(d);
Node
source(s);
Node
dest(d);
source.Display();
dest.Display();
Search
search(
search.Find(
search.DisplayRoute();
}
void
test_search2level()
{
std::vector
s;
CreateNode1(s);
std::vector
d;
CreateNode8(d);
Node
source(s);
Node
dest(d);
source.Display();
dest.Display();
Search
search(
search.Find(
search.DisplayRoute();
}
void
test_search_lab1()
{
std::vector
s;
CreateNode1(s);
std::vector
d;
CreateNode27(d);
Node
source(s);
Node
dest(d);
source.Display();
dest.Display();
Search
search(
search.Find(
search.DisplayRoute();
}
int
main(int
argc,char**
argv)
{
//
test_expand();
//
test_search();
//
test_search2level();
//
test_search_lab1();
std::vector
s;
CreateNode1(s);
std::vector
d;
CreateNode27(d);
Node
source(s);
Node
dest(d);
source.Display();
dest.Display();
Search
search(
search.Find(
search.DisplayRoute();
return
0;
}
2、新建Source
File文件：Node.cpp
#ifndef
PROGECT_1_NODE
#define
PROGECT_1_NODE
#include
#include
“Search.h“enum
OP
{
EMPTY,UP,DOWN,LEFT,RIGHT
};
bool
IsOpposite(OP
opa,OP
opb);
class
Node
{
public:
Node(std::vector
const
bool
Expand(Node
const
void
Display()
const;
void
DisplayRoute()
const;
bool
operator==(Node
const
private:
Node*
CreateChild(OP
op);
int
FindEmptySpaceId()
const;
std::vector
GenerateLegalOperators(int
spaceId)
const;
int
CalIdBasedOP(OP
op,int
spaceId)
const;
bool
IsWithinRange(OP
op,int
spaceId)
const;
std::vector
m_state;
Nodem_pParent;
std::vector
m_children;
OP
m_op;
};
#endif
//
PROGECT_1_NODE
3新建Heard
File文件：node.h。
代码：#include
#include
#include
“Node.h“bool
IsOpposite(OP
opa,OP
opb)
{
if
(LEFT==opa
if
(RIGHT==opa
if
(UP==opa
if
(DOWN==opa
return
false;
}
Node::Node(std::vector
const
id
legalOPs
=
GenerateLegalOperators(spaceId);
ShowOPs(legalOPs);
while
(
legalOPs.size()
>
0
)
{
OP
op
=
legalOPs[
legalOPs.size()
-
1
];
legalOPs.pop_back();
Node*
pChild
=
CreateChild(op);
if
(pChild
==
destNode
)
{
search.SetDestPt(pChild);
return
true;
}
search.GetQueue().EnQueue(pChild);
}
return
false;
}
void
Node::Display()
const
{
for(int
i=0;
i
routeOps;
Node
const*
pNode
=
this;
while
(
NULL
!=
pNode
)
{
routeOps.push_back(pNode->m_op);
pNode
=
pNode->m_pParent;
}
for(int
id=routeOps.size()-2;
id>=0
;
--id)
{
ShowOP(
routeOps[id]
);
std::cout
childState
=
m_state;
int
exchangePos1
=
FindEmptySpaceId();
int
exchangePos2
=
CalIdBasedOP(op,exchangePos1);
int
temp
=
childState[exchangePos1];
childState[exchangePos1]
=
childState[exchangePos2];
childState[exchangePos2]
=
temp;
Node*
child
=
new
Node(childState);
child->m_pParent
=
this;
child->m_op
=
op;
m_children.push_back(child);
return
child;
}
int
Node::FindEmptySpaceId()
const
{
for
(int
id=0;
id
Node::GenerateLegalOperators(int
spaceId)
const
{
std::vector
allPossibleOps;
allPossibleOps.push_back(UP);
allPossibleOps.push_back(DOWN);
allPossibleOps.push_back(LEFT);
allPossibleOps.push_back(RIGHT);
std::vector
ops;
for
(int
id=0;
id=
0
class
Queue
{
public:
void
EnQueue(Node*
pNode);
Node*
DeQueue();
private:
std::deque
m_queue;
};
#endif
//
PROGECT_1_QUEUE
6、新建Source
File文件：Search.cpp，
代码：
#include
“Search.h“#include
“Node.h“Search::Search(Node*
root)
:m_queue(),m_pDestNode(
NULL
)
{
m_queue.EnQueue(root);
}
Node*
Search::Select()
{
return
m_queue.DeQueue();
}
void
Search::Find(Node*
destNode)
{
bool
isFound
=
false;
while
(
!isFound
)
{
Node*
pNode
=
Select();
pNode->Display();
isFound
=
pNode->Expand(*destNode,*this);
}
}
void
Search::DisplayRoute()
const
{
m_pDestNode->DisplayRoute();
}
7新建Heard
File文件：Search.h。
代码：
#ifndef
PROGECT_1_SEARCH
#define
PROGECT_1_SEARCH
#include
“Queue.h“class
Node;
class
Search
{
public:
Search(Node*
root);
Queue
}
void
Find(Node*
destNode);
Node*
Select();
void
SetDestPt(Node*
pDestNode)
{
m_pDestNode
=
pDestNode;
}
void
DisplayRoute()
const;
private:
Queue
m_queue;
Node*
m_pDestNode;
};
#endif
//
PROGECT_1_SEARCH
8、新建Source
File文件：Tree.cpp，
代码：
#include
“Tree.h“9新建Heard
File文件：Tree.h。
代码：
#ifndef
PROGECT_1_TREE
#define
PROGECT_1_TREE
#endif
//
PROGECT_1_TREE
五、实验过程原始记录(
测试数据、图表、计算等)
六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）
通过完成这次八数码难题试验报告，我对编程的理解更深刻了，以前做的很多编程仅仅是
几十行的一个函数的代码，而这次的工作量明显大了很多，需要构建几个
好多文件才能完成，在试验中虽然遇到很多的困难，但在老师同学的帮助下，还是学到了很多知识，这次的试验使我在以后的编程中，思路更加开阔了
-19-