昆明理工大学八数码实验报告

昆明理工大学信息工程与自动化学院学生实验报告（ 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.上机内容：求解八数码问题。问题描述：八数码难题，问题描述：在33方格棋盘上，分别放置了标有数字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放入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 #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_pDestNode-DisplayRoute();7新建Heard File文件：Search.h。#ifndef PROGECT_1_SEARCH#define PROGECT_1_SEARCH#include Queue.hclass 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.h9、新建Heard File文件：Tree.h。#ifndef PROGECT_1_TREE#define PROGECT_1_TREE#endif / PROGECT_1_TREE五、实验过程原始记录( 测试数据、图表、计算等)六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）人工智能这门课程综合了许多学科的知识，这些知识面十分广，以及它的应用也是十分广泛的，才刚开始学习的时候就会感觉有点复杂，因为它毕竟综合了一些我们还没有学过的知识。通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。用广度优先算法实现八数码问题，其实是一种比较费劲的方式；然而深度优先将是一个很好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程有了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验使我受益匪浅。