当前课程知识点:智能控制 > 第二章 专家控制专题 > 2.1基于搜索的问题求解 > 2.1.9 登山法和最佳优先搜索.
好
下面我们看一下登山法和最佳优先搜索算法
某一个盲人在山上某一点
他想要爬到山顶怎么办呢
他从站立的地方用拐杖往前一试
如果觉得前面高一些
就往前面走一步
如果前面不高就往后面走一步
后面如果高的话就往后面走一步
如果左边比较高的话就往左边走一步
否则的话就往右边走一步
如果四面都不高的话
那就站在原地不动
总之如果发现前后左右有高的地方
比当前位置要高的地方
就往前走一步
或者往那个方向走一步
那就这样一步一步地往前走
他一定可以走上山顶
因为山顶相对位置来说它是最高点
我们每一步都是朝着
能够提高它的高度的位置那个方向走
所以最终他一定能走到山顶上
那这个方法每一步测试的步
也就是登山法
估计函数
估计代价的函数
我们把它称为h(n)
下面我们看一下登山法的
也就是算法5的搜索过程
第1步 设初始节点为n
第2步 如果节点n为目标节点
那么求解成功
第3步
扩展当前节点n
得到子节点的集合
第4步
从子节点的集合中选起n′的代价为最小的节点
如果h(n)小于h(n′)
那么求解失败
第5步 设n′为新的n返回到第2步进行循环
这就是登山法
在这个算法里头
我们会把h(n)看作是到达山顶
也就是目标节点的距离
也可以采用类似于曼哈顿距离
这样的定义来描述
当前节点到达目标节点的距离有多远
这样的话我们每一步都可以朝着使得
代价函数也就是h(n)减小的方向
逐步进行搜索
所以看起来跟登山的情况是一样的
但是也有例外
比如当这样的节点不再存在的时候
我们就会以失败告终
也就是说如果在登山途中发现了小的山峰
也就是对于优化问题来说就是一个局部最优解
就可能会产生不能由这个地方 当前节点
继续完成原来的搜索过程的问题
比如在刚才节点之后
G之后
要选择H
那么此后就会发生无路可走的情况
因为H节点没有子节点
这种情况下和前面介绍的随机搜索中
产生的问题是相同的
所以我们就试图
能够同时引入OPEN表和CLOSED表
对比前面的算法中可以只根据代价函数h(n)的值
根据代价函数h(n)的值代替它
可以只根据估计函数g(n)的值
代替实际的函数h(n)的值
同时按照OPEN表来进行分类
这时候搜索过程如下图所示
那么在这个图里
我们每一步要考虑的代价
就是从当前节点到达目标节点的曼哈顿距离
我们这么定义的
那么起始节点还是F 目标节点是B
在起始节点F它有一个子节点G
那么G的代价多少
我们找它的曼哈顿距离
G到目标节点B的曼哈顿距离横坐标之差是2
纵坐标之差是3
所以它的代价是5
所以在F节点
它OPEN表里面就是G对应的代价是5
所以下一步想要搜索G
节点G有两个子节点
一个E 一个是H
对于E节点来说
它到目标节点B的曼哈顿距离多少
显然是2+2等于4
而H节点到目标节点B的曼哈顿距离是多少呢
显然就是3
所以在节点G位置
OPEN表里面就是H3和E4
代价要从小到大排列
而且这个代价指的是
这个节点到达目标节点的曼哈顿距离
也就是说在理论上它的最小距离
那么下一步显然H代价是3
它要小于E的节点
代价4
所以先搜索代价小的H
但是H节点是没有子节点的
所以到A节点的时候
只剩下节点E和对应的代价4了
那么到了E节点
它有两个子节点A和C
A到目标节点的曼哈顿距离多少
显然是2
C到目标节点的曼哈顿距离多少呢
是1+2等于3
所以在节点E
A的代价是2
C的代价是3
这是它们的OPEN表
那么显然下一步要搜索的是
代价小的A
我们发现A的子节点是B
那么B到目标节点B的曼哈顿距离多少呢 是0
所以在节点A处OPEN表里面有两个点
一个是B0
另外一个还有C3
那么下一步想要搜索的是目标节点B
因为它代价为0
其实我们到目标节点B的时候
我们发现已经找到目标节点了
我们再按照蓝色箭头回溯一下
就找到这个问题的一个解了
也就是F G E A B但是它实际代价是多少
1+1+4+2等于8
它并不是最优解
这也是它的一个缺陷
为什么呢
其实我们刚才在最佳优先搜索的过程中
每一步都是朝着使得
当前节点到目标节点的曼哈顿距离
最小的方向去努力搜索的
但这往往并不是最优选择
为什么呢
因为在最佳优先搜索算法中
我们并没有考虑从起始节点到当前节点代价
只是考虑了使得当前节点到目标节点
它们之间的代价的估计值也就是曼哈顿距离
也就是说使得将来的代价预测值
变成最小的路径方向搜索
这个算法可以保证能够找到可行解
它虽然可以在很多场合中高效地运行
但是不能保证一定能够获得最优解
最佳优先搜索算法是登山法的推广
但它是在OPEN表中所有的节点进行比较
比较它们的曼哈顿距离
也就是说代价估计函数
按从小到大的顺序重新排列OPEN表
那么这个曼哈顿距离小的优先搜索
曼哈顿距离大的后面搜索
这个算法效率大概相当于纵向搜索算法
但使用了与问题密切相关的代价函数
来确定下一步待扩展的节点
所以是一种启发式搜索算法
-开篇
--开篇
-1.1课程考试方式
-1.2 数据、信息、知识与智能
-1.3传统控制面临的挑战
-1.4 控制科学发展过程
-1.5 智能控制的多元论
--1.5
-1.6 控制策略的渗透与融合
--1.6
-1.7 智能控制与传统控制的联系与区别
--1.7
-1.8 智能控制的类型之分级递阶智能控制系统
--1.8
-1.9 智能控制的类型之专家控制系统
--1.9
-1.10 智能控制的类型之模糊控制系统
--1.10
-1.11 智能控制的类型之神经网络控制系统,智能控制的类型之基于规则的仿人智能控制系统,集成智能控制系统,组合智能控制
--1.11
-1.12智能控制系统的类型之基于规则的仿人智能控制系统,集成智能控制系统,组合智能控制
--1.12
-1.13本章小结
--1.13
-第一章测试
-2.1基于搜索的问题求解
-- 2.1.7 均一代价搜索
-- 2.1.10 A星算法
-2.2 专家系统简介
- 2.3 专家PID
-第二章测试
-3.1 模糊控制概述
-3.2 模糊集合
-3.3 隶属函数
--3.3隶属函数.
-3.4 模糊关系及其运算
-第三章测试
- 4.1 模糊自适应整定PID控制原理
-4.2 基于FF的模糊PID控制试验验证
-第四章测试
- 5.1 神经网络简介
- 5.2 神经网络的发展简史
-5.3 神经网络的基本概念
- 5.4 神经网络的分类
-5.5 神经网络的学习算法、基本特征和研究领域
-第五章测试
-6.1 感知器
--6.1.2.1 感知器应用实例分析(实现逻辑运算与或非)
- 6.2 BP神经网络
--6.2.2.1 BP神经网络应用实例分析之一:逻辑运算异或实现
--6.2.2.2 BP神经网络应用实例分析之二:非线性函数拟合
-第六章测试
- 7.1 什么是遗传算法
-7.2 遗传算法的特点
-7.3 遗传算法的基本操作之复制
-7.4 遗传算法的基本操作之交叉与变异
-第七章测试
-8.1 遗传编程工作原理
-8.2 遗传编程基本操作之复制
-8.3 遗传编程基本操作之交换和突变
- 8.4 遗传编程的工作步骤及实例分析
-第八章测试
-期末测试






