《人工智能 一种现代方法》第三版 第3章 通过搜索进行问题求解 笔记摘录

本文主要是介绍《人工智能 一种现代方法》第三版 第3章 通过搜索进行问题求解 笔记摘录,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第三章 通过搜索进行问题求解

本章讨论的问题具有如下性质:环境是可观察的、确定的、已知的,问题解是一个动作序列

  • 问题求解Agent
    1. 使用原子表示的基于目标的Agent,被称之为问题求解Agent
    2. 使用要素法或结构化表示的基于目标的Agent,称之为规划Agent
    3. 基于当前的情形和Agent的性能度量进行目标的形式化是问题求解的第一个步骤
    4. 为达到目标,寻找行动序列的过程称之为搜索。搜索算法输入是问题,输出是问题的解,以行动序列的形式返回问题的解。
    5. 解一旦找到,他所建议的行动将会付诸实施,这被称为执行阶段
    6. 因此对Agent的简单设计,即“形式化、搜索、执行。
    7. 需要注意的是,Agent在执行解的序列时,无视它的感知信息,它明确行为的后果是什么。控制理论把这成为开环系统
    8. 良定义的问题及解
      1. 一个问题可以用5个组成部分形式化地描述,其中初始状态、行动、转移模型定义了问题的状态空间即从初始状态可以到达的所有状态的集合,状态空间形成一个有向网络或图:
        1. Agent的初始状态 ,例如:In(Arad)
        2. 描述Agent的可能的行动。例如:ACTIONS(s),返回在状态s下可移植性的动作集合:{Go(sibiu),Go(Timisoara)}
        3. 对每个行动的描述,也叫转移模型,例如:RESULT(s,a),在状态s下执行行动a后达到的状态:RESULT(In(Arad),Go(sibiu))=In(sibiu)
        4. 目标测试:确定给定的状态是不是目标状态
        5. 路径消耗函数为每条路径赋予一个耗散值,即边加权。问题求解Agent选择能反应它的性能度量的耗散函数。
  • 问题实例
    1. 玩具问题(举例)

      1. 增量形式化(举例)

      1. 完全形式化
    1. 现实世界问题(举例)

  • 通过搜索求解:再对问题形式化后,我们还需对问题求解
    1. 一个解是一个行动序列,搜索算法的工作就是考虑各种可能的行为序列。
    2. 从搜索树中根节点的初始状态出发,连线表示行动,结点是对应问题的状态空间中得状态。
    3. 再通过扩展当前的状态完成:从当前状态下应用各种合法行为,由此生成了一个新的状态集。
    4. 以上就是搜索,选择一条路走下去,把其他的选择放在一边,等以后发现第一个选择不能求出问题的解时再考虑。
    5. 所有待扩展的叶结点集合成为边缘。
    6. 搜索算法基础
      1. 搜索算法需要一个数据结构来记录搜索树的构建过程,对树中的每个节点,我们定义的数据结构包含四个 元素:

      1. 问题求解算法的性能:
        1. 评价一个算法的性能考虑以下四个方面:
          1. 完备性
          2. 最优性
          3. 时间复杂度
          4. 空间复杂度
        2. 评价搜索算法的有效性:
          1. 可以只考虑搜索代价—取决于时间复杂度,也包括内存的使用;
          2. 也可以使用总代价—包括求解的搜索代价和解路径的路径总代价
  • 无信息搜索(盲目搜索)策略
    1. 无信息搜索算法:算法除了问题定义本身没有任何其他信息
    2. 搜索算法要做的是生成后继并区分目标状态与非目标状态。
    3. 这些搜索策略是以节点扩展的次序来分类的,以下为常见盲目搜索策略:
      1. 宽度优先搜索
      2. 一致代价搜索
      3. 深度优先搜索
      4. 深度受限搜索
      5. 迭代加深的深度优先搜索
      6. 双向搜索
    4. 无信息搜索策略对比
  • 有信息(启发式)的搜索策略:(知道一个非目标状态是否比其他状态更有希望接近目标的策略)
    1. 有信息的搜索算法,利用给定的只是引导能够更有效的找到解。
    2. 要考虑的一般算法称为最佳优先搜索,结点是基于评价函数f(n)值被选择扩展的,评估函数被看作是代价估计,因此评估值最低的节点被选择首先进行扩展。
    3. 最佳优先图搜索的实现与一致代价搜索类似,区别在于最佳优先是根据f值而不是g值对优先级队列排序的。
    4. 对f的选择决定了搜索策略,大多数的最佳优先搜索算法的f由启发函数构成

    1. 启发式信息导引搜索的两种形式
      1. 贪婪最佳优先搜索
      2. A*搜索:缩小总评估代价
      3. 存储首先的启发式搜索
      4. 学习以促搜索
  • 启发式函数
    1. 启发式的精确度对性能的影响
    2. 从松弛问题出发设计可采纳的启发式
    3. 从子问题出发设计可采纳的启发式:模型数据库
    4. 从经验中学习启发式
    5.  
  • 本章小结

这篇关于《人工智能 一种现代方法》第三版 第3章 通过搜索进行问题求解 笔记摘录的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1096640

相关文章

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil