1 -
昆明理工大学信息工程与自动化学院学生实验报告
（ 2014 — 2015 学年 第 1 学期 ）
课程名称：人工智能及其应用 开课实验室：信自楼504 2014年11月 26日
年级、专业、班
计科122班
学号
201210405204
姓名
邹华宇
成绩
实验项目名称
八数码问题
指导教师
吴霖
教师评语
该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□
该同学的实验能力： A.强 □ B.中等 □ C.差 □
该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□
实验报告是否规范： A.规范□ B.基本规范□ C.不规范□
实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □
教师签名：
年 月 日
一、上机目的及内容
1.上机内容：
求解八数码问题。
问题描述：八数码难题，问题描述：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态S1如图所示，可以使用的操作有：空格上移，空格左移，空格右移，空格下移。只允许位于空格左，上，右，下方的牌移入空格。用广度优先搜索策略寻找从初始状态到目标状态的解路径。
2.上机目的:
（1）复习程序设计和数据结构课程的相关知识；
（2）熟悉人工智能系统中的问题求解过程；
（3）熟悉对八码数问题的建模、求解及编程语言的运用。
二、实验原理及基本技术路线图（方框原理图或程序流程图）
（1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点的表中；
（2）建立一个叫做CLOSED的已扩展节点表，其初始为空表；
（3）LOOP:若OPEN表是空表，则失败退出；
（4）选择OPEN表上的第一个节点，把它从OPEN表移除并放进CLOSED表中，称此节点为节点n；
（5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的；
（6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点舔到图中；
（7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN表或CLOSED表上的成员，确定是否需要更改通到n的指针方向；
（8）按某一任意方式或按某个探视值，重排OPEN表。
开始把S放入
开始
把S放入OPEN表
OPEN表为空
把第一个节点（n）从OPEN移至CLOSED表
n为目标节点
成功
失败
把n的后继节点n放入OPEN表的末端，提供返回节点的指针
修改指针方向
重排OPEN表
（1）把起始节点放到OPEN表中；
（2）如果OPEN是个空表，则没有解，失败退出；否则继续；
（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；
（4）扩展节点n。如果没有后继节点，则转向（2）；
（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；
（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转（2）。
开始
开始
把S放入OPEN表
OPEN表为空
失败
把第一个节点n从把S放入OPEN表移除，放到CLOSED表中
移除
扩展n，把它的后继节点放入OPEN表的末端，提供回到n
的指针
是否任何节点为目标节点
成功
深度优先实现过程
（1）把起始节点S放入未扩展节点OPEN表中。如果此节点为一目标节点，则得一个解；
（2）如果OPEN为一空表，则失败退出；
（3）把第一个节点从OPEN表移到CLOSED表；
（4）如果节点n的深度等于最大深度，则转向（2）；
（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；
（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。
开始
开始
把S放入OPEN表
S是否为目标节点
成功
把第一个节点n从把S放入OPEN表移除，放到CLOSED表中
移除
节点n深度是否等于最深界限
OPEN表为空
失败
扩展n，把它的后继放入OPEN表的前头，提供回到n的指针
是否有任何后继节点为目标节点
成功
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
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
五、实验过程原始记录( 测试数据、图表、计算等)
六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）
人工智能这门课程综合了许多学科的知识，这些知识面十分广，以及它的应用也是十分广泛的，才刚开始学习的时候就会感觉有点复杂，因为它毕竟综合了一些我们还没有学过的知识。
通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。用广度优先算法实现八数码问题，其实是一种比较费劲的方式；然而深度优先将是一个很好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。
这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程有了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验使我受益匪浅。