当前课程知识点：智能控制 > 第二章 专家控制专题 > 2.1基于搜索的问题求解 > 2.1.7 均一代价搜索
我们比较一下
纵向搜索是按照一条线往下搜
每一条线都挖到底
看能不能找到我们的目标节点
这是它的搜索顺序
横向搜索
它一层层地往下走
这一层找不到
就搜下一层
直到找到我们的目标节点为止
那么这是它的区别
下面我们把之前的这种算法进行比较一下
算法1 随机搜索
它就是每次都是随机地选择节点进行搜索
它不能保证算法一定能够停止
因为它可能会陷入死循环
而且不一定能找到解
陷入死循环
它就不一定能找到解
算法2在一的基础上引入了CLOSED表
不走回头路
如果搜索图的节点数是有限的
那么它可以保证算法是能够停止下来
但是它不一定能保证找到可行解
因为它有可能陷入死角
无法退出
第3个算法就是在引入CLOSED表基础上
继续引入了OPEN表
也就是说既不走回头路
也要把所有未曾搜索过的节点都要搜一搜
这样的话呢
如果搜索图是有解的
它就可以保证算法一定能够停止
而且一定能够找到这个问题的解
这是对这三种算法的一个比较
下面我们介绍一下均一代价搜索
我们看这张搜索图
初始节点是F 目标节点是B
显然我们很容易发现这张图里面存在着
两条可能的求解路径
第一条就是FGECAB 那么它所对应的代价是多少呢
1+1+1+1再加二等于6
那么第二条路径就是FGEAB 它的对应代价是多少呢
就是一加一再加四再加二等于八
那么显然在这两条可行解的路径中
我们比较一下就会发现
第一条路径FGECAB显然它的代价要小
这是我们希望得到的更优的解
所以如果不存在比某个解的代价更小的解
那么这个解就称为最优解
在这个问题里
显然求解路径一是最优解
那么这样的话我们就提出了算法4 均一代价搜索
它的步骤是这样
第1步 将初始节点n及所对应的代价g(n)
放入OPEN表中
第2步将OPEN表中的最前面的节点提出来
并将其设为n´
如果节点n´就是目标节点
那么求解成功
否则的话
如果OPEN表为空
则求解失败
第3步
扩展节点n得到子节点的集合
并将n加入CLOSED表中
也就是当前节点n已经搜索过了
把它放入CLOSED表中
不再进行搜索
第4步
对于子节点集合中未包含在CLOSED表中的节点n
配置指向节点n的指针
并计算相应的代价
并将它放入OPEN表中
但是如果n已经进入OPEN表中了
那么当发现了比原来的代价更小的值的时候
我们就要对它进行更新
显然替换一个代价变小的路径
同时配置相应的指针
第5步 返回到第2步进行循环
那么这就是算法4
均一代价搜索
我们看看状态空间图
起始节点F目标节点B 那么对于F来说
它有一个子节点就是G
所以在F节点
我们OPEN表里面就是G
它代价多少呢
就是F到G的实际代价路径
路径代价多少呢 1
所以OPEN表是[G,1]
也就是它对应的子节点G
以及它所对应的代价F到G的代价1
CLOSED表里面显然就是F节点本身
那么下一步到了G节点
显然它有两个子节点E和H
到E的代价多少呢
F到G是1 G到E是1
加起来就是代价是2
所以1 2
那么H节点代价是F到G 1
G到H 2
所以加起来代价是3
所以在节点G OPEN表里面呢
[E,2],[H,3] 这是它对应的OPEN表
CLOSED表里面呢
在原来的F基础上再加上G
下一步显然要搜索这个代价
比较小的那一个
那就是E了
那么到了E节点
它要有两个子节点C和A
那么F经过G E到C的代价多少呢
1+1+1是3
那么F经过G E到A的代价多少呢
1+1
再加4是6
所以在节点1
它的OPEN表里面除了刚才的H3之外
还有C3 A6
那么由于H节点之前已经搜索过了
下一步先可以考虑先搜索H节点
那么在下一步第4步的时候
OPEN表里面只有
因为H节点没有子节点
所以OPEN表里只剩下C3 A6
下一步想要搜索C 第5步
那么C只有两个子节点A和D
那么F经过G E C到A
它代价多少呢
四个一
对应的就是四
F经过
G E C到D代价多少呢
三个1
再加个2是5
所以D的代价是5
A的代价是4
这样的话就会出现了
一个比原来的A的代价6更小的值
就是F经过G E C到A
替换了F G E到A
取得了更小的代价就是4
这样把A6给取代了
所以就剩下A4和D5
显然下一步要搜索A
A的子节点有且只有一个B
那么F经过G E C A到B代价多少呢
四个1加2显然代价是6
D呢 还是5
所以在节点A处
OPEN表里面就是D5 A6
下一步显然搜索D
由于节点D呢 并没有子节点
所以它的OPEN表里面只剩下了B6
那么最后一步呢 显然搜索B
到B这个节点位置
因为B已经是目标节点了
所以OPEN表里面是空的
也搜索完了
CLOSED表里面就把之前搜索都放在里头
这样就形成了均一代价搜索
我们发现从目标节点沿着蓝色的箭头回溯一下
其实就找到了这个问题的解
反过来就是FGECAB
我们发现它正好就是我们这个问题的最优解
最短路径
加起来最短路径刚好就是四个1加2 6
而不是另外一条可行路径
两个1加4再加2
那代价是8
这样的话就形成了均一代价搜索
-开篇
--开篇
-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 遗传编程的工作步骤及实例分析
-第八章测试
-期末测试
