昆明理工大学人工智能八数码难题实验报告.doc
昆明理工大学信息工程与自动化学院学生实验报告（ 2013 2014 学年 第 1 学期 ）课程名称：人工智能 开课实验室：信自楼445 2013 年10月 25日年级、专业、班计科113学号4姓名周国映成绩实验项目名称八数码难题指导教师 刘英莉教师评语该同学是否了解实验原理：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 <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 OPEMPTY,UP,DOWN,LEFT,RIGHT;bool IsOpposite(OP opa, OP opb);class Nodepublic: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_NODE3新建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(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<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() constfor(int i=0; i<m_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; j<m_children.size(); +j)std:cout << m_childrenj << " "std:cout << std:endl;void Node:DisplayRoute() conststd: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( routeOpsid );std:cout << " "std:cout << std:endl;bool Node:operator=(Node const& v) constfor (int id=0; id<m_state.size(); + id)if ( m_stateid != v.m_stateid )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 = 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; id<m_state.size(); +id)if ( 0 = m_stateid )return id;return -1;std:vector<OP> Node:GenerateLegalOperators(int spaceId) conststd: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 = allPossibleOpsid;if( IsOpposite(op, m_op) )continue;if ( IsWithinRange(op, spaceId) )ops.push_back(op);return ops;int Node:CalIdBasedOP(OP op, int spaceId) constswitch (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) constspaceId = 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_queue0;m_queue.pop_front();return pNode;5新建Heard File文件：Queue.h。代码：#ifndef PROGECT_1_QUEUE#define PROGECT_1_QUEUE#include <deque>class Node;class Queuepublic:void EnQueue(Node* pNode);Node* DeQueue();private:std:deque<Node*> m_queue;#endif / PROGECT_1_QUEUE6、新建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() constm_pDestNode->DisplayRoute();7新建Heard File文件：Search.h。代码：#ifndef PROGECT_1_SEARCH#define PROGECT_1_SEARCH#include "Queue.h"class Node;class Searchpublic: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_SEARCH8、新建Source File文件：Tree.cpp，代码：#include "Tree.h"9新建Heard File文件：Tree.h。代码：#ifndef PROGECT_1_TREE#define PROGECT_1_TREE#endif / PROGECT_1_TREE五、实验过程原始记录( 测试数据、图表、计算等)六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获） 通过完成这次八数码难题试验报告，我对编程的理解更深刻了，以前做的很多编程仅仅是几十行的一个函数的代码，而这次的工作量明显大了很多，需要构建几个好多文件才能完成，在试验中虽然遇到很多的困难，但在老师同学的帮助下，还是学到了很多知识，这次的试验使我在以后的编程中，思路更加开阔了
