当前课程知识点:智能控制 >  第二章 专家控制专题 >  2.1基于搜索的问题求解 >  2.1.9 登山法和最佳优先搜索.

返回《智能控制》慕课在线视频课程列表

2.1.9 登山法和最佳优先搜索.在线视频

下一节: 2.1.10 A星算法

返回《智能控制》慕课在线视频列表

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.1课程考试方式

-1.2 数据、信息、知识与智能

--1.2 数据、信息、知识与智能

-1.3传统控制面临的挑战

--1.3 传统控制面临的挑战.

-1.4 控制科学发展过程

--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.1 搜索与人工智能的关系

--2.1.2 算法1 随机搜索

--2.1.3 算法2 引入CLOSED表.

--2.1.4 算法3 引入OPEN表.

--2.1.5 纵向搜索算法(深度优先搜索)

--2.1.6 横向搜索算法(广度优先搜索)

-- 2.1.7 均一代价搜索

--2.1.8 启发式搜索

--2.1.9 登山法和最佳优先搜索.

-- 2.1.10 A星算法

-- 2.1.11 八数码魔方实例分析

-2.2 专家系统简介

--2.2.1 专家系统简介(上)

--2.2.2 专家系统简介(下)

- 2.3 专家PID

--2.3.1 专家PID (上)

--2.3.2 专家PID (下)

-第二章测试

第三章 模糊控制的理论基础

-3.1 模糊控制概述

--3.1.1 模糊控制概述

-3.2 模糊集合

--3.2.1 模糊集合(上)

--3.2.2 模糊集合(中)

--3.2.3 模糊集合(下)

-3.3 隶属函数

--3.3隶属函数.

-3.4 模糊关系及其运算

--3.4模糊关系及其运算

-第三章测试

第四章 模糊控制

- 4.1 模糊自适应整定PID控制原理

--4.1.1 模糊自适应整定PID控制原理(上)

--4.1.2 模糊自适应整定PID控制原理(下)

-4.2 基于FF的模糊PID控制试验验证

-- 4.2.1 基于FF的模糊PID控制试验验证(上)

-- 4.2.2 基于FF的模糊PID控制试验验证(下)

-第四章测试

第五章 神经网络的理论基础

- 5.1 神经网络简介

--5.1 神经网络简介

- 5.2 神经网络的发展简史

--5.2 神经网络的发展简史

-5.3 神经网络的基本概念

--5.3 神经网络的基本概念

- 5.4 神经网络的分类

--5.4 神经网络的分类

-5.5 神经网络的学习算法、基本特征和研究领域

--5.5 神经网络的学习算法、基本特征和研究领域

-第五章测试

第六章 典型神经网络

-6.1 感知器

--6.1.1 感知器的数学模型.

--6.1.2.1 感知器应用实例分析(实现逻辑运算与或非)

--6.1.2.2 感知器应用实例分析(实现逻辑运算异或)

- 6.2 BP神经网络

--6.2.1.1 BP神经网络简介(上)

--6.2.1.2 BP神经网络简介(中)

--6.2.1.3 BP神经网络简介(下)

--6.2.2.1 BP神经网络应用实例分析之一:逻辑运算异或实现

--6.2.2.2 BP神经网络应用实例分析之二:非线性函数拟合

-第六章测试

第七章 遗传算法及其应用

- 7.1 什么是遗传算法

--7.1 什么是遗传算法

-7.2 遗传算法的特点

--7.2 遗传算法的特点

-7.3 遗传算法的基本操作之复制

--7.3 遗传算法的基本操作之复制

-7.4 遗传算法的基本操作之交叉与变异

--7.4 遗传算法的基本操作之交叉与变异

-第七章测试

第八章 遗传编程

-8.1 遗传编程工作原理

--8.1 遗传编程工作原理

-8.2 遗传编程基本操作之复制

--8.2 遗传编程基本操作之复制

-8.3 遗传编程基本操作之交换和突变

--8.3 遗传编程基本操作之交换和突变

- 8.4 遗传编程的工作步骤及实例分析

-- 8.4 遗传编程的工作步骤及实例分析

-第八章测试

期末测试

-期末测试

2.1.9 登山法和最佳优先搜索.笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。