人工智能论文[精品]

人工智能论文[精品] 淮北师范大学 计算机科学与技术学院 09级网络工程 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目: 人工智能中用*算法解决八数码问题 学 号: 21 姓 名: 1 专 业: 网络工程 课 程: 1 2012年6月12日 问题说明: 八数码问题是人工智能中一个很典型的智力问题。本文以状态空间搜索的观点讨论了八数码问题，给出了八数码问题的Jv算法与实现的思想， 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 了算法的可采纳性等及系统的特点。关键词九宫重排，状态空间，启发式搜索，算法1引言九宫重排问题是人工智能当中有名的难题之一。问题是在3×3方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则:空格四周的数移向空格，我们可以看作是空格移动，它最多可以有,个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。 一、 问题描述 1.1 待解决问题的解释 八数码游戏(八数码问题)描述为:在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是:给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态)，问如何移动将牌，实现从初始状态到目标状态的转变。 1.2 问题的搜索形式描述(4要素) 初始状态: 8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其 中，状态空间中的任一种状态都可以作为初始状态。 后继函数: 通过移动空格(上、下、左、右)和周围的任一棋子一次，到达新的合法状态。 目标测试: 比较当前状态和目标状态的格局是否一致。 路径消耗: 每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。 1.3 解决原理 对于八数码问题的解决，首先要考虑是否有 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 。每一个状态可认为是一个1×9的矩阵，问题即通过矩阵的变换，是否可以变换为目标状态对应的矩阵,由数学知识可知，可计算这两个有序数列的逆序值，如果两者都是偶数或奇数，则可通过变换到达，否则，这两个状态不可达。这样，就可以在具体解决问题之前判断出问题是否可解，从而可以避免不必要的搜索。 如果初始状态可以到达目标状态，那么采取什么样的方法呢, 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用*算法作为搜索策略。在这里就要用到启发式搜索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价 可以有不同的效果。 启发中的估价是用估价函数 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示的，如:(n) = g(n) + h(n) 其中(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。 在此八数码问题中，显然g(n)就是从初始状态变换到当前状态所移动的步数，估计函数(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数，即错位数。 二、 算法介绍 2.1 搜索算法一般介绍 不管哪种搜索，都统一用这样的形式表示:搜索的对象是一个图，它面向一个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解(可行解)，搜索的目的有两个方面，或者求可行解，或者从可行解集中求最优解。 搜索算法可分为两大类:无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索，其特点是只要问题状态可以形式化表示，原则上就可用使用无信息的搜索，无信息搜索有如下常见的几种搜索策略:广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。我们说DS和BS都是蛮力搜索，因为它们在搜索到一个结点时，在展开它的后续结点时，是对它们没有任何‘认识’的，它认为它的孩子们都是一样的‘优秀’，但事实并非如此，后续结点是有好有坏的。好，就是说它离目标结点‘近’，如果优先处理它，就会更快的找到目标结点，从而整体上提高搜索性能。 为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索(Ordered-Serch)，它着重看好能否找出解，而不看解离起始结点的距离(深度)。如果估值函数考虑了深度，或者是带权距离(从起始结点到目标结点的距离加权和)，那就是*如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用*。简单的来说*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性 启发价值，合在一起算估整个结点的价值， 考虑到八数码问题的特点，在本实验中使用*算法求解。*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价:(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Serch的*算法将是最优的。 2.2 算法伪代码 算法的功能:产生8数码问题的解(由初始状态到达目标状态的过程) 输入:初始状态，目标状态 输出:从初始状态到目标状态的一系列过程 算法描述: Begin: 读入初始状态和目标状态，并计算初始状态评价函数值; 根据初始状态和目标状态，判断问题是否可解; I(问题可解) 把初始状态假如open表中; While(未找到解&&状态表非空) ?在open表中找到评价值最小的节点，作为当前结点; ?判断当前结点状态和目标状态是否一致，若一致，跳出循环; 否则跳转到?; ?对当前结点，分别按照上、下、左、右方向移动空格位置来扩 展新的状态结点，并计算新扩展结点的评价值并记录其父节点; ?对于新扩展的状态结点，判断其是否重复，若不重复，把其加 入到open表中; ?把当前结点从open表中移除; End while End i 输出结果; End 算法流程如下: 开始 读入棋局初始状态 否 是否可解 o 是 o 初始状态加入open表 在open表中找到评价值最小的节点，作为当前结点 是 是目标节点 o 否 o 扩展新状态，把不重复的新状态加入open表中 当前结点从open表移除 输出结果 结束 问题规模:对于任一给定可解初始状态，状态空间有9!/2=181440个状态;当采 用不在位棋子数作为启发函数时，深度超过20时，算法求解速度缓慢; 3.2 数据结构 sttic int trget[9]={1,2,3,8,0,4,7,6,5}; 全局静态变量，表示目标状态 clss eight_num { privte: int num[9]; 定义八数码的初始状态 int not_in_position_num; 定义不在正确位置八数码的个数 int depth; 定义了搜索的深度 int ev_unction; 评价函数的值，每次选取最小的进行扩展 public: eight_num* prent; 指向节点的父节点 eight_num* le_next; 指向open表的下一个节点 eight_num* le_pre; 指向open 表的前一个节点 初始状态的构造函数 eight_num(int init_num[9]); eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9){} eight_num(void){ } 计算启发函数g(n)的值 void eight_num::cul_pr(void){} 显示当前节点的状态 void eight_num::show(){} 复制当前节点状态到一个另数组中 void eight_num::get_numbers_to(int other_num[9]){} 设置当前节点状态(欲设置的状态记录的other数组中) void eight_num::set_num(int other_num[9]){} eight_num& eight_num::opertor=(eight_num& nother_8num){} eight_num& eight_num::opertor=(int other_num[9]){} int eight_num::opertor==(eight_num& nother_8num){} int eight_num::opertor==(int other_num[9]){} 空格向上移 int move_up(int num[9]){} 空格向下移 int move_down(int num[9]){} 空格向左移 int move_let(int num[9]){} 空格向右移 int move_right(int num[9]){} 判断可否解出 int icnsolve(int num[9],int trget[9]){} 判断有无重复 int existed(int num[9],eight_num *where){} 寻找估价函数最小的叶子节点 eight_num* ind_OK_le(eight_num* strt){} } 3.3 实验结果 h: 启发函数(不在位将牌数) 初始状目标状是否有启发函数 用时 步数 态 态 解 3 2 1 1 2 3 否 h -- 8 0 4 8 0 4 7 6 5 7 6 5 1 0 4 1 2 3 是 h 2875ms 21 2 7 3 8 0 4 8 5 6 7 6 5 1 0 3 1 2 3 是 h 0ms 1 8 2 4 8 0 4 7 6 5 7 6 5 3.4 系统中间及最终输出结果(要求有屏幕显示) 目标状态默认为1 2 3 8 0 4 7 6 5 . a) 初始状态是3 2 1 8 0 4 7 6 5，用h作为启发函数结果都如下: b)初始状态是1 04 2 7 3 8 5 6，用h作为启发函数结果都如下: 中间略 b)初始状态是1 0 3 8 2 4 7 6 5，用h作为启发函数结果都如下: 源代码(用c++实现): #include "stdx.h" #include "iostrem.h" #include #include #include #include sttic int trget[9]={1,2,3,8,0,4,7,6,5}; //clss deinition clss eight_num { privte: int num[9]; int not_in_position_num; int depth; int ev_unction; public: eight_num* prent; eight_num* le_next; eight_num* le_pre; eight_num(int init_num[9]); eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9) { num[0]=num1; num[1]=num2; num[2]=num3; num[3]=num4; num[4]=num5; num[5]=num6; num[6]=num7; num[7]=num8; num[8]=num9; } eight_num(void) { or (int i=0;i<9;i++) num[i]=i; } void cul_pr(void); void get_numbers_to(int other_num[9]); int get_nipn(void) {return not_in_position_num;} int get_depth(void) {return depth;} int get_evun(void) {return ev_unction;} void set_num(int other_num[9]); void show(void); eight_num& opertor=(eight_num&); eight_num& opertor=(int other_num[9]); int opertor==(eight_num&); int opertor==(int other_num[9]); }; //计算启发函数g(n)的值 void eight_num::cul_pr(void) { int i; int temp_nipn=0; or (i=0;i<9;i++) i (num[i]!=trget[i]) temp_nipn++; not_in_position_num=temp_nipn; i (this->prent==NULL) depth=0; else depth=this->prent->depth+1; ev_unction=not_in_position_num+depth; } //构造函数1 eight_num::eight_num(int init_num[9]) { or (int i=0;i<9;i++) num[i]=init_num[i]; } //显示当前节点的状态 void eight_num::show() { cout<5) return 0; else { num[i]=num[i+3]; num[i+3]=0; return 1; } } //空格向左移 int move_let(int num[9]) { or (int i=0;i<9;i++) i (num[i]==0) brek; i (i==0||i==3||i==6) return 0; else { num[i]=num[i-1]; num[i-1]=0; return 1; } } //空格向右移 int move_right(int num[9]) { or (int i=0;i<9;i++) i (num[i]==0) brek; i (i==2||i==5||i==8) return 0; else { num[i]=num[i+1]; num[i+1]=0; return 1; } } //判断可否解出 int icnsolve(int num[9],int trget[9]) { int i,j; int count_num,count_trget; or (i=0;i<9;i++) or (j=0;jprent) i(*p==num) return 1; return 0; } //寻找估价函数最小的叶子节点 eight_num* ind_OK_le(eight_num* strt) { eight_num *p,*OK; p=OK=strt; int min=strt->get_evun(); or(p=strt;p!=NULL;p=p->le_next) i(min>p->get_evun()) { OK=p; min=p->get_evun(); } return OK; } //主函数开始 int min(void) { double time; clock_t Strt,inish; int memery_used=0,step=0; int num[9]; int lg=0;//是否输入错误标志，1表示输入错误 int bingo=0;//是否查找成功标志，1表示成功 int i,j; cout<<"Plese input the number(0 or the blnk):\n"; or (i=0;i<9;i++) { lg=0; cin>>num[i]; or(j=0;j8||lg==1) { i--; cout<<"Illegle number!\tReinput!\n"; } } eight_num S(num),Trget(trget); S.prent=S.le_next=S.le_pre=NULL; S.cul_pr(); memery_used++; cout<<"Now the initil numbers re:\n"; S.show(); cout<<"nd the Trget is:\n"; Trget.show(); i(!icnsolve(num,trget)) { cout<<"No one cn solve it!\n"; cin>>i; return 1; } Strt=clock( ); eight_num *OK_le=&S,*le_strt=&S,*new_8num,*p; while(OK_le!=NULL&&bingo!=1) { OK_le=ind_OK_le(le_strt); i(*OK_le==Trget) { bingo=1; brek; } p=OK_le->le_pre; OK_le->get_numbers_to(num); i(move_up(num)&&!existed(num,OK_le)) { new_8num=new eight_num; new_8num->set_num(num); new_8num->prent=OK_le; new_8num->cul_pr(); new_8num->le_pre=p; i(p==NULL) le_strt=new_8num; else p->le_next=new_8num; p=new_8num; memery_used++; } OK_le->get_numbers_to(num); i(move_down(num)&&!existed(num,OK_le)) { new_8num=new eight_num; new_8num->set_num(num); new_8num->prent=OK_le; new_8num->cul_pr(); new_8num->le_pre=p; i(p==NULL) le_strt=new_8num; else p->le_next=new_8num; p=new_8num; memery_used++; } OK_le->get_numbers_to(num); i(move_let(num)&&!existed(num,OK_le)) { new_8num=new eight_num; new_8num->set_num(num); new_8num->prent=OK_le; new_8num->cul_pr(); new_8num->le_pre=p; i(p==NULL) le_strt=new_8num; else p->le_next=new_8num; p=new_8num; memery_used++; } OK_le->get_numbers_to(num); i(move_right(num)&&!existed(num,OK_le)) { new_8num=new eight_num; new_8num->set_num(num); new_8num->prent=OK_le; new_8num->cul_pr(); new_8num->le_pre=p; i(p==NULL) le_strt=new_8num; else p->le_next=new_8num; p=new_8num; memery_used++; } p->le_next=OK_le->le_next; i(OK_le->le_next!=NULL) OK_le->le_next->le_pre=p; OK_le->le_next=OK_le->le_pre=NULL; } inish=clock( ); i(bingo==1) { time = (double)(inish-Strt)*1000/CLOCKS_PER_SEC; eight_num *p; or (p=OK_le->prent;p!=NULL;p=p->prent) { cout<<" ^\n"; p->show(); step++; } cout<<"Time cost:"; cout<