人工智能
Artificial Intelligence (AI)
刘静
******@sdutcm.
理工学院
2009年春季
上一章中我们研究了知识表示方法,为人工智能问题的求解打下了基础。从问题表示到问题的解决,有一个求解的过程。接下来要研究的是实现求解的过程,采用的基本方法包括搜索和推理。本章先介绍搜索技术,将要讨论问题求解的搜索原理,包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理,包括AO*算法、遗传算法和模拟退火算法等。
第3章搜索推理原理
图的搜索策略
盲目搜索
启发式搜索
与或树搜索(补充)
博弈树搜索(补充)
消解原理
解决实际问题的两个关键之处:
①问题的表达
状态空间法
问题归约法
谓词逻辑法
②问题的求解
搜索技术
推理技术
盲目与启发式搜索:状态空间法、图的搜索技术
与或树搜索:问题归约法、与或图的特例的搜索技术
博弈树搜索:状态空间法+问题归约法、双人博弈的特殊搜索技术
消解原理:谓词逻辑法、推理技术
在介绍图搜索策略之前,让我们来看一个例子。 例子:从某王姓家族的四代中找王A的后代且其寿命为X的人。 王A:寿命47,有儿子王B1、王B3、王B2 王B1:寿命77,有儿子王C1、王C2 王B3:寿命52,有儿子王D1 王B2:寿命65,有儿子王E1、王E2 王F1:寿命32 王G1:寿命96 王C2:寿命87,有儿子王F1 王D1:寿命77,没有儿子 王E1:寿命57,有儿子王G1
王E2:寿命92,有儿子王H1 王C1:寿命27,没有儿子 王H1:寿命51 若X=57,下面讨论一种可通用的图搜索策略求解此问题。 如果是一个N代的家族表中找其寿命为X的人,我们最可能用的手工方法是从家族表的开始往下,例中还要求所找的人是某人的后代,就比较复杂了。如果用图来表示,就很容易了。图中把姓氏省去,每个成员的后代按例子中给出名字的先后顺序。图示为:
图 用图表示方法的家族表
图搜索策略
状态空间中:
状态
初始状态
目标状态
操作符
图中有:
节点
初始节点
目标节点
有向弧
状态空间法与图的对应关系
在状态空间中,解是从初始状态到目标状态的操作符序列
在图中,解是从初始节点到目标节点的一条路径
解的含义:
人工智能之(搜索推理技术1-图盲目搜索) 来自淘豆网m.daumloan.com转载请标明出处.
