文档介绍：Artificial Intelligence (AI)人工智能
主讲:戚玉涛
Email:qi_yutao@
第三章:确定性推理
内容提要
第三章:确定性推理

搜索策略
搜索策略
搜索的基本概念
状态空间的搜索策略
与/或树的搜索策略
搜索的完备性与效率
状态空间的搜索策略
状态空间的搜索策略
状态空间搜索的基本思想
图搜索的一般过程
状态空间的盲目搜索
广度优先搜索
深度优先搜索
代价树搜索
状态空间的启发式搜索
启发性信息和估价函数
A算法和A*算法
A算法
A算法:在图搜索算法中,如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对OPEN表中的节点进行排序,则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信息,因此,A算法也被称为启发式搜索算法。
A算法的类型:可根据搜索过程中选择扩展节点的范围,将启发式搜索算法分为
全局择优搜索算法: 从OPEN表的所有节点中选择一个估价函数值最小的一个进行扩展。
局部择优搜索算法:仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。
A算法
全局择优搜索算法流程
(1)把初始节点S0放入OPEN表,计算f(S0)。
(2)如果OPEN表为空,则问题无解,退出。
(3)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表。
(4)考察节点n是否为目标节点。若是,则求得了问题的解,退出。
(5)若节点n不可扩展,则转第2步。
(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并为每一个子节点都配置指向父节点的指针。把这些子节点都送入OPEN表中,然后对OPEN表中的全部节点按估价值从小至大的顺序进行排序,然后转第2步。
A算法
局部择优搜索算法流程
(1) 把初始节点S0放入OPEN表,计算f(S0)。
(2)如果OPEN表为空,则问题无解,退出。
(3)把OPEN表的第一个节点(记为节点n)取出放入CLOSED表。
(4)考察节点n是否为目标节点。若是,则求得了问题的解,退出。
(5)若节点n不可扩展,则转第2步。
(6) 扩展节点n,用估价函数f(x)计算每个子节点的估价值,并按估价值从小到大的顺序放到OPEN表中的首部,并为每一个子节点都配置指向父节点的指针,然后转第2步。
A*算法
A*算法:A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。
假设f*(n)是从初始节点出发经过节点n达到目标节点的最小代价,估价函数f(n)是对f*(n)的估计值。且
f*(n)=g*(n)+h*(n)
g*(n)是从初始节点S0到节点n的最小代价。
h*(n)是从节点n到目标节点的最小代价,若有多个目标节点,则为其中最小的一个。
A*算法
A*算法:A*算法对A算法(全局择优的启发式搜索算法)中的g(n)和h(n)分别提出如下限制:
第一,g(n)是对最小代价g*(n)的估计,且g(n)>0;
第二,h(n)是最小代价h*(n)的下界,即对任意节点n均有h(n)≤h*(n)。
即:满足上述两条限制的A算法称为A*算法。