人工智能课件

人工智能(问题求解基本原理及搜索技术

)人工智能课件第1页问题求解基本原理问题求解：在给定条件下，寻求一个能处理某类问题且能在有限步骤内完成算法。

问题求解特征：传统软件：

①求解问题是能够用数学准确描述良结构问题（如，解方程）；②计算机执行繁杂统计计算任务普通不能看成是人工智能活动。AI软件：①求解是不可直接用数学模型描述所谓不良结构问题（如，几何证实、求不定积分、逻辑演算等），通常需要采取弱方法进行搜索求解；②

AI程序中符号内涵不但局限于数值计算和数据处理中普通数据信息，应表现人类进行推理所需要各种知识。人工智能课件第2页问题求解基本原理一、问题求解基本方法二、搜索技术人工智能课件第3页问题求解基本原理问题求解方法：基于状态空间问题求解方法基于问题空间问题求解方法基于博弈搜索问题求解方法人工智能课件第4页问题实例

桌上固定了3根柱子，按1，2，3次序排例。有n个大小全不一样大盘子d1，…，dn

，按从小到大，小在上次序依次插在第一根柱子上，要把这n个盘子全部搬到第三根柱子上，每次只许搬一个，任何时候都不允许把大盘子放在小盘子上面，问该怎样搬法。设n=3，该怎样搬法？1 23123梵塔问题人工智能课件第5页基于状态空间问题求解方法（1，1，1）→（1，1，2）（1，1，1）→（1，1，3）（1，1，2）→（1，3，2）。。。。。状态正当变换规则（满足约束条件）：状态定义-（i大,j中,k小）:设向量下标分别表示大盘、中盘、小盘；向量值分别表示盘子所在柱子编号。状态描述-大盘在第i根柱子上；中号盘在第j根柱子上，小号盘在第k根柱子上。人工智能课件第6页基于问题空间问题求解方法问题：怎样将

i柱子上m个盘子搬到k柱子上?将i柱子上m–1个盘子搬到j柱子上；将i柱子上第m个盘子搬到k柱子上；将j柱子上m–1个盘子搬到k柱子上。

问题描述：问题（a,b,c):将b柱子上a个盘子搬到c柱子上。问题分解正当规则： （3，1，3）--〉（2，1，2）(1，1，3）（2，2，3） 。。。。。。人工智能课件第7页基于问题空间问题求解方法人工智能课件第8页状态空间法相关概念

状态空间法:从问题初始状态出发，经过一系列状态变换找到目标状态问题求解方法。

状态：描述问题中事物形状或情况符号或数据结构。

状态空间：全部状态全体组成集合；用四元组（S,S0,O,G)表示:S:非空状态子集，S0=初始状态（非空）。G:非空目标状态子集。O:操作算子集合，一个状态正当转换为另一个状态描述规则

问题求解过程：隐含求一个普通有向图，节点-状态，边–算子

搜索空间：问题求解过程中抵达过全部状态（节点）集合。人工智能课件第9页状态空间法相关概念状态空间、搜索空间及解径关系：

问题解（解径）：初始状态到目标状态通路上每一条规则（或状态）组成序列，称为解径。解不唯一。S0

R1S2R2Sk…..RkG问题有解：从代表初始状态s节点出发，存在一条通向目标节点路径。人工智能课件第10页问题空间法相关概念问题空间法：首先产生待证问题全部子问题，而后经过处理全部子问题到达问题求解目标方法。

问题：描述问题及其子问题符号或数据结构。

问题空间：初始问题以及其全部子问题全体组成集合，用四元组（S,S0,F,G)

表示:

S:问题和子问题；S0

:初始问题。G:含有平凡解本原问题集合。F:操作算子集合，用于将问题分解成其若干个子问题描述规则人工智能课件第11页问题空间法相关概念（2）问题空间分解过程：隐含求一个与或图

节点

–问题，边

-

分解问题算子。

“与”节点：假如节点A有边通向一组节点{B1，B2，…..Bn}，问题A处理有待于A子问题组{B1,B2…..Bn}全部处理，则称A为“与”节点。如图a所表示。

“或”节点：若节点Ａ有边通向一组节点{{Ｂ１},{Ｂ2}，…{Ｂn}}，问题Ａ处理有待于子问题Ｂ１或Ｂ2或…或Ｂn中某一个子问题处理，则称A为“或”节点。如图b所表示。…...a:AB1B2Bn…...b:AB1B2Bn人工智能课件第12页问题空间法相关概念（2）问题解（解图）：从代表初始问题节点出发，搜索到一个完整‘与或’子图，图中全部叶节点均满足问题求解结束条件。例：（C,B,Z)-〉（M,…M)重写规则:R1:C(D,L)

