当前课程知识点:智能控制 > 第二章 专家控制专题 > 2.1基于搜索的问题求解 > 2.1.8 启发式搜索
下面我们看一下
应用智能的搜索方法
也就是说如何用人工智能的方法进行高效启发式搜索
比如在一个典型的八数码魔方和15数码魔方中
也就是九宫格和十六宫格中
这个方框图中到底存在着各种不同
多少种不同的状态呢
答案分别是九的阶乘和十六的阶乘
这就非常巨大
这就意味着搜索的空间非常巨大
很难求得它的解
怎么样解决这个问题呢
办法就是能不能够利用某些信息进行高效启发式搜索
也就是利用人工智能的方法进行高效启发式搜索
那么关键问题就是
我们要能够快速地找到问题的可行解
甚至最优解
其实就是要尽可能地减小它的搜索范围
使得搜索范围
在更小的范围之内进行快速地高效搜索
所以这种方法叫做启发式搜索
也就是要应用启发式
应用已有的知识的方法进行搜索
比如在这个迷宫问题中
如果知道目标状态的位置
那么就该考虑采取
尽可能靠近该位置的搜索策略
针对这个问题提出一个概念
叫做曼哈顿距离
那么也就是当设定目标节点的坐标为
(xg,yg)的时候
当前节点n 它的坐标为(x,y)
那么它到目标节点的曼哈顿距离怎么定义的呢
就定义为横坐标之差的绝对值
就是xg减x它的绝对值
加上纵坐标之差的绝对值
也就是yg减y的绝对值之和
就定义为曼哈顿距离
我们搜索的时候
我们始终朝着
能够使得曼哈顿距离变小的方向进行扩展
也就是意味着当曼哈顿距离为零的时候
我们发现发生了什么呢
其实就是已经找到了目标节点了
这是高效启发式搜索
但这种高效启发式搜索呢
虽然大多数情况下是有用的
但是不一定永远正确
比如所示的迷宫中
对节点G进行扩展的时候
它有两个子节点
一个是E 一个是H
按照曼哈顿的具体的定义
那么E节点的坐标是(1,1)
H呢 是(3,0)
那么目标节点B的位置是多少呢
是(3,3)
这样的话按照曼哈顿距离的定义
节点E到目标节点B的曼哈顿距离
就是2+2等于4
而结点H到目标节点B的曼哈顿距离是多少呢
就是3+0等于3
实际上这时候就发生问题了
虽然可以说H离目标节点相对E的目标节点
曼哈顿距离要近
但它并不是正确的选择
为什么
因为它虽然曼哈顿距离比较小
但是它并没有可以扩展的子节点
理论上是可行的
但实际上是过不去的
它就是有这样的一个问题
-开篇
--开篇
-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 遗传编程的工作步骤及实例分析
-第八章测试
-期末测试