昆明理工大学人工智能八数码难题实验报告
昆明理工大学信息工程与自动化学院学生实验报告
（2013 —2014 学年第 1 学期）
课程名称：人工智能开课实验室：信自楼445 2013 年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
#include "Node.h"
#include "Queue.h"
#include "Search.h"
#include "Tree.h"
void CreateNode1(std::vector
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.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.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.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.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.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
CreateNode1(s);
std::vector
CreateNode4(d);
Node source(s);
Node dest(d);
source.Display();
Search search(&source);
std::cout << source.Expand(dest, search); }
void test_search()
{
std::vector
CreateNode1(s);
std::vector
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
CreateNode1(s);
std::vector
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
CreateNode1(s);
std::vector
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
CreateNode1(s);
std::vector
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.h"
enum OP
{
EMPTY,
UP,
DOWN,
LEFT,
RIGHT
};
bool IsOpposite(OP opa, OP opb);
class Node
{
public:
Node(std::vector
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
int CalIdBasedOP(OP op, int spaceId) const;
bool IsWithinRange(OP op, int spaceId) const;
std::vector
Node *m_pParent;
std::vector
OP m_op;
};
#endif // PROGECT_1_NODE
3新建Heard File文件：node.h。
代码：#include
#include
#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
, 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
{
for (int id=0; 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 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 { 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 { std::cout << m_children[j] << " "; } std::cout << std::endl; } void Node::DisplayRoute() const { std::vector 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 { if ( m_state[id] != v.m_state[id] ) return false; } return true; } Node* Node::CreateChild(OP op) { std::vector 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 { if ( 0 == m_state[id] ) { return id; } } return -1; } std::vector std::vector allPossibleOps.push_back(UP); allPossibleOps.push_back(DOWN); allPossibleOps.push_back(LEFT); allPossibleOps.push_back(RIGHT); std::vector for (int id=0; 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 class Node; class Queue { public: void EnQueue(Node* pNode); Node* DeQueue(); private: std::deque }; #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 五、实验过程原始记录( 测试数据、图表、计算等) 六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获） 通过完成这次八数码难题试验报告，我对编程的理解更深刻了，以前做的很多编程仅仅是几十行的一个函数的代码，而这次的工作量明显大了很多，需要构建几个 好多文件才能完成，在试验中虽然遇到很多的困难，但在老师同学的帮助下，还是学到了很多知识，这次的试验使我在以后的编程中，思路更加开阔了