- 浏览: 173076 次
- 性别:
- 来自: 吉林
文章分类
最新评论
-
zaocha321:
图片全部挂掉了。。
eclipse中新建maven项目 -
springdata_spring:
可以参考最新的文档:如何在eclipse jee中检出项目并转 ...
eclipse中新建maven项目
转载请注明出处:http://hi.baidu.com/lvchengbin405/blog/item/e354fd1faaeb09c0a7866921.html
// 类的定义头文件EDCPP.h #include <stdio.h> #include <stdlib.h> #ifndef _EDCPP_H #define _EDCPP_H struct State{ char value[3][3]; int blankx; // blank position x int blanky; // blank position y }; class EDCNode{ private: int m_index; // ID State* m_state; // state int m_g; // g value int m_h; // h value int m_x; // x coordinate(for drawing) int m_y; // y coordinate(for drawing) int m_parent; public: // 构造与析构函数 EDCNode(); EDCNode(EDCNode& node); ~EDCNode(); // 初始化Node void InitEDCNode(int index, State* s); void InitEDCNode(int index, State* s, int x, int y); void InitEDCNode(int index, State* s, int g, int h, int x, int y); // Set函数 void SetIndex(const int index); void SetState(State* s); void SetG(const int g); void SetH(const int h); void SetX(const int x); void SetY(const int y); void SetParent(int parentindex); // Get函数 int GetIndex(); State* GetState(); int GetG(); int GetH(); int GetF(); int GetX(); int GetY(); int GetParent(); // 静态函数,由类调用 static bool MoveLeft(State* s); // 左移,返回值false表示不可移 static bool MoveRight(State* s); // 右移,返回值false表示不可移 static bool MoveUp(State* s); // 上移,返回值false表示不可移 static bool MoveDown(State* s); // 下移,返回值false表示不可移 static bool Compare(State* s1, State* s2); // 比较两种状态是否一样,返回值false表示不一样 }; #define MAXNUM 100 #define EDC_L 1 #define EDC_R 2 #define EDC_U 3 #define EDC_D 4 class EDC { private: static int m_index;// EDCNode* m_start; // 起始节点 EDCNode* m_end; // 目标节点 EDCNode m_openList[MAXNUM]; // Open表 EDCNode m_closeList[MAXNUM]; // Close表 int m_openNum; // Open表节点个数 int m_closeNum; // Close表节点个数 int m_gParas; // 值为1时选择g(suc)=g(bes)+h(suc,bes),为0时选择g(child)=g(parent)+1 int m_hParasDn; // h(scr,des)=aDn+bPn+cSn,Dn方法的系数a int m_hParasPn; // h(scr,des)=aDn+bPn+cSn,Pn方法的系数b int m_hParasSn; // h(scr,des)=aDn+bPn+cSn,Sn方法的系数c public: // 构造函数 EDC(); // 构造函数2,具备起始节点和目标节点和代价树参数 EDC(EDCNode* start, EDCNode* end, int g, int hd, int hp, int hs); // 析构函数 ~EDC(); EDCNode* GetStart(); EDCNode* GetEnd(); int GetOpenNum(); int GetCloseNum(); EDCNode* GetNodeFromOpenList(int index); EDCNode* GetNodeFromCloseList(int index); void GetParas(int& gParas, int& hParasDn, int& hParasPn, int& hParasSn); void InsertToOpenList(EDCNode* node); // 插入一个节点到Open表中,并构建堆 EDCNode* PopNodeFromOpenList(); // 取Open表首元素,并调整堆 int IsInOpenList(EDCNode* node); // 判断该节点是否在Open表中 void UpdateOpenList(int index); // 更新堆,使第一元素为最小元素 void InsertToCloseList(EDCNode* node); // 插入一个节点到Close表中,按照G值从小到大排序 int IsInCloseList(EDCNode* node); // 判断该节点是否在Close表中 int GetNodeParentFromCloseList(int index); // 获取Close中下标为index的父节点在Close的位置。 EDCNode* ExpandNode(EDCNode* node, int direct); // 扩展子节点 void SetParas(int g, int hd, int hp, int hs); // 设置代价树参数 int CalculateG(EDCNode* node1, EDCNode* node2); // 计算节点的G值,由m_gParas决定计算方式 int CalculateH(EDCNode* node1, EDCNode* node2); // 计算节点1到节点2的H值,h(scr,des)=aDn+bPn+cSn static int DnMethod(EDCNode* node1, EDCNode* node2); // D(n)表示节点node1的格局与node2目标节点格局的不同牌数,包括空格 static int PnMethod(EDCNode* node1, EDCNode* node2); // P(n)是指node1格局各将牌离“家”(node2)的最短路径之和,包括空格 static int SnMethod(EDCNode* node1, EDCNode* node2); /* S(n)计算方法:依照顺时针方向来检查非中心位置的每个奖牌, 若其后紧跟的将牌与目标格局一致,该将牌得0分,否则得2分; 中间方格有将牌得1分,否则得0分。所有将牌得分之和即为S(n)。*/ void StartEDC(); // 启动EDC,为单步遍历做好准备 int EDCOnce(); // 遍历搜索树一次,返回值-1表示失败,0表示继续,1表示成功 bool EDCAll(); // 遍历直到结果出来,返回值ture表示成功,false表示失败 }; #endif; ********************************************************************************************************************* // 类的实现EDCPP.cpp 文件 #include "EDCPP.h" //------------------------------------------------------------------------- // EDCNode class //------------------------------------------------------------------------- EDCNode::EDCNode() { m_index = -1; m_state = new State(); m_g = 0; m_h = 0; m_x = 0; m_y = 0; m_parent = -1; } EDCNode::EDCNode(EDCNode &node) { m_index = node.m_index; m_state = new State(*(node.m_state)); m_g = node.m_g; m_h = node.m_h; m_x = node.m_x; m_y = node.m_y; m_parent = node.m_parent; } EDCNode::~EDCNode() { m_index = -1; if (!m_state) delete m_state; m_state = NULL; m_g = 0; m_h = 0; m_x = 0; m_y = 0; } void EDCNode::InitEDCNode(int index, State* s) { m_index = index; *m_state = *s; } void EDCNode::InitEDCNode(int index, State* s, int x, int y) { m_index = index; *m_state = *s; m_x = x; m_y = y; } void EDCNode::InitEDCNode(int index, State* s, int g, int h, int x, int y) { m_index = index; *m_state = *s; m_g = g; m_h = h; m_x = x; m_y = y; } void EDCNode::SetIndex(const int index) { m_index = index; } void EDCNode::SetState(State* s) { m_state = s; } void EDCNode::SetG(const int g) { m_g = g; } void EDCNode::SetH(const int h) { m_h = h; } void EDCNode::SetX(const int x) { m_x = x; } void EDCNode::SetY(const int y) { m_y = y; } void EDCNode::SetParent(int parentindex) { m_parent = parentindex; } int EDCNode::GetIndex() { return m_index; } State* EDCNode::GetState() { return m_state; } int EDCNode::GetG() { return m_g; } int EDCNode::GetH() { return m_h; } int EDCNode::GetF() { return m_g + m_h; } int EDCNode::GetX() { return m_x; } int EDCNode::GetY() { return m_y; } int EDCNode::GetParent() { return m_parent; } bool EDCNode::MoveLeft(State* s) { if (s->blanky==0) return false; s->value[s->blankx][s->blanky] = s->value[s->blankx][s->blanky-1]; s->blanky--; s->value[s->blankx][s->blanky] = '0'; return true; } bool EDCNode::MoveRight(State* s) { if (s->blanky==2) return false; s->value[s->blankx][s->blanky] = s->value[s->blankx][s->blanky+1]; s->blanky++; s->value[s->blankx][s->blanky] = '0'; return true; } bool EDCNode::MoveUp(State* s) { if (s->blankx==0) return false; s->value[s->blankx][s->blanky] = s->value[s->blankx-1][s->blanky]; s->blankx--; s->value[s->blankx][s->blanky] = '0'; return true; } bool EDCNode::MoveDown(State* s) { if (s->blankx==2) return false; s->value[s->blankx][s->blanky] = s->value[s->blankx+1][s->blanky]; s->blankx++; s->value[s->blankx][s->blanky] = '0'; return true; } bool EDCNode::Compare(State* s1, State* s2) { for (int i=0; i<3; i++) for (int j=0; j<3; j++) { if (s1->value[i][j] != s2->value[i][j]) return false; } return true; } //------------------------------------------------------------------------- // EDC class //------------------------------------------------------------------------- int EDC::m_index = 0; EDC::EDC() { m_start = new EDCNode(); m_end = new EDCNode(); m_openNum = 0; m_closeNum = 0; m_gParas = 0; m_hParasDn = 1; m_hParasPn = 0; m_hParasSn = 0; } EDC::EDC(EDCNode* start, EDCNode* end, int g=0, int hd=1, int hp=0, int hs=0) { m_start = new EDCNode(*start); m_end = new EDCNode(*end); m_openNum = 0; m_closeNum = 0; m_gParas = g; m_hParasDn = hd; m_hParasPn = hp; m_hParasSn = hs; } EDC::~EDC() { if (m_start) delete m_start; if (m_end) delete m_end; m_start = NULL; m_end = NULL; m_openNum = 0; m_closeNum = 0; m_gParas = 0; m_hParasDn = 1; m_hParasPn = 0; m_hParasSn = 0; } EDCNode* EDC::GetStart() { return m_start; } EDCNode* EDC::GetEnd() { return m_end; } int EDC::GetOpenNum() { return m_openNum; } int EDC::GetCloseNum() { return m_closeNum; } EDCNode* EDC::GetNodeFromOpenList(int index) { if (index<1 || index>m_openNum) return NULL; return &m_openList[index]; } EDCNode* EDC::GetNodeFromCloseList(int index) { if (index<1 || index>m_closeNum) return NULL; return &m_closeList[index]; } void EDC::GetParas(int &gParas, int &hParasDn, int &hParasPn, int &hParasSn) { gParas = m_gParas; hParasDn = m_hParasDn; hParasPn = m_hParasPn; hParasSn = m_hParasSn; } void EDC::InsertToOpenList(EDCNode* node) { m_openList[++m_openNum] = *node; UpdateOpenList(m_openNum); } EDCNode* EDC::PopNodeFromOpenList() { if (m_openNum<1) return NULL; // 获取首元素 EDCNode* node = new EDCNode(m_openList[1]); // 调整堆 m_openList[1] = m_openList[m_openNum--]; int u,v=1; EDCNode temp; do { u = v; if (u*2+1<=m_openNum) { if (m_openList[u].GetF()>=m_openList[u*2].GetF()) v = u*2; if (m_openList[v].GetF()>=m_openList[u*2+1].GetF()) v = u*2+1; } else if (u*2<=m_openNum) { if (m_openList[u].GetF()>=m_openList[u*2].GetF()) v = u*2; } if (u==v) break; else { temp = m_openList[u]; m_openList[u] = m_openList[v]; m_openList[v] = temp; } }while (true); return node; } int EDC::IsInOpenList(EDCNode* node) { for (int i=0; i<m_openNum; i++) { if (EDCNode::Compare(node->GetState(), m_openList[i].GetState())) return i; } return -1; } void EDC::UpdateOpenList(int index) { if (index<1 || index>m_openNum) return; EDCNode temp; int i = index; while (i!=1) { if (m_openList[i].GetF() <= m_openList[i/2].GetF()) { temp = m_openList[i/2]; m_openList[i/2] = m_openList[i]; m_openList[i] = temp; i = i/2; } else break; } } void EDC::InsertToCloseList(EDCNode* node) { //m_closeList[++m_closeNum] = *node; int i; for (i=m_closeNum; i>0; i--) { if (m_closeList[i].GetG() > node->GetG()) { m_closeList[i+1] = m_closeList[i]; } else { break; } } m_closeList[i+1] = *node; m_closeNum++; } int EDC::IsInCloseList(EDCNode* node) { for (int i=0; i<m_closeNum; i++) { if (EDCNode::Compare(node->GetState(), m_closeList[i].GetState())) return i; } return -1; } int EDC::GetNodeParentFromCloseList(int index) { if (index>m_closeNum) return -1; for (int i=0; i<index; i++) { if (m_closeList[index].GetParent() == m_closeList[i].GetIndex()) return i; } return -1; } EDCNode* EDC::ExpandNode(EDCNode* node, int direct) { EDCNode* child = new EDCNode(*node); bool result = false; switch (direct) { case EDC_L: if (EDCNode::MoveLeft(child->GetState())) result = true; break; case EDC_R: if (EDCNode::MoveRight(child->GetState())) result = true; break; case EDC_U: if (EDCNode::MoveUp(child->GetState())) result = true; break; case EDC_D: if (EDCNode::MoveDown(child->GetState())) result = true; break; default: result = false; } if (result) { child->SetIndex(++EDC::m_index); return child; } delete child; return NULL; } void EDC::SetParas(int g, int hd, int hp, int hs) { m_gParas = g; m_hParasDn = hd; m_hParasPn = hp; m_hParasSn = hs; } int EDC::CalculateG(EDCNode* node1, EDCNode* node2) { int res; if (m_gParas==1) res = node1->GetG() + CalculateH(node1, node2); else if (m_gParas==0) res = node1->GetG() + 1; else res = 0; return res; } int EDC::CalculateH(EDCNode* node1, EDCNode* node2) { int res = 0; if (m_hParasDn != 0) res += m_hParasDn*DnMethod(node1, node2); if (m_hParasPn != 0) res += m_hParasPn*PnMethod(node1, node2); if (m_hParasSn != 0) res += m_hParasSn*SnMethod(node1, node2); return res; } int EDC::DnMethod(EDCNode *node1, EDCNode *node2) { State *s1 = node1->GetState(); State *s2 = node2->GetState(); int i,j, Dn=0; for (i=0; i<3; i++) { for (j=0; j<3; j++) { if (s1->value[i][j] != s2->value[i][j]) Dn++; } } return Dn; } int EDC::PnMethod(EDCNode *node1, EDCNode *node2) { State *s1 = node1->GetState(); State *s2 = node2->GetState(); int xcur[9], ycur[9], xdes[9], ydes[9]; int i,j, Pn=0; for (i=0; i<3; i++) { for (j=0; j<3; j++) { xcur[s1->value[i][j] - '0'] = i; ycur[s1->value[i][j] - '0'] = j; xdes[s2->value[i][j] - '0'] = i; ydes[s2->value[i][j] - '0'] = j; } } for (i=0; i<9; i++) { Pn += abs(xdes[i]-xcur[i]) + abs(ydes[i]-ycur[i]); } return Pn; } int EDC::SnMethod(EDCNode *node1, EDCNode *node2) { State *s1 = node1->GetState(); State *s2 = node2->GetState(); int i, k, Sn=0; int dirX[9]; int dirY[9]; if (s2->blankx==0) { if (s2->blanky==0) { dirX[0]=0;dirX[1]=0;dirX[2]=1;dirX[3]=2; dirX[4]=2;dirX[5]=2;dirX[6]=1;dirX[7]=1;dirX[8]=0; dirY[0]=1;dirY[1]=2;dirY[2]=2;dirY[3]=2; dirY[4]=1;dirY[5]=0;dirY[6]=0;dirY[7]=1;dirY[8]=1; } else if (s2->blanky==1) { dirX[0]=0;dirX[1]=1;dirX[2]=2;dirX[3]=2; dirX[4]=2;dirX[5]=1;dirX[6]=0;dirX[7]=1;dirX[8]=0; dirY[0]=2;dirY[1]=2;dirY[2]=2;dirY[3]=1; dirY[4]=0;dirY[5]=0;dirY[6]=0;dirY[7]=1;dirY[8]=2; } else // blanky=2 { dirX[0]=1;dirX[1]=2;dirX[2]=2;dirX[3]=2; dirX[4]=1;dirX[5]=0;dirX[6]=0;dirX[7]=1;dirX[8]=1; dirY[0]=2;dirY[1]=2;dirY[2]=1;dirY[3]=0; dirY[4]=0;dirY[5]=0;dirY[6]=1;dirY[7]=1;dirY[8]=2; } } else if (s2->blankx==1) { if (s2->blanky==0) { dirX[0]=0;dirX[1]=0;dirX[2]=0;dirX[3]=1; dirX[4]=2;dirX[5]=2;dirX[6]=2;dirX[7]=1;dirX[8]=0; dirY[0]=0;dirY[1]=1;dirY[2]=2;dirY[3]=2; dirY[4]=2;dirY[5]=1;dirY[6]=0;dirY[7]=1;dirY[8]=0; } else if (s2->blanky==1) { dirX[0]=0;dirX[1]=0;dirX[2]=0;dirX[3]=1; dirX[4]=2;dirX[5]=2;dirX[6]=2;dirX[7]=1;dirX[8]=0; dirY[0]=0;dirY[1]=1;dirY[2]=2;dirY[3]=2; dirY[4]=2;dirY[5]=1;dirY[6]=0;dirY[7]=0;dirY[8]=0; } else // blanky=2 { dirX[0]=2;dirX[1]=2;dirX[2]=2;dirX[3]=1; dirX[4]=0;dirX[5]=0;dirX[6]=0;dirX[7]=1;dirX[8]=2; dirY[0]=2;dirY[1]=1;dirY[2]=0;dirY[3]=0; dirY[4]=0;dirY[5]=1;dirY[6]=2;dirY[7]=1;dirY[8]=2; } } else // blankx=2 { if (s2->blanky==0) { dirX[0]=1;dirX[1]=0;dirX[2]=0;dirX[3]=0; dirX[4]=1;dirX[5]=2;dirX[6]=2;dirX[7]=1;dirX[8]=1; dirY[0]=0;dirY[1]=0;dirY[2]=1;dirY[3]=2; dirY[4]=2;dirY[5]=2;dirY[6]=1;dirY[7]=1;dirY[8]=0; } else if (s2->blanky==1) { dirX[0]=2;dirX[1]=1;dirX[2]=0;dirX[3]=0; dirX[4]=0;dirX[5]=1;dirX[6]=2;dirX[7]=1;dirX[8]=2; dirY[0]=0;dirY[1]=0;dirY[2]=0;dirY[3]=1; dirY[4]=2;dirY[5]=2;dirY[6]=2;dirY[7]=1;dirY[8]=0; } else // blanky=2 { dirX[0]=2;dirX[1]=2;dirX[2]=1;dirX[3]=0; dirX[4]=0;dirX[5]=0;dirX[6]=1;dirX[7]=1;dirX[8]=2; dirY[0]=1;dirY[1]=0;dirY[2]=0;dirY[3]=0; dirY[4]=1;dirY[5]=2;dirY[6]=2;dirY[7]=1;dirY[8]=1; } } for (k=0; k<8; k++) { for (i=0; i<8; i++) { if (s1->value[dirX[k]][dirY[k]] == s2->value[dirX[i]][dirY[i]]) { if (s1->value[dirX[k+1]][dirY[k+1]] != s2->value[dirX[i+1]][dirY[i+1]]) { Sn += 2; break; } break; } } } if (s1->blankx!=s2->blankx || s1->blanky!=s2->blanky) Sn += 1; return Sn; } int EDC::EDCOnce() { // 选取open表中未设置过的具有最小f值的节点bestnode EDCNode* bestnode = PopNodeFromOpenList(); if (!bestnode) return -1; // open表为空,返回-1,失败 // 放入close表 InsertToCloseList(bestnode); // 判断bestnode是否是目标节点,如果是返回1,成功 if (EDCNode::Compare(bestnode->GetState(), m_end->GetState())) return 1; // 扩展bestnode,从4个移动方向产生其后续节点successor int i=EDC_L; int old = -1; EDCNode* successor; while(i<=EDC_D) { successor = ExpandNode(bestnode, i); i++; if (!successor) continue; // 建立从successor返回bestnode的指针 successor->SetParent(bestnode->GetIndex()); /*// 计算个g(suc)=g(bes)+h(bes,suc) successor->SetG(CalculateG(bestnode, successor));*/ // 计算个g(suc)=g(bes)+1,深度加1 successor->SetG(CalculateG(bestnode, successor)); // suc是否在openlist中,如果在则返回位置 old = IsInOpenList(successor); if (old!=-1) { // 判断g(suc)<g(old) if (successor->GetG()<m_openList[old].GetG()) { // 重新确定old的父辈节点为bestnode,并修正父辈节点的g值 m_openList[old].SetParent(bestnode->GetIndex()); m_openList[old].SetG(successor->GetG()); } } else // 不在openlist中 { // 如果不在closelist表中 if (IsInCloseList(successor)==-1) { // 计算H值 successor->SetH(CalculateH(successor, m_end)); InsertToOpenList(successor); // 放入openlist中 } } delete successor; } delete bestnode; return 0; // 继续 } bool EDC::EDCAll() { InsertToOpenList(m_start); int result=0; while (result==0) { result = EDCOnce(); } if (result==-1) return false; return true; } void EDC::StartEDC() { m_openNum = 0; m_closeNum = 0; m_index = 0; InsertToOpenList(m_start); }
发表评论
-
源代码:基于A*算法的八数码问题的实现(用OpenGL实现动态演示)
2012-04-15 21:25 1542转载请注明出处:http://hi.baidu.com/ ... -
八数码问题使用HashTable优化查找后的版本
2012-04-07 11:17 1324在《双向广度优先搜索算法框架及八数码问题例程》一文中,给 ... -
双向广度优先搜索算法框架及八数码问题例程
2012-04-07 11:16 4570双向广度优先搜索算 ... -
用 A* 解决八数码问题
2012-04-07 11:13 1316Description The 15-puzzle has ... -
八数码问题(A*&&双向BFS)
2012-04-07 11:08 2590题目地址:http://acm.zju.edu. ... -
八数码问题源代码
2012-04-07 11:05 2183题目描述: 八方块移动游戏要求从一个含8个数字(用1- ...
相关推荐
本报告利用A*算法,给出了15数码问题的C++算法实现。 A*算法是一种预测算法,主要用于寻路等,根据当前状态和目标状态之间的差异,预测到达目标需要多少开销,根据这个开销来判断下一次选择以那个状态开始。这个开销...
A*算法解决八数码问题(C++),用数组实现的
人工智能作业,用python实现A*算法搜索解决八数码问题,测试通过
人工智能:A*算法实现八数码(C++),A*(A-Star)算法是一种静态路网中求解最短路最有A star算法在静态路网中的应用效的方法。
用a*算法实现八数码问题。随意输入一序列可以找到最佳路径编程1 2 3 8 4 7 6 5
A*算法实现8数码问题。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
A*算法解决传教士与野人过河问题 * 程 序 说 明 * * 功能: 用A*算法求解传教士与野人问题。M=C=5, K=3 * * 说明: * * 本程序按照《人工智能导论》一书所介绍的A*算法求解传教士与野人问题。 * * * * 注意:...
用C++实现的一个解决八数码问题的A*算法。仅供大家学习讨论。
主要实现了A*算法解决8数码问题,另有深度优先,广度优先及有序搜索的实现
用A*算法(人工智能或者数据结构与算法课程可能会学)解决八数码问题: 初始状态 目标状态 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 java实现方法在源码中。
A*算法解决八数码问题,包含了两种估价函数1.不在位的数字到该位置的曼哈顿距离;2.初始格局与目标格局位置不符的数码数目
自己写的用c++实现的简易八数码问题,搜索算法采用A*算法,搜索代价使用哈密顿路(可以自己更改,),资源是工程文件。在vs2008下运行通过,里面代码都进行了注释。
使用C++实现基于A*算法的N数码问题,是8数码问题的拓展。
一种基于环境栅格地图的机器人路径规划方法,包括建模与仿真。基于环境栅格地 图的路径规划及路径优化算法,首先建立已知环境的矩形化栅格地图用分区算法实现地图建模。机器人沿着路径即可实现对已知环境区域的全...
用JAVA写的A*算法实现八数码问题,能运行。
使用A*算法实现8数码问题的求解,以人格保证可以正确运行,并且运行时输出空格移动的步骤!文件使用VC++6.0打开,代码文件是1.cpp
C++实现的A*算法解八数码问题,报告的附录里有源代码,在VC6.0的环境下开发运行的
A*算法是路径规划的算法之一,也是最经典的算法。此代码为学习过程中用python编写,能够实现生成指定大小的地图,并随机生成地图上的障碍物,然后在地图上进行算法寻最优路径