人工智能：第1章 搜索问题.ppt

该【人工智能：第1章 搜索问题 】是由【窝窝爱蛋蛋】上传分享，文档一共【120】页，该文档可以免费在线阅读，需要了解更多关于【人工智能：第1章 搜索问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第1章、搜索问题
有许多智力问题(如梵塔问题、八数码问题、八皇后问题、农夫过河问题等)
许多实际问题(如装箱问题、机器人行动规划、最优路径规划、人力排班等)
都可以归结为在某一状态空间中搜索目标或路径的问题。
*
梵塔问题:
在印度北部的佛教圣地,安放着一块黄铜板,板上插著三根细细的、镶上宝石的细针。当印度教的主神梵天在创造地球这个世界时,就在其中的一根针上从下到上放了半径由大到小的六十四片圆金片环,这就是有名的「梵塔」。
天神梵天要这庙的僧侣,把这些金片全部由一根针移到另外一根指定的针上,一次只能移一片,不管在什么情况下,金片环的大小次序不能变更,小金片环永远只能放在大金片环上面。
只要有一天这六十四片的金环能从指定的针上完全转移到另外指定的针上,世界末日就来到,芸芸众生、神庙一切都将消灭,万物尽入极乐世界去。
n阶梵塔移动次数:设金片数为n,则移动次数=2的n次方-1
以一秒钟移动一次计算,这需要夜以继日地搬动5800亿年!
*
*
装箱与布局问题
您是否遇到装箱繁难的问题呢?您想降低运输成本、提高企业的竞争力吗?
*
人力排班
高速公路收费员优化配置
问题:如何解决这类问题?
这类问题不能用简单的数学公式/数学方程来描述,属于非结构化问题。
难以获得求解所需的全部信息;更没有现成的算法可供求解使用
属于组合爆炸问题,稍大规模的问题就超出了人类的认知负荷
解决方法:利用计算机的超人计算能力,通过不断试探搜索找到问题的(最优)解。优点建模简单
*
具体方法:状态空间法
状态:是指问题状态的的向量表示(x,y,z,….)。
问题有初始状态,有目标状态
有些状态可能是非法的,问题不可能发展到那种状态
问题表示为向量,向量就是在Euclidean空间,因此问题的初始状态和目标状态都是此空间中的点。
此类问题的特征是找出从初始状态到目标状态的路径,方法是通过一个状态向另一个状态的转换实现的。
*
问题状态的表示方法(一)
*
问题状态的表示方法(二)
*
问题状态的变迁