昆明理工大学信息工程与自动化学院学生实验报告
（ 20XX — 20XX 学年 第 1 学期 ）
课程名称：人工智能 开课实验室：信自楼445
20XX年10月 25日
一、上机目的及内容
1.上机内容
用确定性推理算法求解教材65-66页介绍的八数码难题。
2.上机目的
（1）复习程序设计和数据结构课程的相关知识，实现课程间的平滑过渡；
（2）掌握并实现在小规模状态空间中进行图搜索的方法；
（3）理解并掌握图搜索的技术要点。
二、实验原理及基本技术路线图（方框原理图或程序流程图）
（1）设计并实现程序，求解出正确的解答路径；
（2）对所设计的算法采用大O符号进行时间复杂性和空间复杂性分析；
（3）对一般图搜索的技术要点和技术难点进行评述性分析。
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1台PC及VISUAL C++6.0软件
四、实验方法、步骤（或：程序代码或操作过程）
1、先创建项目，新建Source File文件：main.cpp。
#include ＜iostream＞
#include "Node.h"
#include "Queue.h"
#include "Search.h"
#include "Tree.h"
void CreateNode1(std::vector＜int＞& s)
{
s.push_back(2);
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＜int＞& d)
{
d.push_back(2);
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＜int＞& d)
{
d.push_back(0);
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＜int＞& d)
{
d.push_back(2);
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＜int＞& d)
{
d.push_back(1);
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＜int＞& d)
{
d.push_back(7);
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＜int＞ s;
CreateNode1(s);
std::vector＜int＞ d;
CreateNode4(d);
Node source(s);
Node dest(d);
source.Display();
Search search(&source);
std::cout ＜＜ source.Expand(dest, search);
}
void test_search()
{
std::vector＜int＞ s;
CreateNode1(s);
std::vector＜int＞ d;
CreateNode4(d);
Node source(s);
Node dest(d);
source.Display();
dest.Display();
Search search(&source);
search.Find( & dest);
search.DisplayRoute();
}
void test_search2level()
{
std::vector＜int＞ s;
CreateNode1(s);
std::vector＜int＞ d;
CreateNode8(d);
Node source(s);
Node dest(d);
source.Display();
dest.Display();
Search search(&source);
search.Find( & dest);
search.DisplayRoute();
}
void test_search_lab1()
{
std::vector＜int＞ s;
CreateNode1(s);
std::vector＜int＞ d;
CreateNode27(d);
Node source(s);
Node dest(d);
source.Display();
dest.Display();
Search search(&source);
search.Find( & dest);
search.DisplayRoute();
}
int main(int argc, char** argv)
{
// test_expand();
// test_search();
// test_search2level();
// test_search_lab1();
std::vector＜int＞ s;
CreateNode1(s);
std::vector＜int＞ d;
CreateNode27(d);
Node source(s);
Node dest(d);
source.Display();
dest.Display();
Search search(&source);
search.Find( & dest);
search.DisplayRoute();
return 0;
}
2、新建Source File文件：Node.cpp
#ifndef PROGECT_1_NODE
#define PROGECT_1_NODE
#include ＜vector＞
#include "Search.h"
enum OP
{
EMPTY,
UP,
DOWN,
LEFT,
RIGHT
};
bool IsOpposite(OP opa, OP opb);
class Node
{
public:
Node(std::vector＜int＞ const& state);
bool Expand(Node const& destNode, Search& search);
void Display() const;
void DisplayRoute() const;
bool operator==(Node const& v) const;
private:
Node* CreateChild(OP op);
int FindEmptySpaceId() const;
std::vector＜OP＞ GenerateLegalOperators(int spaceId) const;
int CalIdBasedOP(OP op, int spaceId) const;
bool IsWithinRange(OP op, int spaceId) const;
std::vector＜int＞ m_state;
Node *m_pParent;
std::vector＜Node*＞ m_children;
OP m_op;
};
#endif // PROGECT_1_NODE
3新建Heard File文件：node.h。
代码：#include ＜iostream＞
#include ＜math.h＞
#include "Node.h"
bool IsOpposite(OP opa, OP opb)
{
if (LEFT==opa && RIGHT == opb)
return true;
if (RIGHT==opa && LEFT == opb)
return true;
if (UP==opa && DOWN == opb)
return true;
if (DOWN==opa && UP == opb)
return true;
return false;
}
Node::Node(std::vector＜int＞ const& state)
: m_state(state)
, m_pParent(NULL)
, m_children()
, m_op(EMPTY)
{
}
void ShowOP(OP op)
{
switch (op)
{
case EMPTY:
std::cout ＜＜ "EMPTY";
break;
case UP:
std::cout ＜＜ "UP";
break;
case DOWN:
std::cout ＜＜ "DOWN";
break;
case LEFT:
std::cout ＜＜ "LEFT";
break;
case RIGHT:
std::cout ＜＜ "RIGHT";
break;
default:
exit(-1);
}
}
void ShowOPs(std::vector＜OP＞ const& ops)
{
for (int id=0; id＜ops.size(); ++id)
{
ShowOP(ops[id]);
std::cout ＜＜ " ";
}
std::cout ＜＜ std::endl;
}
bool Node::Expand(Node const& destNode, Search& search)
{
int spaceId = FindEmptySpaceId();
std::cout ＜＜ "space is at " ＜＜ spaceId ＜＜ std::endl;
std::vector＜OP＞ 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＜m_state.size(); ++i)
{
std::cout ＜＜ m_state[i] ＜＜ " ";
}
std::cout ＜＜ std::endl;
std::cout ＜＜ " pParent: " ＜＜ m_pParent ＜＜ std::endl;
std::cout ＜＜ " op: ";
ShowOP(m_op);
std::cout ＜＜ std::endl;
std::cout ＜＜ " ";
for(int j=0; j＜m_children.size(); ++j)
{
std::cout ＜＜ m_children[j] ＜＜ " ";
}
std::cout ＜＜ std::endl;
}
void Node::DisplayRoute() const
{
std::vector＜OP＞ 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 ＜＜ " ";
}
std::cout ＜＜ std::endl;
}
bool Node::operator==(Node const& v) const
{
for (int id=0; id＜m_state.size(); ++ id)
{
if ( m_state[id] != v.m_state[id] )
return false;
}
return true;
}
Node* Node::CreateChild(OP op)
{
std::vector＜int＞ 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＜m_state.size(); ++id)
{
if ( 0 == m_state[id] )
{
return id;
}
}
return -1;
}
std::vector＜OP＞ Node::GenerateLegalOperators(int spaceId) const
{
std::vector＜OP＞ allPossibleOps;
allPossibleOps.push_back(UP);
allPossibleOps.push_back(DOWN);
allPossibleOps.push_back(LEFT);
allPossibleOps.push_back(RIGHT);
std::vector＜OP＞ ops;
for (int id=0; id＜allPossibleOps.size(); ++id)
{
OP op = allPossibleOps[id];
if( IsOpposite(op, m_op) )
{
continue;
}
if ( IsWithinRange(op, spaceId) )
{
ops.push_back(op);
}
}
return ops;
}
int Node::CalIdBasedOP(OP op, int spaceId) const
{
switch (op)
{
case UP:
spaceId -= int( sqrt( m_state.size() ) );
break;
case DOWN:
spaceId += int( sqrt( m_state.size() ) );
break;
case LEFT:
--spaceId;
break;
case RIGHT:
++spaceId;
break;
default:
return -1;
}
return spaceId;
}
bool Node::IsWithinRange(OP op, int spaceId) const
{
spaceId = CalIdBasedOP(op, spaceId);
if (spaceId ＞= 0 && spaceId ＜ m_state.size())
{
return true;
}
return false;
}
4、新建Source File文件：Queue.cpp，
代码：#include "Queue.h"
void Queue::EnQueue(Node* pNode)
{
m_queue.push_back(pNode);
}
Node* Queue::DeQueue()
{
if ( m_queue.size() == 0 )
{
return NULL;
}
Node* pNode = m_queue[0];
m_queue.pop_front();
return pNode;
}
5新建Heard File文件：Queue.h。
代码：
#ifndef PROGECT_1_QUEUE
#define PROGECT_1_QUEUE
#include ＜deque＞
class Node;
class Queue
{
public:
void EnQueue(Node* pNode);
Node* DeQueue();
private:
std::deque＜Node*＞ 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& GetQueue()
{
return m_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
五、实验过程原始记录( 测试数据、图表、计算等)
六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）
通过完成这次八数码难题试验报告，我对编程的理解更深刻了，以前做的很多编程仅仅是
几十行的一个函数的代码，而这次的工作量明显大了很多，需要构建几个
好多文件才能完成，在试验中虽然遇到很多的困难，但在老师同学的帮助下，还是学到了很多知识，这次的试验使我在以后的编程中，思路更加开阔了