.华南理工大学《人工智能》复习资料Ch2.【状态空间表示】?，GS，F?：初始状态的集合SF：操作的集合：目标状态的集合G}{{Q}，Q??，，ab，c}{，Q例如：570【状态空间图】按选择范围分类：全局择优搜索局部择优搜索f（xg(x)h(x)A*对对h(x)）（x【启发式搜索算法分类：考虑所有待考察节：只考虑当前节点的子节算法A）为当前点的代为距离目标的距算法的改进Ah*作限制，使其总是小于实际最小距，具有完备【与或图】【状态空间图搜索使用的数据结构】)(待考察节点OPEN表：已生成但没考察的节点)(搜索树CLOSED表：考察过的节点及节点间关系）Q可以分解为Q1+Q2与QQ1，Q2与等价（即i'}或等价（即与Q1可以转换为{Q1i}或Q1{Q1i'}）【与或图中的概念】本原问题：直接可解的问题。终止节点：本原问题对应的节点【广度/深度优先搜索特点】无子节点的节点端节点：广度优先：完备的(一定能找到最优解)，搜索效率低，OPEN子节点为与关系与节点：表为队列结构或节点：子节点为或关系深度优先：不能保证找到最优解，OPEN表为堆栈结构有界深度优先搜索：即使能求出解，也不一定是最优可变界深度优先搜索算法：深度可变，每次深度超过阈值深度搜索】/【与或图的广度)在的点，都被当作待考察点(CLOSED表中资料Word.Step1:S0放入OPEN表Step2:OPEN表第一个点（记为N）取出放入CLOSED表，冠以编号n。Step3:若n可扩展：(1)扩展N，其子节点放入OPEN表(深度:尾部，广度:首部)(2)考查这些节点是否终止节点。若是，放入CLOSED表，被标可解，得解。标为可解节点，并对先辈点标示。若S0。OPEN表删除具有可解先辈的节点。转Step2(3)从不可扩展：Step4:若N为不可解。(1)标示N标示先辈节。若(2)S0被标不可解，失败。Step2OPEN表删除具有不可解先辈的节点。转。(3)从β剪枝：节点倒推上确界余子节点MA节若其倒推下确不小MA的则不必扩展MA节点【与或图启发式搜索】由下往上更新函数值，函数值=子节点价值+子节点与父节点距离。例子见PP3Ch3.P117-120【博弈树】MAX的选择。因此站在我方与结点：对手(MIN)力图干扰MAX）的立场，由MIN出棋的结点具有与结点的性质。（MAX）力图通往取胜。MAX出棋的结点具或结点：我方（有或结点的性质。Ch3.【离散数学相关定义】命题（proposition）：具有真假意义的语句谓词(predicate)：刻画个体的性质、状态或个体间的关【α剪枝,β剪枝】的父亲P(x,y):x系，例如是yα剪枝：对MIN节点,若其倒推上确界β不大于MIN的父是变P(x,y)中，x,y如个体域：个体变元的变化范围。(节点倒推下确界α,即α≥β,则不必扩展该MIN节点其)元余子节点:全总个体域包揽一切事物的集合的例如个体之间的对应关系函数：,father(x):x值为父亲是项，，：个体常元和变元都是项。若项t1t2，…，tntnt2，t1f则（，…，）是项）tn，…，，t1：若原子公式t2t2，t1（为项，Ptn，…，资料Word.称为原子谓词公式，简称原子或原子公式谓词公式：原子公式是谓词公式。若A、B是谓词公式，则?A，A∪B等都是谓词公式辖域：紧接于量词之后被量词作用的谓词公式指导变量：量词后的变量约束变量：量词辖域中，与该量词的指导变元相同的变量自由变量：除了约束变量之外的变量一阶谓词：仅个体变元被量化的谓词二阶谓词：个体变元、函数符号、谓词符号被量化从谓词公式得到命题：(1)把谓词中的个体变元代入个体常元(2)把谓词中的个体变元全部量化如P(x)表示硜是素数,则?xP(x)，P(a)都是命题合取范式：B?B?…?B，如n12(P(x)?Q(x))?(?Q(y)?R(y))?(?P(z)?S(z))8?B，如B?B?…：析取范式n12))，v?u))?L(uP))?P))()?La，y?（?(x)C(z?(?(yD(?(谓词公式永真性：P对个体域D全部成立，则P在D上永真。P在全总个体集成立，则P永真谓词公式可满足性：P对个体域D至少有一个个体成立，则P在D上可满足。【常用逻辑等价式】【常用推理定律】资料Word.消去存在量词，把全称量词移到最左，右式为合取，如Skolem逻辑结论与前提且仅当对每个解释G也为真。互补文字归结式：和L2亲本子句消解基例如：x[P(f(x))R(x,g(x))]标准型与原公式一般并不等【命题逻辑中的归结原理定义的逻辑结论，2都为真，，如2的前提2LC包LC包LLL互补。L删除，并把剩余部分析取，得C12：...