R2:C(B,M)

R3:B(M,M)

R4:Z(B,B,M)

解图人工智能课件第13页小结–问题求解方法比较状态空间法问题空间法问题求解状态变换问题分解搜索过程隐含构建普通有向图隐含构建与或图节点状态问题边状态变换规则（算子）问题分解规则（算子）

求解解径解图人工智能课件第14页问题求解基本原理一、问题求解基本方法二、搜索技术（一）人工智能课件第15页搜索技术预备状态空间搜索相关概念盲目搜索策略启发式搜索策略问题求解基本原理人工智能课件第16页搜索策略预备盲目搜索：不考虑给定问题所含有特定知识，系统按照事先确定好某种固定次序调用规则，或是随机地调用规则。

惯用盲目搜索算法:

深度优先搜索策略；宽度优先搜索策略人工智能课件第17页搜索策略预备启发式信息：与问题求解相关信息和知识。因为信息片面性和不准确性，应用启发式信息不能百分之百地确保找到问题解，但能提升问题求解可能性。

启发式信息在问题求解过程中作用：有利于加速求解过程；有利于找到“较优”解。

启发式搜索策略:考虑给定问题领域含有特定知识（启发式信息），系统动态地要求规则调用次序，优先使用“较”适当规则。人工智能课件第18页搜索策略预备惯用基于状态图启发式搜索策略:爬山搜索策略(HillClimbing)大英博物馆搜索策略(BritishMuseum)启发式图搜索策略(A)最正确启发式图搜索策略(A*

)惯用基于与或图及博弈启发式搜索策略：最正确启发式与或图搜索策略(AO*)极大极小搜索策略(Minimax)α－β剪枝搜索策略(Alpha-BetaPruning)人工智能课件第19页基于状态空间搜索技术：

相关搜索概念

盲目搜索策略

启发式搜索策略问题求解基本原理人工智能课件第20页状态空间搜索相关概念状态图特点：多条路径通向同一节点。例：E人工智能课件第21页状态空间搜索相关概念人工智能课件第22页状态空间搜索相关概念

节点深度：根节点深度为0，其它节点深度要求为其父节 点深度加1，即dn+1=dn+1。

标识节点n：用指针将后继节点连接到父节点n操作。

节点：对应状态图中相关状态描述。扩展节点n：称生成节点n全部后继节点并计算生成这些后继节点所造成花费过程（即，计算各后继节点优劣且将其连接到节点n等操作造成开销）叫做扩展节点n。

后继节点：称将规则作用于节点n生成新节点为节点n后 继节点。人工智能课件第23页路径：对于一个节点序列（n0,n1,…,nl,…,nk），如若每一节点ni-1都有一个后继节点ni（i=1,2,…,k），则称该节点序列为一条从节点n0到节点nk、长度为k路径；路径还可表示为与节点序列对应规则序列。状态空间搜索相关概念路径花费：设C（ni，nj）为节点ni到nj这段路径（或弧线）花费。一条路径花费等于连接这条路径各节点间全部弧线花费值总和。路径ni

→nj→t花费值C（ni，t）可递归计算以下:

C（ni，t）=C(ni，nj)+C（nj，t)。人工智能课件第24页基于状态空间盲目搜索算法:宽度优先搜索策略深度优先搜索策略问题求解基本原理人工智能课件第25页盲目搜索算法符号及数据结构

s：

初始节点；n：当前节点。

open：

已被生成但未被扩展节点序列表；closed：已被生成且已被扩展节点序列表；{mi}={mj}∪{mk}∪{ml}：扩展n后所得n后继节点其中，{mk}：在OPEN表中出现过待扩展节点，{ml}：在CLOSED表中出现过已扩展节点。{mj}：第一次生成节点，mj∈OPEN且mj∈CLOSED表，人工智能课件第26页宽度优先搜索算法

