华南理工大学《人工智能》复习资料

华南理工大学《人工智能》复习资料Ch2.【状态空间表示】SFG，，S：初始状态的集合F：操作的集合G：目标状态的集合例如：507{}{}{}QabcQQ，，，，，【状态空间图】【状态空间图搜索使用的数据结构】OPEN表：已生成但没考察的节点(待考察节点)CLOSED表：考察过的节点及节点间关系(搜索树)【广度/深度优先搜索特点】广度优先：完备的(一定能找到最优解)，搜索效率低，OPEN表为队列结构深度优先：不能保证找到最优解，OPEN表为堆栈结构有界深度优先搜索：即使能求出解，也不一定是最优可变界深度优先搜索算法：深度可变，每次深度超过阈值的点，都被当作待考察点(在CLOSED表中)【启发式搜索算法分类】按选择范围分类：全局择优搜索：考虑所有待考察节点局部择优搜索：只考虑当前节点的子节点【A*算法】f（x）＝g（x）＋h（x）g(x)为当前点的代价h(x)为距离目标的距离A*对A算法的改进：对h(x)作限制，使其总是小于实际最小距离h（x）h*（x），具有完备性【与或图】Q与Q1，Q2与等价（即Q可以分解为Q1+Q2）Q1与{Q1i},{Q1i’}或等价（即Q1可以转换为{Q1i}或{Q1i’}）【与或图中的概念】本原问题：直接可解的问题。终止节点：本原问题对应的节点端节点：无子节点的节点与节点：子节点为与关系或节点：子节点为或关系【与或图的广度/深度搜索】Step1:S0放入OPEN表Step2:OPEN表第一个点（记为N）取出放入CLOSED表，冠以编号n。Step3:若n可扩展：(1)扩展N，其子节点放入OPEN表(深度:尾部，广度:首部)(2)考查这些节点是否终止节点。若是，放入CLOSED表，标为可解节点，并对先辈点标示。若S0被标可解，得解。(3)从OPEN表删除具有可解先辈的节点。转Step2。Step4:若N不可扩展：(1)标示N为不可解。(2)标示先辈节。若S0被标不可解，失败。(3)从OPEN表删除具有不可解先辈的节点。转Step2。【与或图启发式搜索】由下往上更新函数值，函数值=子节点价值+子节点与父节点距离。例子见PP3Ch3.P117-120【博弈树】与结点：对手(MIN)力图干扰MAX的选择。因此站在我方（MAX）的立场，由MIN出棋的结点具有与结点的性质。或结点：我方（MAX）力图通往取胜。MAX出棋的结点具有或结点的性质。【α剪枝,β剪枝】α剪枝：对MIN节点,若其倒推上确界β不大于MIN的父节点倒推下确界α,即α≥β,则不必扩展该MIN节点其余子节点β剪枝：对MAX节点,若其倒推下确界α不小于MAX的父节点倒推上确界β,即α≥β,则不必扩展该MAX节点其余子节点Ch3.【离散数学相关定义】命题（proposition）：具有真假意义的语句谓词(predicate)：刻画个体的性质、状态或个体间的关系，例如P(x,y):x是y的父亲个体域：个体变元的变化范围。(如P(x,y)中，x,y是变元)全总个体域:包揽一切事物的集合函数：个体之间的对应关系,例如father(x):值为x的父亲项：个体常元和变元都是项。若t1，t2，…，tn是项，则f（t1，t2，…，tn）是项原子公式：若t1，t2，…，tn为项，P（t1，t2，…，tn）称为原子谓词公式，简称原子或原子公式谓词公式：原子公式是谓词公式。若A、B是谓词公式，则¬A，A∪B等都是谓词公式辖域：紧接于量词之后被量词作用的谓词公式指导变量：量词后的变量约束变量：量词辖域中，与该量词的指导变元相同的变量自由变量：除了约束变量之外的变量一阶谓词：仅个体变元被量化的谓词二阶谓词：个体变元、函数符号、谓词符号被量化从谓词公式得到命题：(1)把谓词中的个体变元代入个体常元(2)把谓词中的个体变元全部量化如P(x)表示x是素数,则xP(x)，P(a)都是命题合取范式：B1B2…Bn，如(()())(()())(()())PxQxQyRyPzSz8析取范式：B1B2…Bn，如(()())(DyLayPxCzPuLuv，（()())())(，))谓词公式永真性：P对个体域D全部成立，则P在D上永真。P在全总个体集成立，则P永真谓词公式可满足性：P对个体域D至少有一个个体成立，则P在D上可满足。【常用逻辑等价式】【常用推理定律】【子句集】文字：原子谓词公式及其否定子句：任何文字的析取【子句集特点】1.没有蕴含词、等值词2.“¬”作用原子谓词3.没有量词(、)4.合取范式5.元素之间变元不同6.集合形式【由谓词公式得到子句集】(对应子句集特点的序号)1.根据蕴含等价式消去蕴含关系2.根据量词转换律、双重否定律、摩根定律转换3.存在量词：受x约束，则定义f(x)替换y(Skolem函数)不受x约束，常量代替y(Skolem常量)全称量词：直接消去4.根据分配率合取5.各个合取子句变量改名6.把合取符号替换为逗号，组成集合【Skolem标准型】消去存在量词，把全称量词移到最左，右式为合取，如x[P(x，f(x))¬R(x,g(x))]Skolem标准型与原公式一般并不等价【命题逻辑中的归结原理定义】逻辑结论与前提：G是F1、F2、…、Fn的逻辑结论，当且仅当对每个解释I，如果F1、F2、…、Fn都为真，则G也为真。F1、F2、…、Fn为G的前提。互补文字：L与¬L归结式：C1包含L1，C2包含L2，L1与L2互补。把L1和L2删除，并把剩余部分析取，得到C12亲本子句：上例中C1与C2消解基：上例中L1与L2例如：【归结原理定理】1.谓词公式A不可满足当且仅当其子句集S不可满足。2.G是公式F1、F2、…、Fn的逻辑结论，当且仅当F1F2…Fn=G3.G是公式F1、F2、…、Fn的逻辑结论，当且仅当F1F2…Fn¬G不可满足4.归结式是其亲本子句的逻辑结果5.子句集S的C1，C2替换为C12得到S1，则S1不满足=S不满足6.子句集S添加C12得到S2，则S2不满足=S不满足【归结反演法】否定目标公式G，¬G加入到F1F2…Fn中，得到子句集S。对S进行归结，并把归结结果并入S，直到得到空子句，原问题得证。【替换定义】替换：{t1/x1,t2/x2,…,tn/xn}替换的分子：t1,t2,…,tn是项替换的分母：x1,x2,…,xn是互不相同的个体变元(ti,,xi不同,xi不循环出现在tj中,如{f(x)/y,g(y)/x}不是替换)基替换：t1,t2,…,tn是不含变元的项（称为基项）空替换：没有元素的替换，记作ε表达式：项、原子公式、文字、子句的统称基表达式：没有变元的表达式例/特例：对公式E实施替换θ，记为Eθ，所得结果称为E在θ下的例复合/乘积：θ＝{t1/x1,t2/x2,…,tm/xm}，λ＝{u1/y1,u2/y2,…,un/yn}，删除{t1λ/x1,t2λ/x2,…,tmλ/xm,u1/y1,u2/y2,…,un/yn}中：(1)tiλ/xi当tiλ＝xi(2)ui/yi当yi∈{x1,…,xn}得到θ与λ的复合或乘积，记为θ•λ例如：θ={a/x,f(u)/y,y/z},λ={b/u,z/y,g(x)/z}从{a/x，f(b)/y，z/z，b/u，z/y，g(x)/z},删去：z/z，z/y，g(x)/z得到：θ·λ={a/x，f(b)/y，b/u}【合一定义】合一：F1λ=F2λ=…=Fnλ则λ为F的合一，F为可合一的（一个公式的合一一般不唯一）最一般合一：σ为F的一个合一，如果对F任何合一θ都存在λ使得θ＝σ•λ，则σ为F的最一般合一，极为MGU（一个公式集的MGU不唯一）差异集：S是具有相同谓词名的原子公式集，从各公式左边开始，同时向右比较，直到发现第一个不都相同的项为止，用这些项的差异部分组成的集合【合一算法】Step1：置k＝0，Fk＝F，σk＝ε；Step2：若Fk只含有一个谓词公式，则算法停止，σk就是最一般合一；Step3：求Fk的差异集Dk；Step4：若Dk中存在元素xk和tk，其中xk是变元，tk是项且xk不在tk中出现，则置Sk＋1＝Fk{tk/xk},σk+1=σk•{tk/xk}，k＝k+1然后转Step2；Step5：算法停止，F的最一般合一不存在。对任一非空有限可合一的公式集，一定存在最一般合一，而且用合一算法一定能找到最一般合一【合一算法例子】求公式集F＝{Q(a,x,f(g(y))),Q(z,h(z,u),f(u))}的最一般合一解：解k＝0；F0＝F，σ0＝ε，D0＝{a,z}σ1＝σ0·{a/z}={a/z}F1=F0{a/z}={Q(a,x,f(g(y))),Q(a,h(a,u),f(u))}k＝1；D1={x,h(a,u)}σ2=σ1·{h(a,u)/x}＝{a/z,h(a,u)/x}F2=F1{a/z,h(a,u)/x}={P(a,h(a,u),f(g(y))),P(a,h(a,u),f(u))}k＝2；D2＝{g(y),u}σ3＝{a/z,h(a,g(y))/x,g(y)/u}F3=F2{g(y)/u}={P(a,h(a,g(y)),f(g(y)))}S3单元素集，σ3为MGU。【谓词逻辑中的归结原理定义】二元归结式（二元消解式）:（C1σ－{L1σ}）∪（C2σ－{L2σ}）,其中：亲本子句：C1，C2为无相同变元的子句消解文字：L1，L2σ为L1和¬L2的最一般合一因子：Cσ。其中σ为C的子句文字的最一般合一单因子：Cσ为单元句子RSPC12【归结式】子句的C1，C2归结式，是下列二元归结式之一:（1）C1和C2的二元归结式；（2）C1和C2的因子的二元归结式；（3）C1因子和C2的二元归结式；（4）C1的因子和C2的因子的二元归结式。归结注意事项：(1)两个子句不能含有相同的变元(2)归结的子句内部含有可合一的文字，则需进行简化【谓词逻辑的消解原理/归结原理】谓词逻辑中的消解（归结）式是它的亲本子句的逻辑结果：C1C2＝（C1σ－{L1σ}）∪（C2σ－{L2σ}）【谓词逻辑的定理】如果子句集S是不可满足的，那么必存在一个由S推出空子句的消解序列。【应用归结原理求取问题答案】Step1：前提化为子句集SStep2：确定目标谓词，化为子句，并析取助谓词新子句，并入到S形成S’。Step3：对S’应用归结原理。Step4：当只剩辅助谓词时，归结结束。(例子见CH3P105)【归结策略】Step1：子句集S置入CLAUSES表Step2：若Nil在CLAUSES，归结成功Step3：若CLAUSES存在可归结子句对，则归结，并将归结式并入CLAUSES表，step2Step4：归结失败【广度优先搜索归结策略】用于确定归结策略step3的搜索次序第一轮：0层（原子句集S）两两进行归结，产生1层下一轮：1层与0、1层两两进行归结，得到2层再一轮：2层与0、1、2层两两进行归结，得到3层如此类推，直至出现Nil【归结策略完备性】一个归结策略是完备的，如果对于不可满足的子句集，使用该策略进行归结，最终必导出空子句Nil。（广度优先是完备的，亦称水平浸透法）【归结策略出发点】（1）简化性策略。（2）限制性策略。（3）有序性策略（包含排序策略）【归结策略类型】删除策略支持集策略线性归结策略单元归结策略语义归结策略祖先过滤型策略【正向演绎推理--初始事实F0】任意谓词公式前束范式表示；消去量词，改名与或图表示：析取部分用与节点表示合取部分用或节点表示【正向演绎推理--F－规则】形如L=W，L为单一文字W为任意与或型谓词公式；(消去量词，改名)【正向演绎推理—目标谓词】文字的析取式(消去量词，改名)【正向演绎推理图解】012':()(()())':()()':()()':()()FPxQxRxFPySyFQzNzGSaNa¬P(x)∨(Q(x)∧R(x))Q(x)∧R(x)¬P(x)Q(x)R(x)Q(z)¬P(y)N(x)¬S(x)F0F1{x/z}F2{x/