*文件Chess.h,包含必要的数据结构,全局变量和类声明
*/
#ifndef _YLQ_CHESS_
#define _YLQ_CHESS_
#include
#include
#include
#ifndef N
#define N 3
#endif
#define BLANK 0
static int g_iId=1;
typedef struct tagNode{
int node[N][N];
int iF,iH,iG;
int id,idParent;
}NODE,*PNODE;
typedef std::vector
#define CLOSED OPEN
#define SUCCERSSOR OPEN
class Chess
{
public:
Chess(NODE const &nstar,NODE const &nend); private:
OPEN m_vOpen,m_vClosed;
NODE m_nStart,m_nEnd;
bool NodeEuqal(NODE node1,NODE node2);
bool NodeExist(NODE node);
bool InOpen(NODE node,int &index);
bool InClose(NODE node,int &index);
SUCCERSSOR ExplortNode(NODE node); protected:
virtual int CaculateHV(NODE &node);//计算h值和f值public:
bool Algorithms();
void Show(int it);//it=1展示Open,2->Closed
};
#endif
*文件Chess.cpp,包含算法实现
*/
#include "Chess.h"
#include
bool comp(const NODE &n1,const NODE &n2)
{
return n1.iF>n2.iF;
}
void Chess::Show(int tp)
{
SUCCERSSOR::iterator it,iend;
if (tp==1) {
it=m_vOpen.begin();
iend=m_vOpen.end();
}
else{
it=m_vClosed.begin();
iend=m_vClosed.end();
}
for (;it!=iend;it++)
{
printf("iF=%d;iG=%d;iH=%d\n",(PNODE)it->iF,(PNODE)it->iG,(PNODE)it->iH);
printf("id=%d;idParent=%d\n",(PNODE)it->id,(PNODE)it->idParent);
for(int i=0;i for (int j=0;j printf("%d ",(PNODE)it->node[i][j]); } std::cout< } } } Chess::Chess(const NODE &nstar,const NODE &nend) { m_nStart = nstar; m_nEnd = nend; m_nStart.idParent=0;//初始结点的父节点设为0 m_nStart.id = 1; m_nStart.iG=0;//初始结点G设为0,再次结点扩展一次就+1( 表示深度); CaculateHV(m_nStart);//初始化开始结点h和f以及g m_vOpen.push_back(m_nStart); } int Chess::CaculateHV(NODE &node) {//用位置差来计算h值 node.iH=0; for (int i=0;i for (int j=0;j bool bget=false; for (int m=0;m for (int n=0;n if (node.node[m][n] == m_nEnd.node[i][j]) { node.iH+=abs(m-i)+abs(n-j); bget=true; break; } } if (bget) break; } } } node.iF =node.iG+node.iH; return node.iH; } bool Chess::NodeEuqal(NODE node1,NODE node2) { int sum=0; for (int i=0;i for (int j=0;j if (node1.node[i][j] == node2.node[i][j]) { sum++; } } if (sum==N*N) { return true; } else return false; } bool Chess::InOpen(NODE node,int &index) {//查找node是否在Open表中,是的返回true并返回指针位置index OPEN::iterator itOpen=m_vOpen.begin(); index=0; for (;itOpen!=m_vOpen.end();itOpen++){ if (NodeEuqal(node,*(PNODE)itOpen->node)) { return true; } index++; } return false; } bool Chess::InClose(NODE node,int &index) {//查找node是否在InClose表中,是的返回true并返回指针位置index CLOSED::iterator itClosed=m_vClosed.begin(); index=0; for (;itClosed!=m_vClosed.end();itClosed++){ if (NodeEuqal(node,*(PNODE)itClosed->node)) { return true; } index++; } return false; } bool Chess::NodeExist(NODE node) { int i; if (InOpen(node,i) || InClose(node,i)) { return true; } return false; } SUCCERSSOR Chess::ExplortNode(NODE node) {//扩展结点,并插入到SUCCERSSOR队列中 int i,j; SUCCERSSOR temp; for (i=0;i for (j=0;j if (node.node[i][j]==BLANK) {//找到空格,开始扩张,按照空格依次往上下左右扩展,判断其合法性if (j>0) { NODE ntemp=node; ntemp.node[i][j]=ntemp.node[i][j-1]; ntemp.node[i][j-1]=BLANK; g_iId++; ntemp.id=g_iId; ntemp.idParent = node.id; ntemp.iG=ntemp.iG+1; CaculateHV(ntemp); temp.push_back(ntemp); } if (j NODE ntemp=node; ntemp.node[i][j]=ntemp.node[i][j+1]; ntemp.node[i][j+1]=BLANK; g_iId++; ntemp.id=g_iId; ntemp.idParent = node.id; ntemp.iG=ntemp.iG+1; CaculateHV(ntemp); temp.push_back(ntemp); } if (i>0) { NODE ntemp=node; ntemp.node[i][j]=ntemp.node[i-1][j]; ntemp.node[i-1][j]=BLANK; g_iId++; ntemp.id=g_iId; ntemp.idParent = node.id; ntemp.iG=ntemp.iG+1; CaculateHV(ntemp); temp.push_back(ntemp); } if (i NODE ntemp=node; ntemp.node[i][j]=ntemp.node[i+1][j]; ntemp.node[i+1][j]=BLANK; g_iId++; ntemp.id=g_iId; ntemp.idParent = node.id; ntemp.iG=ntemp.iG+1; CaculateHV(ntemp); temp.push_back(ntemp); } } return temp; } bool Chess::Algorithms() { NODE nTemp; while (m_vOpen.size()!=0) { std::sort(m_vOpen.begin(),m_vOpen.end(),comp); //取出f值最小的进行扩展 nTemp = *((PNODE)(m_vOpen.end()-1)); m_vOpen.pop_back(); m_vClosed.push_back(nTemp); if (NodeEuqal(nTemp,m_nEnd)) return true; SUCCERSSOR stemp=ExplortNode(nTemp); SUCCERSSOR::iterator isuc=stemp.begin(); for (;isuc!=stemp.end();isuc++){ int indexOp,indexCl=0; NODE suc=*(PNODE)isuc,*old; if (InOpen(suc,indexOp)) { old = (PNODE)(m_vOpen.begin()+indexOp); if (suc.iG {//若G值比原先的小,则直接修改old结点 old->iG = suc.iG; //修改其父节点,指向suc结点 old->idParent = suc.idParent; old->iF = old->iG+old->iH; } } else if (InClose(suc,indexCl)) { old = (PNODE)(m_vClosed.begin()+indexCl); if (suc.iG {//若G值比原先的小,则直接修改old结点 old->iG = suc.iG; //修改其父节点,指向suc结点 old->idParent = suc.idParent; old->iF = old->iG+old->iH; } } else { m_vOpen.push_back(suc); } } } return false; } /* *文件main.cpp,如何使用该类 */ #include "Chess.h" #include using namespace std; NODE nStart={{2,8,3, 0,1,4, 7,6,5},0,0,0, g_iId,0}; NODE nEnd={{1,2,3, 8,0,4, 7,6,5},0,0,0, 0,0}; int main(int argc,char *argv) { Chess *chess=new Chess(nStart,nEnd); if (chess->Algorithms()){ cout<<"搜索成功:\n"; chess->Show(2); } return 0; } 用A*算法解决八数码问题 一、 题目:八数码问题也称为九宫问题。在3×3的棋盘,有八个棋子,每个 棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有 一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给 出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动 棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态:状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态:任何状态都可以被指定为初始状态。 操作符:用来产生4个行动(上下左右移动)。 目标测试:用来检测状态是否能匹配上图的目标布局。 路径费用函数:每一步的费用为1,因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态,要求找到一种搜索策略,用尽可能少的步数 得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。对于 几何路网来说,可以取两节点间欧几理德距离(直线距离)做为估价值,即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--; 这样估价函数f 在g 值一定的情况下,会或多或少的受估价值h 的制约,节点距目标点近,h 值小,f 值相对就小,能保证最短路的搜索向终点的 方向进行。明显优于盲目搜索策略。 A star算法在静态路网中的应用 2.算法伪代码 创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。算起点的估价值,将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 ) {把n设置为X的父亲; 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值} } if(X not inboth) {把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; //还没有排序} 实验报告 一、实验问题 八数码问题求解 二、实验软件 VC6.0 编程语言或其它编程语言 三、实验目的 1. 熟悉人工智能系统中的问题求解过程; 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用; 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 四、实验数据及步骤 (一、)实验内容 八数码问题:在3×3的方格棋盘上,摆放着1到8这八个数码,有1个方格是空的,其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 (a) 初始状态(b) 目标状态 图1 八数码问题示意图 (二、)基本数据结构分析和实现 1.结点状态 我采用了struct Node数据类型 typedef struct _Node{ int digit[ROW][COL]; int dist; // distance between one state and the destination一 个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; 2.发生器函数 定义的发生器函数由以下的四种操作组成: (1)将当前状态的空格上移 Node node_up; Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE; (2)将当前状态的空格下移 Node node_down; Assign(node_down, index);//向下扩展的节点 int dist_down = MAXDISTANCE; (3)将当前状态的空格左移 Node node_left; Assign(node_left, index);//向左扩展的节点 int dist_left = MAXDISTANCE; (4)将当前状态的空格右移 Node node_right; Assign(node_right, index);//向右扩展的节点 int dist_right = MAXDISTANCE; 通过定义结点状态和发生器函数,就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。 3.图的搜索策略 经过分析,8数码问题中可采用的搜速策略共有:1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索,一共五种。其中,广度优先搜索法是可采纳的,有界深度优先搜索法是不完备的,最好优先和局部择优搜索法是启发式搜索法。 实验时,采用了广度(宽度)优先搜索来实现。 (三、)广度(宽度)优先搜索原理 1. 状态空间盲目搜索——宽度优先搜索 其基本思想是,从初始节点开始,向下逐层对节点进形依次扩展,并考察它是否为目标节点,再对下层节点进行扩展(或搜索)之前,必须完成对当层的所有节点的扩展。再搜索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面,后进入的节点排在后面。其搜索过程如图(1)所示。 用A算法解决八数码 问题 用A*算法解决八数码问题 一、 题目:八数码问题也称为九宫问题。在3×3的棋盘,有八个棋子,每个 棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态:状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态:任何状态都可以被指定为初始状态。 操作符:用来产生4个行动(上下左右移动)。 目标测试:用来检测状态是否能匹配上图的目标布局。 路径费用函数:每一步的费用为1,因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态,要求找到一种搜索策略,用尽可能少的步数得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*(A-Star)算法是一种静态路网中求解最短路最有效的方法。对 于几何路网来说,可以取两节点间欧几理德距离(直线距离)做为估价 值,即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--; 这样估价函数f 在g 值一定的情况下,会或多或少的受估价值h 的制 约,节点距目标点近,h 值小,f 值相对就小,能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。 A star算法在静态路网中的应用 2.算法伪代码 创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。算起点的估价值,将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 ) 1、实验目的 (1)熟悉人工智能系统中的问题求解过程; (2)熟悉状态空间中的盲目搜索策略; (3)掌握盲目搜索算法,重点是宽度优先搜索和深度优先搜索算法。 2、实验要求 用VC语言编程,采用宽度优先搜索和深度优先搜索方法,求解8数码问题 3、实验内容 (1)采用宽度优先算法,运行程序,要求输入初始状态 假设给定如下初始状态S0 2 8 3 1 6 4 7 0 5 和目标状态Sg 2 1 6 4 0 8 7 5 3 验证程序的输出结果,写出心得体会。 (2)对代码进行修改(选作),实现深度优先搜索求解该问题 提示:每次选扩展节点时,从数组的最后一个生成的节点开始找,找一个没有被扩展的节点。这样也需要对节点添加一个是否被扩展过的标志。 4 源代码及实验结果截图 #include //八数码状态对应的节点结构体 struct Node{ int s[3][3];//保存八数码状态,0代表空格 int f,g;//启发函数中的f和g值 struct Node * next; struct Node *previous;//保存其父节点 }; int open_N=0; //记录Open列表中节点数目 //八数码初始状态 int inital_s[3][3]={ 2,8,3,1,6,4,7,0,5 }; //八数码目标状态 int final_s[3][3]={ 2,1,6,4,0,8,7,5,3 }; //------------------------------------------------------------------------ //添加节点函数入口,方法:通过插入排序向指定表添加 //------------------------------------------------------------------------ void Add_Node( struct Node *head, struct Node *p) { struct Node *q; . 用盲目搜索技术解决八数码问题 题目 在3×3的棋盘,有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上 标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 算法流程 使用宽度优先搜索 从初始节点开始,向下逐层对节点进形依次扩展,并考察它是否为目标节点,再对下层节点进行扩展(或搜索)之前,必须完成对当层的所有节点的扩展。再搜 索过程中,未扩展节点表OPEN中的节点排序准则是:先进入的节点排在前面, 后进入的节点排在后面。 宽度优先算法如下: 把初始结点S0放入OPEN表中 若OPEN表为空,则搜索失败,问题无解 取OPEN表中最前面的结点N放在CLOSE表中,并冠以顺序编号n 若目标结点,则搜索成功,问题有解N?Sg若N无子结点,则转2 扩展结点N,将其所有子结点配上指向N的放回指针,依次放入OPEN表的尾部,转2 源程序 #include using namespace std; const int ROW = 3;//行数 const int COL = 3;//列数 const int MAXDISTANCE = 10000;//最多可以有的表的数目const int MAXNUM = 10000; typedef struct _Node{ int digit[ROW][COL]; int dist;//distance between one state and the destination 一个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置} Node; Node src, dest;// 父节表目的表 vector 1、程序源代码 #include 一、实验目的 1、熟悉和掌握启发式搜索的定义、估价函数和算法过程。 2、利用A*算法求解N数码难题,理解求解流程和搜索顺序。 二、实验内容 以八数码为例实现A或A*算法。 1、分析算法中的OPEN表CLOSE表的生成过程。 1)建立一个队列,计算初始结点的估价函数f,并将初始结点入队,设置队列头和尾指针。 2)取出队列头(队列头指针所指)的结点,如果该结点是目标结点,则输出路径,程序结束。否则对结点进行扩展。 3)检查扩展出的新结点是否与队列中的结点重复,若与不能再扩展的结点重复(位于队列头指针之前),则将它抛弃;若新结点与待扩展的结点重复(位于队列头指针之后),则比较两个结点的估价函数中g的大小,保留较小g值的结点。跳至第五步。 4)如果扩展出的新结点与队列中的结点不重复,则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置,使它们按从小到大的顺序排列,最后更新队列尾指针。 5)如果队列头的结点还可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步。 2、分析估价函数对搜索算法的影响。 3、分析启发式搜索算法的特点。 广度优先搜索和双向广度优先搜索都属于盲目搜索,这在状态空间不大的情况下是很合适的算法,可是当状态空间十分庞大时,它们的效率实在太低,往往都是在搜索了大量无关的状态结点后才碰到解答,甚至更本不能碰到解答。 搜索是一种试探性的查寻过程,为了减少搜索的盲目性引,增加试探的准确性,就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估,从中选择最好、可能容易到达目标的位置,再从这个位置向前进行搜索,这样就可以在搜索中省略大量无关的结点,提高了效率。 启发式函数选取为:f*(n)=g*(n)+ h*(n) 其中: g*(n)是搜索树中节点n的深度 h*(n)用来计算对应于节点n的数据中错放的棋子个数。 三、实验结果 实验三:A*算法求解8数码问题实验 一、实验目的 熟悉和掌握启发式搜索的定义、估价函数和算法过程,并利用A*算法求解N数码难题,理解求解流程和搜索顺序。 二、实验内容 1、八数码问题描述 所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8,其中一个单元格是空的。将任意摆放的数码盘(城初始状态)逐步摆成某个指定的数码盘的排列(目标状态), 如图1所示 图1 八数码问题的某个初始状态和目标状态 对于以上问题,我们可以把数码的移动等效城空格的移动。如图1的 初始排列,数码7右移等于空格左移。那么对于每一个排列,可能的一次数码移动最多只有4中,即空格左移、空格右移、空格上移、空格下移。最少有两种(当空格位于方阵的4个角时)。所以,问题1 就转换成如何从初始状态开始,使空格经过最小的移动次数最后排列成目标状态。 2、八数码问题的求解算法 2.1 盲目搜索 宽度优先搜索算法、深度优先搜索算法 2.2 启发式搜索 启发式搜索算法的基本思想是:定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。 先定义下面几个函数的含义: f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;h*(n)表示从当前节点n到目标节点g的最短路径的耗散值,f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。 评价函数的形式可定义如(2)式所示: f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 人工智能实验一报告题目:采用A*算法解决八数码问题 姓名: XXX 学号: 10S003028 专业:计算机科学与技术 提交日期: 2011-05-04 目录 1问题描述........................................................................................................................... - 2 - 1.1待解决问题的解释............................................................................................... - 2 - 1.2问题的搜索形式描述............................................................................................ - 2 - 1.3解决方案介绍(原理)........................................................................................ - 3 - 2算法介绍........................................................................................................................... - 4 - 2.1A*搜索算法一般介绍............................................................................................ - 4 - 2.2 算法伪代码........................................................................................................... - 4 - 3算法实现........................................................................................................................... - 5 - 3.1 实验环境与问题规模........................................................................................... - 5 - 3.2 数据结构............................................................................................................... - 5 - 3.3 实验结果............................................................................................................... - 6 - 3.4系统中间及最终输出结果.................................................................................... - 6 - 4参考文献........................................................................................................................... - 7 - 5附录—源代码及其注释................................................................................................... - 7 - A*算法求解八数码问题 1、八数码问题描述 所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、 6、7、8,其中一个单元格是空的。将任意摆放的数码盘(城初始状态)逐步摆成某个 指定的数码盘的排列(目标状态),如图1所示 图1 八数码问题的某个初始状态和目标状态 对于以上问题,我们可以把数码的移动等效城空格的移动。如图1的初始排列,数码7右移等于空格左移。那么对于每一个排列,可能的一次数码移动最多只有4中,即空格左移、空格右移、空格上移、空格下移。最少有两种(当空格位于方阵的4个角时)。所以,问题就转换成如何从初始状态开始,使空格经过最小的移动次数最后排列成目标状态。 2、八数码问题的求解算法 2.1 盲目搜索 宽度优先搜索算法、深度优先搜索算法 2.2 启发式搜索 启发式搜索算法的基本思想是:定义一个评价函数f,对当前的搜索状态进行评估,找出一个最有希望的节点来扩展。 先定义下面几个函数的含义: f*(n)=g*(n)+h*(n) (1) 式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;h*(n)表示从当前节点n到目标节点g的最短路径的耗散值,f*(n)表示从初始节点s经过n到目标节点g 的最短路径的耗散值。 评价函数的形式可定义如(2)式所示: f(n)=g(n)+h(n) (2) 其中n是被评价的当前节点。f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。 利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。在A算法中,如果对所有的x, h(x)<=h*(x) (3) 成立,则称好h(x)为h*(x)的下界,它表示某种偏于保守的估计。采用h*(x)的下界h(x)为启发函数的A算法,称为A*算法。 针对八数码问题启发函数设计如下: f(n)=d(n)+p(n) (4) 其中A*算法中的g(n)根据具体情况设计为d(n),意为n节点的深度,而h(n)设计为 启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。 要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ,A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? , 其中:()d n 是搜索树中结点n 的深度;()w n 为结点n 的数据库中错放的棋子个数;()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度,深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中,并计算节点S 的)(S f ; ② 如果OPEN 是空表,则失败退出,无解; ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同,当其中有一个 为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点i ; ④ 把节点i 从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中; ⑤ 如果i 是个目标节点,则成功退出,求得一个解; ⑥ 扩展节点i ,生成其全部后继节点。对于i 的每一个后继节点j : 计算)(j f ;如果j 既不在OPEN 表中,又不在CLOCED 表中,则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针,以便一旦找到目标节点时记住一个解答路径;如果j 已在OPEN 表或CLOSED 表中,则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小,则 (I)以此新值取代旧值。 (II)从j 指向i ,而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中,则把它移回OPEN 表中。 ⑦ 转向②,即GOTO ②。 #include 人工智能实验报告 学院:信息科学与工程学院 班级:自动化0901班 学号: 06 姓名:孙锦岗 指导老师:刘丽珏 日期:2011年12月20日 一、实验名称、目的及内容 实验名称: 八数码难题的搜索求解演示 实验目的: 加深对图搜索策略概念的理解,掌握搜索算法。 实验内容要求: 以八数码难题为例演示广度优先或深度优先搜索、A算法(本实验使用的是广度优先搜索)的搜索过程,争取做到直观、清晰地演示算法。 八数码难题:在3 X 3方格棋盘上,分别放置了标有数字 123,4,5,6,7,8 的八张牌,初始状态SO,目标状态如图所示,可以 使用的操作有:空格上移,空格左移,空格右移,空格下移。试编一程序实现这一搜索过程。 二、实验原理及基本技术路线图 实验原理: 八数码问题中,程序产生的随机排列转换成目标共有两种可能,而且这两种不可能同时成立,也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个数组表示,例如{8, 7,1,5,2,6,3,4,0}其中0代表空格。它在奇序列位置上。 在这个数组中我们首先计算它能够重排列出来的结果,公式就是: E(F(X))=Y,其中F (X),就是一个数他前面比这个数小的数的个数,Y为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。 数据结构: 本实验使用的数据结构是队列,应用队列先进先出的特点来实现对节点的保存和扩展。首先建立一个队列,将初始结点入队,并设置队列头和尾指,然后取出队列(头指针所指)的结点进行扩展,从它扩展出子结点,并将这些结点按扩展的顺序加入队列,然后判断扩展出的新结点与队列中的结点是否重复,如果重复则,否则记录其父结点,并将它加入队列,更新队列尾指针,然后判断扩展出的结点是否是目标结点,如果是则显示路径,程序结束。否则如果队列头的结点可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步,知道扩展出的结点是目标结点结束,并显示路径。 算法分析: 九宫问题的求解方法就是交换空格(0)位置,直至到达目标位置为止。如图所示: 《八数码问题》实验报告 一、实验目的: 熟练掌握启发式搜索A *算法。 二、实验内容: 使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题A *算法,采用估价函数 ()()()()w n f n d n p n ??=+??? , 其中:()d n 是搜索树中结点n 的深度;()w n 为结点n 的数据库中错放的棋子个数;()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 三、实验原理: 1. 问题描述: 八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格(以数字0来表示),与空格相邻的棋子可以移到空格中。 要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 原理描述: 启发式搜索 (1)原理 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 (2)估价函数 计算一个节点的估价函数,可以分成两个部分: 1、 已经付出的代价(起始节点到当前节点); 2、 将要付出的代价(当前节点到目标节点)。 节点n 的估价函数)(n f 定义为从初始节点、经过n 、到达目标节点的路径的最小代价 的估计值,即)(* n f = )(* n g + )(* n h 。 )(*n g 是从初始节点到达当前节点n 的实际代价; )(*n h 是从节点n 到目标节点的最佳路径的估计代价。 )(*n g 所占的比重越大,越趋向于宽度优先或等代价搜索;反之,)(*n h 的比重越大, 表示启发性能就越强。 (3)算法描述: ① 把起始节点S 放到OPEN 表中,并计算节点S 的)(S f ; ② 如果OPEN 是空表,则失败退出,无解; ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同,当其中有一个 为目标节点时,则选择此目标节点;否则就选择其中任一个节点作为节点i ; ④ 把节点i 从 OPEN 表中移出,并把它放入 CLOSED 的已扩展节点表中; ⑤ 如果i 是个目标节点,则成功退出,求得一个解; ⑥ 扩展节点i ,生成其全部后继节点。对于i 的每一个后继节点j : 计算)(j f ;如果j 既不在OPEN 表中,又不在CLOCED 表中,则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针,以便一旦找到目标节点时记住一个解答路径;如果j 已在OPEN 表或CLOSED 表中,则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小,则 (I)以此新值取代旧值。 (II)从j 指向i ,而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中,则把它移回OPEN 表中。 ⑦ 转向②,即GOTO ②。 (3)算法流程图: 人工智能实验报告 学院:信息科学与工程学院 班级:自动化0901班 学号: 姓名:孙锦岗 指导老师:刘丽珏 日期:2011年12月20日 一、实验名称、目的及内容 实验名称: 八数码难题的搜索求解演示 实验目的: 加深对图搜索策略概念的理解,掌握搜索算法。 实验内容要求: 以八数码难题为例演示广度优先或深度优先搜索、A算法(本实验使用的是广度优先搜索)的搜索过程,争取做到直观、清晰地演示算法。 八数码难题:在3×3方格棋盘上,分别放置了标有数字1,2,3,4,5,6,7,8的八张牌,初始状态S0,目标状态如图所示,可以使用的操作有:空格上移,空格左移,空格右移,空格下移。试编一程序实现这一搜索过程。 二、实验原理及基本技术路线图 实验原理: 八数码问题中,程序产生的随机排列转换成目标共有两种可能,而且这两种不可能同时成立,也就是奇数排列和偶数排列。我们可以把一个随机排列的数组从左到右从上到下用一个数组表示,例如{8, 7,1,5,2,6,3,4,0}其中0代表空格。它在奇序列位置上。 在这个数组中我们首先计算它能够重排列出来的结果,公式就是:∑(F(X))=Y,其中F(X),就是一个数他前面比这个数小的数的个数,Y为奇数和偶数个有一种解法。那么上面的数组我们就可以解出它的结果。 数据结构: 本实验使用的数据结构是队列,应用队列先进先出的特点来实现对节点的保存和扩展。首先建立一个队列,将初始结点入队,并设置队列头和尾指,然后取出队列(头指针所指)的结点进行扩展,从它扩展出子结点,并将这些结点按扩展的顺序加入队列,然后判断扩展出的新结点与队列中的结点是否重复,如果重复则,否则记录其父结点,并将它加入队列,更新队列尾指针,然后判断扩展出的结点是否是目标结点,如果是则显示路径,程序结束。否则如果队列头的结点可以扩展,直接返回第二步。否则将队列头指针指向下一结点,再返回第二步,知道扩展出的结点是目标结点结束,并显示路径。 算法分析: 九宫问题的求解方法就是交换空格(0)位置,直至到达目标位置为止。如图所示: 八数码问题A*算法的实现及性能分析 计算机科学与技术学院 专业:计算机科学与技术 161210404 杨凯迪 目录 一、8数码问题 (3) 1.问题描述 (3) 2.八数码问题形式化描述 (3) 3.解决方案 (4) 二、A*算法 (4) 1.A*搜索算法一般介绍 (4) 2. A*算法的伪代码 (5) 3. 建立合适的启发式 (6) 三、算法实现及性能比较 (7) 四、算法性能分析 (8) 五、结论 (9) 六、参考文献 (10) 附录 (10) 一、8数码问题 1.问题描述 八数码问题是指这样一种游戏:将分别标有数字1,2,3,…,8 的八块正方形数码牌任意地放在一块3×3 的数码盘上。放牌时要求不能重叠。于是,在3×3 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,不断移动该空格方块以使其和相邻的方块互换,直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动,在四个角落上有2个方向可移动,在其他位置上有3个方向可移动,问题描述如图1-1所示 初始状态过渡状态最终状态 图1-1 八数码问题执行过程 2.八数码问题形式化描述 初始状态: 初始状态向量:规定向量中各分量对应的位置,各位置上的数字。把3×3的棋盘按从左到右,从上到下的顺序写成一个一维向量。我们可以设定初始状态:<1,5,2,4,0,3,6,7,8> 后继函数: 按照某种规则移动数字得到的新向量。例如: <1,5,2,4,0,3,6,7,8> <1,0,2,4,5,3,6,7,8> 目标测试: 新向量是都是目标状态。即<1,2,3,4,5,6,7,8,0>是目标状态? 路径耗散函数: 每次移动代价为1,每执行一条规则后总代价加1。 1、程序源代码 #include <> #include<> struct node{ int a[3][3];//用二维数组存放8数码 int hx;//函数h(x)的值,表示与目标状态的差距struct node *parent;//指向父结点的指针 struct node *next;//指向链表中下一个结点的指针 }; //------------------hx函数-------------------// int hx(int s[3][3]) {//函数说明:计算s与目标状态的差距值 int i,j; int hx=0; int sg[3][3]={1,2,3,8,0,4,7,6,5}; for(i=0;i<3;i++) for(j=0;j<3;j++) if(s[i][j]!=sg[i][j]) hx++; return hx; } //-------------hx函数end----------------------// //-------------extend扩展函数----------------// struct node *extend(node *ex) { //函数说明:扩展ex指向的结点,并将扩展所得结点组成一条//单链表,head指向该链表首结点,并且作为返回值 int i,j,m,n; //循环变量 int t; //临时替换变量 int flag=0; int x[3][3];//临时存放二维数组 struct node *p,*q,*head; head=(node *)malloc(sizeof(node));//head p=head; q=head; head->next=NULL;//初始化 for(i=0;i<3;i++)//找到二维数组中0的位置 { for(j=0;j<3;j++) 八数码问题算法 文献综述报告 摘要:随着计算机和网络的大范围普及,电脑游戏也普遍存在于人们的生活中,但是大部分的人都只是看重游戏的娱乐价值(启发思维,培养观察能力、耐心等),而不在乎其本质,比如说它有着什么样的数据结构,它的核心算法是什么等等这些问题。本文就目前一个很经典的算法问题——八数码问题来分析其核心的算法,并且借助前人得出的研究,进一步分析和设计算法。 关键词:八数码;拼图游戏;广度优先搜索;深度优先搜索;A*搜索 1引言 从古至今,“游戏”这个词对于人们来说都不陌生,从古代的斗禽,蹴鞠等到现在的一系列的电脑游戏。尤其是如今的电脑游戏,不胜其数,种类繁多,不亦乐乎,拼图游戏就是其中的一种。所谓的拼图游戏就是把一副完整的图片通过规则的或者不规则的切割后打乱成零片,玩家只需把零片拼凑回原形即可。在这个过程中,要发生无数次的状态改变,在电脑上也如此。不同的是,电脑上的拼图游戏需要一个“看不见”的存储空间来存储这一个个不同的状态。这就必须涉及到数据的存贮方式。尤其是算法,它是拼图游戏的核心,它决定了计算机怎样解决这个问题,同时还影响着这个游戏程序的存储方式。但是,并不是一个能玩的游戏都具有理想的算法和数据结构。因此,对一个游戏的算法进行分析优化并设计出一个理想的算法显得更加重要。此拼图游戏是建立在一个3*3 的方格棋盘上,把棋盘上的打散的八块图片分别用数字1-8标识,棋盘上空的那块标识为0,那么拼图游戏就可以转化成我们算法中极为极为经典的八数码问题。 2 八数码问题的研究现状 2.1 八数码问题的概念 八数码问题也称为九宫问题。在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要求解决的问题是:给出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后,状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2.2 八数码问题的状态空间法表示 2.2.1状态描述 八数码问题的一个状态就是八个数字在棋盘上的一种放法。每个棋子用它上面所标的数字表示,并用0表示空格,这样就可以将棋盘上棋子的一个状态存储在一个一维数组p[9]中,存储的顺序是从左上角开始,自左至右,从上到下。把 用A*算法解决八数码问题 一、 题目:八数码问题也称为九宫问题。在3×3的棋盘,有八个棋子,每个棋子 上标有1至8的某一数字,不同棋子上标的数字不相同。棋盘上还有一个空格,与空格相邻的棋子可以移到空格中。要解决的问题就是:任意给出一个初始状态与一个目标状态,找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态:状态描述了8个棋子与空位在棋盘的9个方格上的分布。 初始状态:任何状态都可以被指定为初始状态。 操作符:用来产生4个行动(上下左右移动)。 目标测试:用来检测状态就是否能匹配上图的目标布局。 路径费用函数:每一步的费用为1,因此整个路径的费用就是路径中的步数。 现在任意给定一个初始状态,要求找到一种搜索策略,用尽可能少的步数得到上图的目标状态算法介绍 三、 解决方案介绍 1、A*算法的一般介绍 A*(A-Star)算法就是一种静态路网中求解最短路最有效的方法。对于几何路网来说,可以取两节点间欧几理德距离(直线距离)做为估价值,即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--; 这样估价函数f 在g 值一定的情况下,会或多或少的受估价值h 的制约,节点距目标点近,h 值小,f 值相对就小,能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。 A star算法在静态路网中的应用 2、算法伪代码 创建两个表,OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。算起点的估价值,将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 ) {把n设置为X的父亲; 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值} } if(X not inboth) {把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; //还没有排序}用A算法解决八数码问题
八数码问题求解--实验报告讲解
用A算法解决八数码问题演示教学
C语言实现8数码问题
用盲目搜索技术解决八数码问题
启发式搜索算法解决八数码问题(C语言)
八数码难题 Matlab
实验三A星算法求解8数码问题实验讲解
采用A算法解决八数码问题
A星算法求解八数码问题
启发式搜索 八数码问题
八数码C语言A算法详细代码
八数码难题的搜索求解演示
八数码问题实验报告讲解
八数码难题的搜索求解演示
八数码问题A算法的实现及性能分析
启发式搜索算法解决八数码问题
八数码问题算法文献综述
用A算法解决八数码问题