人工智能论文讲解.docx
- 文档编号:15385659
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:10
- 大小:94.14KB
人工智能论文讲解.docx
《人工智能论文讲解.docx》由会员分享,可在线阅读,更多相关《人工智能论文讲解.docx(10页珍藏版)》请在冰点文库上搜索。
人工智能论文讲解
滨江学院
课程论文
课程名称:
人工智能
院系滨江学院
专业自动化
学号***********
姓名周程
指导老师孙玉宝
二O一六年六月二十日
摘要
人工智能是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。
人工智能的研究方向、研究领域、应用领域值得我们关注和探讨。
本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Java算法与实现的思想,分析了A*算法的可采纳性等及系统的特点。
关键词:
九宫重排,状态空间,启发式搜索,A*算法
引言
九宫重排问题是人工智能当中有名的难题之一。
问题是在3×3方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。
问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。
状态转换的规则:
空格四周的数移向空格,我们可以看作是空格移动,它最多可以有4个方向的移动,即上、下、左、右。
九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。
一、问题描述
1.1待解决问题的解释
八数码游戏(八数码问题)描述为:
在3×3组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1-8八个数码中的某一个数码。
棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。
这种游戏求解的问题是:
给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。
1.2问题的搜索形式描述(4要素)
初始状态:
8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。
其中,状态空间中的任一种状态都可以作为初始状态。
后继函数:
通过移动空格(上、下、左、右)和周围的任一棋子一次,到达新的合法状态。
目标测试:
比较当前状态和目标状态的格局是否一致。
路径消耗:
每一步的耗散值为1,因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。
1.3解决原理
对于八数码问题的解决,首先要考虑是否有答案。
每一个状态可认为是一个1×9的矩阵,问题即通过矩阵的变换,是否可以变换为目标状态对应的矩阵?
由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通过变换到达,否则,这两个状态不可达。
这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。
常用的状态空间搜索有深度优先和广度优先。
广度优先是从初始状态一层一层向下找,直到找到目标为止。
深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止。
广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。
这在状态空间不大的情况下是很合适的算法。
于八数码问题状态空间共有9!
个状态,对于八数码问题如果选定了初始状态和目标状态,有9!
/2个状态要搜索,考虑到时间和空间的限制,在这里采用A算法作为搜索策略。
在这里就要用到启发式搜索
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。
这样可以省略大量无畏的搜索路径,提到了效率。
在启发式搜索中,对位置的估价是十分重要的。
采用了不同的估价可以有不同的效果。
二、算法介绍
2.1搜索算法一般介绍
不管哪种搜索,都统一用这样的形式表示:
搜索的对象是一个图,它面向一个问题,不一定有明确的存储形式,但它里面的一个结点都有可能是一个解,搜索的目的有两个方面,或者求可行解,或者从可行解集中求最优解。
搜索算法可分为两大类:
无信息的搜索算法和有信息的搜索算法。
无信息的搜索又称盲目搜索,其特点是只要问题状态可以形式化表示,原则上就可用使用无信息的搜索,无信息搜索有如下常见的几种搜索策略:
广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。
为了改善上面的算法,我们需要对展开后续结点时对子结点有所了解,这里需要一个估值函数,估值函数就是评价函数,它用来评价子结点的好坏,因为准确评价是不可能的,所以称为估值。
这就是我们所谓的有信息搜索。
如果估值函数只考虑结点的某种性能上的价值,而不考虑深度,比较有名的就是有序搜索,它着重看好能否找出解,而不看解离起始结点的距离(深度)。
如果估值函数考虑了深度,或者是带权距离(从起始结点到目标结点的距离加权和),那就是A*如果不考虑深度,就是说不要求最少步数,移动一步就相当于向后多展开一层结点,深度多算一层,如果要求最少步数,那就需要用A*。
简单的来说A*就是将估值函数分成两个部分,一个部分是路径价值,另一个部分是一般性启发价值,合在一起算估整个结点的价值,
考虑到八数码问题的特点,在本实验中使用A*算法求解。
A*搜索是一种效的搜索算法,它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价:
f(n)=g(n)+h(n)。
当h(n)是可采纳时,使用Tree-Search的A*算法将是最优的。
2.2算法伪代码
算法的功能:
产生8数码问题的解(由初始状态到达目标状态的过程)
输入:
初始状态,目标状态
输出:
从初始状态到目标状态的一系列过程
算法描述:
Begin:
读入初始状态和目标状态,并计算初始状态评价函数值f;
根据初始状态和目标状态,判断问题是否可解;
If(问题可解)
把初始状态假如open表中;
While(未找到解&&状态表非空)
①在open表中找到评价值最小的节点,作为当前结点;
②判断当前结点状态和目标状态是否一致,若一致,跳出循环;否则跳转到③;
③对当前结点,分别按照上、下、左、右方向移动空格位置来扩展新的状态结点,并计算新扩展结点的评价值f并记录其父节点;
④对于新扩展的状态结点,判断其是否重复,若不重复,把其加入到open表中;
⑤把当前结点从open表中移除;
Endwhile
Endif
输出结果;
End
算法流程如下:
问题规模:
对于任一给定可解初始状态,状态空间有9!
/2=181440个状态;当采用不在位棋子数作为启发函数时,深度超过20时,算法求解速度缓慢;
三、数据介绍
3.1数据结构
staticinttarget[9]={1,2,3,8,0,4,7,6,5};全局静态变量,表示目标状态
classeight_num
{
private:
intnum[9];定义八数码的初始状态
intnot_in_position_num;定义不在正确位置八数码的个数
intdeapth;定义了搜索的深度
inteva_function;评价函数的值,每次选取最小的进行扩展
public:
eight_num*parent;指向节点的父节点
eight_num*leaf_next;指向open表的下一个节点
eight_num*leaf_pre;指向open表的前一个节点
初始状态的构造函数
eight_num(intinit_num[9]);
eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9){}
eight_num(void){}
计算启发函数g(n)的值
voideight_num:
:
cul_para(void){}
显示当前节点的状态
voideight_num:
:
show(){}
复制当前节点状态到一个另数组中
voideight_num:
:
get_numbers_to(intother_num[9]){}
设置当前节点状态(欲设置的状态记录的other数组中)
voideight_num:
:
set_num(intother_num[9]){}
eight_num&eight_num:
:
operator=(eight_num&another_8num){}
eight_num&eight_num:
:
operator=(intother_num[9]){}
inteight_num:
:
operator==(eight_num&another_8num){}
inteight_num:
:
operator==(intother_num[9]){}
空格向上移
intmove_up(intnum[9]){}
空格向下移
intmove_down(intnum[9]){}
空格向左移
intmove_left(intnum[9]){}
空格向右移
intmove_right(intnum[9]){}
判断可否解出
inticansolve(intnum[9],inttarget[9]){}
判断有无重复
intexisted(intnum[9],eight_num*where){}
寻找估价函数最小的叶子节点
eight_num*find_OK_leaf(eight_num*start){}
}
3.2实验结果
h:
启发函数(不在位将牌数)
初始状态
目标状态
是否有解
启发函数
用时
步数
321
804
765
123
804
765
否
h
--
104
273
856
123
804
765
是
h
2875ms
21
103
824
765
123
804
765
是
h
0ms
1
3.3系统中间及最终输出结果(要求有屏幕显示)
目标状态默认为123804765.
a)初始状态是321804765,用h作为启发函数结果都如下:
b)初始状态是104273856,用h作为启发函数结果都如下:
b)初始状态是103824765,用h作为启发函数结果都如下:
参考文献
[1]合成生物学与人工生命体作者:
叶邦策 王建军来源:
科学杂志;
[2]量子神经网络及其应用 南京邮电学院信号与信息处理研究所 李飞;郑宝玉;赵生妹;
[3]人工神经网络在组织网络化发展评价中的应用朱启红张钢《计算机应用研究》2007年第06期;
[4]神经网络研究的发展趋势廖晓峰李传东[5]中科院半导体研究所半导体人工神经网络实验室;
[5]专家系统的现状及发展趋势方景文;机器人,Robot,编辑部邮箱1986年06期;
[6]主体与协同:
专家系统的发展方向中科院计算所张子云曹鹏(计算机世界报2007年102日第41期B11)专家系统的原理、现状和发展趋势杨叔子;郑小军;水利电力机械。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 论文 讲解