open:=[S];closed:=[];whileopen≠[]do{ n:=first(open); remove(first(open));

add(n,closed)；

ifn=goalthenexit(success); expand(n)->{mi}; delete((mi)(mi∈

{mk}∨

(mi∈{ml}

)

);

add(open,mj)};exit(fail);人工智能课件第27页宽度优先搜索算法

1、S,A,D2、A,D,B,D3、D,B,A,E………Open表为队操作：先进先出！人工智能课件第28页G节点扩展次序宽度优先搜索算法

人工智能课件第29页

open:=[S];closed:=[];d=深度限制值whileopen≠[]do{ n:=first(open); remove(first(open)); add(n,closed)；

ifn=goalthenexit(success); ifdepth(n)>dthencontinue; expand(n)->{mi}; delete((mi)(mi∈{mk}∨(mi∈{ml}

));

add(mj,open)};exit(fail);深度优先搜索算法人工智能课件第30页深度优先搜索算法

1、S2、A,D3、B,

D,D………Open表为栈操作：后进先出！4、C,

E,D人工智能课件第31页节点扩展次序深度优先搜索算法

人工智能课件第32页盲目搜索算法应用实例-8数码问题描述状态：

矩阵(Sij)，其中

1≤i,j≤3，Sij∈{0,1,…,8};人工智能课件第33页盲目搜索算法应用实例-

正当走步规则：设(i0、j0)为空格所在行列数值，

Si0j0=0R1:ifj-1≥1thenSi0j0:=

Si0(j0-1),Si0(j0-1):=0空格左移；R2:ifi-1≥1thenSi0j0:=

S(i0-1)j0,S(i0-1)j0:=0空格上移；R3:ifj+1≤3thenSi0j0:=

Si0(j0+1),Si0(j0+1):=0空格右移；R4:ifi+1≤3thenSi0j0:=

S(i0+1)j0,S(i0+1)j0:=0空格下移。8数码问题人工智能课件第34页宽度优先策略求解8数码问题：目标R1R2R3R2R1R2R3R2R2R3R2R4R1R3人工智能课件第35页深度优先策略求解8数码问题：说明：

设规则固定使用次序：R1-左移、R2-上移、R3-右移、R4-下移；设节点深度限制值：6；正当走步规则重复节点–造成循环人工智能课件第36页问题求解基本原理基于状态空间启发式搜索算法:

A算法；A*算法人工智能课件第37页人工智能课件第38页启发式图搜索算法假设：

f(n)=g(n)+h(n)

–任意节点n

评价函数：指迄今为止已找到从初始节点s，抵达节点n，再从节点n抵达目标节点t路径全程最小费用，是对f*(n)一个预计。

h(n)

：迄今为止从节点n到目标节点t最正确分段路径将要花费未知预计费用，是对h*(n)一个预计，可视为启发式分量函数，有h(n)≥0。

g(n)

：迄今为止搜索到从初始节点s到当前节点n最正确路径分段已知费用，是对g*(n)一个预计。

f*(n)=g*(n)+h*(n)：从初始节点s出发，经过最正确路径上任意节点n，抵达目标节点t最小费用。

h*(n)：n→t最正确路径分段费用。

g*(n)：s→n最正确路径分段费用。

s：初始节点；n：当前节点；t：目标节点。人工智能课件第39页启发式图搜索算法-A算法

定义：按照f(n)=g(n)+h(n)估价函数值由小到大地排列待扩展节点次序图搜索算法，称为A算法。

A算法流程。A算法应用实例:

普通有向图A算法搜索实例；

8数码问题A算法搜索实例。人工智能课件第40页启发式图搜索算法-A算法算法中符号：s：初始节点；G：搜索图节点集合；OPEN表：已生成但还未被扩展节点序列表；CLOSED表：已生成且已被扩展节点序列表；n：待扩展当前节点；{mi}={mj}∪{mk}∪{ml}：扩展n后生成后继节点其中，mj：第一次生成节点，mj∈OPEN且mj∈CLOSED表，mk：在OPEN表中出现过待扩展节点，ml：在CLOSED表中出现过已扩展节点。人工智能课件第41页A算法n为目标t?取当前节点nn:=first(OPEN),从OPEN中删除n,CLOSED:=CLOSED∪{n}初始化G:=G0∪S,OPEN:=(S)CLOSED:=(),f(S):=g(S)+h(S)OPEN=Φ

^未发觉目标tReturn(Fail)AyesNoyesNoBExit(Success)输出解径人工智能课件第42页扩展节点n：生成n后继节点；计算后继节点花费。{mi}:=Expand(n),计算:f(n,mi):=g(n,mi)+h(mi)比较花费，修改连接标识

对于{mj}∈{mi}:OPEN:=OPEN∪{mj},mj->n;

对于{mk}∈{mi}:

iff(n,mk)<f(mk)thenf(mk):=f(n,mk),mk->n;

对于{ml}∈{mi}:iff(n,ml)<f(ml)thenf(ml):=f(n,ml),ml->n,OPEN:=OPEN∪{ml}将OPEN表中节点按f值从小到大重新排序AB人工智能课件第43页启发式最正确图搜索算法-A*算法A*算法定义：

若将A算法中评价函数f(n)启发式分量函数h（n）值限制在h*（n）下界范围内，亦即对全部节点n，都满足h（n）≤h*（n），则称此时A算法为A*算法。

A*算法作用：问题有解时，A*算法一定能够找到从初始节点s