昆明理工大学人工智能八数码难题实验报告--八数码难题.doc

昆明理工大学信息工程与自动化学院学生实验报告（ 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.hvoid CreateNode1(std:vector& 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& 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& 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& 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& 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& 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 s;CreateNode1(s);std:vector 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 s;CreateNode1(s);std:vector 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 s;CreateNode1(s);std:vector 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 s;CreateNode1(s);std:vector 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 s;CreateNode1(s);std:vector 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 #include Search.henum OPEMPTY,UP,DOWN,LEFT,RIGHT;bool IsOpposite(OP opa, OP opb);class Nodepublic:Node(std:vector 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 GenerateLegalOperators(int spaceId) const;int CalIdBasedOP(OP op, int spaceId) const;bool IsWithinRange(OP op, int spaceId) const;std:vector m_state;Node *m_pParent;std:vector m_children;OP m_op;#endif / PROGECT_1_NODE3新建Heard File文件：node.h。代码：#include #include #include Node.hbool 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 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 const& ops)for (int id=0; idops.size(); +id)ShowOP(opsid);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 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() constfor(int i=0; im_state.size(); +i)std:cout m_statei ;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; jm_children.size(); +j)std:cout m_childrenj ;std:cout std:endl;void Node:DisplayRoute() conststd:vector 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( routeOpsid );std:cout ;std:cout std:endl;bool Node:operator=(Node const& v) constfor (int id=0; idm_state.size(); + id)if ( m_stateid != v.m_stateid )return false;return true;Node* Node:CreateChild(OP op)std:vector childState = m_state;int exchangePos1 = FindEmptySpaceId();int exchangePos2 = CalIdBasedOP(op, exchangePos1);int temp = childStateexchangePos1;childStateexchangePos1 = childStateexchangePos2;childStateexchangePos2 = temp;Node* child = new Node(childState);child-m_pParent = this;child-m_op = op;m_children.push_back(child);return child;int Node:FindEmptySpaceId() constfor (int id=0; idm_state.size(); +id)if ( 0 = m_stateid )return id;return -1;std:vector Node:GenerateLegalOperators(int spaceId) conststd: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 & spaceId m_state.size()return true;return false;4、新建Source File文件：Queue.cpp，代码：#include Queue.hvoid Queue:EnQueue(Node* pNode)m_queue.push_back(pNode);Node* Queue:DeQueue()if ( m_queue.size() = 0 )return NULL;Node* pNode = m_queue0;m_queue.pop_front();return pNode;5新建Heard File文件：Queue.h。代码：#ifndef PROGECT_1_QUEUE#define PROGECT_1_QUEUE#include class Node;class Queuepublic:void EnQueue(Node* pNode);Node* DeQueue();private:std:deque m_queue;#endif / PROGECT_1_QUEUE6、新建Source File文件：Search.cpp，代码：#include Search.h#include Node.hSearch: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() constm_pDest