人工智能读书报告.doc

(读书报告、研究报告)
考
核
科
目:人工智能
学生所在院(系):计算机学院
学生所在学科:计学生姓名: 学号: 学生类别:学考
核结果
算机术科学与技术阅卷人
人工智能读书报告
——基于动态加权的a*搜索算法研究
启发式搜索
启发式搜索就是在状态空间中对每一个搜索的位置进行评估,选择最好的位置,再从这个位置进行搜索直到目标。在启发式搜索中,对位置的估价是十分重要的。采用了不同的评估方法可以有不同的效果。最佳优先搜索的最广为人知的形式称为a*(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价:d(n)=g(n)+h(n),因为以g(n)给出了从起始节点到节点n的路径耗散,而h(n)是从节点n到目标节点的最低耗散路径的估计耗散值,因此d(n)=,如果我们想要找到最低耗散解,首先尝试找到g(n)+h(n)值最小的节点是合理的。由a*定义可以发现这个策略不只是合理的:倘若启发函数h(n)满足一定的条件,搜索既是完备的也是最优的。如果把a*搜索用于tree-search,它的最优性是能够直接分析的。在这种情况下,如果h(n)是一个可采纳启发式--也就是说,倘若h(n)从不会过高估计到达目标的耗散--a*算法是最优的。可采纳启发式天生是最优的,因为他们认为求解问题的耗散是低于实际耗散的。因为g(n)是到达节点n的确切耗散,我们得到一个直接的结论:d(n)永远不会高估经过节点n的解的实际耗散。常用的启发算法有:蚁群算法,遗传算法、模拟退火算法等。
greedy search on d outperforms search on h
动态加权启发式搜索算法
应用启发式搜索中的加权技术, 其主要目的是调整搜索中深度优先与宽度优先的比值, 以提高搜索效率。通常有两种加权技术, 即常数加权与动态加权技术。由于在常数加权中, 同样的加权量毫无区别地施用在每一个节点上, 加权的作用取决于各单一节点。而在动态加权中, 则会动态地对不同层上的节点施以不同的加权量。故一般地, 采用动态加权技术的启发式搜索效率要比静态( 即常数) 加权好。
定义一. 一个搜索算法是ε可采纳的, 如果该算法总能找到一条求解路径, 其耗散值至少为??ft*(s)。这里ft*(s)表示从初始节点s出发至目标节点的最佳路径的耗散值,ε∈(0,1) 。根据加权技术的基本思想, 启发式评价函数的动态加权应达到这样的效果: 在搜索树的浅层, 搜索应呈现深度优先搜索的特性; 而随着搜索树的层次越来越深, 应逐步呈现出宽度优先搜索的特性
。据此, 我们可以定义动态加权的启发式评价函数为:ft(n)?t(gt(n),??(1?d(n)/n)?ht(n)) 其中d(n) 表示节点n在搜索树中的深度, n 表示预期的目标节点在搜索树中的深度;
定义二. 若算法ra?采用上述的启发式评价函数ft, 且ht≥ht*,则称算法raε为算法ra?*。
若模t满足t(??a,??b)???t(a,b),这里ε∈(0,1),属于最佳路径上的且在open表中属于最浅层的任意节点n,仍然有gt(n)=gt*(n) ,最后经过推导可以得到:ft(n)?t(gt(n),??(1?d(n)/n)?ht(n))
=t(gt*(n),??(1?d(n)/n)?ht(n)) ≥t(gt*(n),??(1?d(n)/n)?ht*(n)) ≥t(gt*(n),??ht*(n)) ≥t(??gt*(n),??ht*(n)) ≥??ft*(s)
动态加权不能克服指数爆炸问题
martelli已经证明了,在最坏情况下,算法a*的时间复杂度为o(2n) 这里m是图的节点数。使用动态加权技术的本质在于提高搜索效率,但是动态加权技术很难消除指数爆炸现象。
定义三. 启发式评价函数ht’被称为引导了一个?(n)的标准化误差,若对于b元树上的所有节点,存在两个固定的正数β和γ和一个正交函数?(.),
ht(n)?ht*(n)ht(n)?ht*(n)
|??]??/b , γ>1和p[||??]??/b ?<1 使得p[|
?(ht*(n))?(ht*(n))
(n) 引出?(n)=n的标准化误差,则当0<?0 <1 <a≤1
1??
d(n)
时,启发式评价函数为aht(n)???(1?)?ht(n) 引出同样的?(n)?n 的
n
标准化误差。这里??(0,1] ,?0得含义如同极限、概率定义中常见的,它与
?不同。
ht(n)?ht*(n)ht(n)?ht*(n)
证明过程:令y(n)? ;y(n)? 因为**
?(ht(n))?(ht(n))11