人工智能总结

形象思维、抽象思维、灵感思维人工智能的核心内容：搜索技术、推理技术、知识表示、人工智能语言应用领域：专家系统、知识库系统、决策支持系统、自然语言理解、智能机器人、模式识别知识表示方法：谓词逻辑表示法、语义网络表示法(结构性好、明确简洁、直观，推理规则不明显，表达范围有限)、产生式规则表示法(格式固定、形式单一、规则间相互独立、模块性好、自然性好、求解效率低，专家系统首选)、框架表示法(对事物描述有层次，适应性强、结构性好、推理方式灵活，能把陈述性知识和过程性知识相结合，但缺乏形式理论)、概念从属表示法、剧本表示法(开场条件、角色、道具、场景、结果组成，呆板，知识表示范围窄)逆否律：X1一X2D-IX2一-IX1深度优先：深度深的节点排在OPEN表的前面，深度浅的节点排在后面定理1：隐含图为有限(无限)时，如果从初始结点到目标结点存在一条路径，则算法A(A*)一定成功结束。引理：A*结束前，OPEN表中必存在f(n)Wf*(s)的节点。OPEN表上任一具有f(n)<f*(s)的结点最终都被A*选为扩展的结点A*选作扩展的任意结点n，有f(n)Wf*(s)。定理6：若h(n)满足单调限制，则由A*所扩展的结点序列，其f值是非递减的。A*算法应用举例(1)八数码问题h(n)=0,h(n)w(n)一不在位将牌个数,h(n)=p(n)一将牌与其目标位之间的距离(2)传教士与野人问题N个传教士与N个野人h(n)=M+C-2B，船在左岸B=1，在右岸B=0(3)迷宫问题h(n)=|Xg-xn|+|Yg-yn|,取g(n)=d(n)有f(n)=d(n)+h(n)影响算法A启发能力的3个重要因素：路径耗散值、扩展结点数、计算h所需要的工作量子句：例如〜pVqVs是子句，子句集：将合取范式中的合取符号换成逗号归结式：有子句：C1=PVC1',C2=〜PVC2'，存在互补对，可得归结式C12=C1VC2例：P[x,f(A)]VP{x,f(y)]VQ(y)和-P[z,f(A)]V-Q(z)取{li}={P[x,f(A)]}{mi}={-P[z,f(A)]}，s={z/x}得P[z,f(y)]V-Q(z)VQ(y)取{li}={P[x,f(A)],P{x,f(y)]}，{mi}={-P[z,f(A)]}，s={z/x,A/y}得Q(A)V-Q(z)题型1：将下式化为Skolem标准型消去蕴含符号、〜深入到量词内部、变元易名、存在量词左移，直到所有量词移到前面，由此得到前束范式，再消去存在量词，略去任意量词题型2：用归结原理证明公式将代证明的公式转化为代归结命题公式如：(p-q)-(~q-~p)=>(p-q)分别将公式前项化为合取范式，结论求反的后项化为合取范式，两项合并后化为合取范式，求子句集，对子句集中的字句进行归结题型3：命题逻辑的归结过程建立待归结命题公式2.求合取范式3.建立子句集4.对子句集中的子句用归结规则(归结式作为新子句加入子句集进行归结，得到空子句，停止)题型4：谓词逻辑的归结过程1.写出谓词关系式2.用反演法写出谓词表达式3.化为Skolem标准型4.求取子句集S5.对S中可归结的子句进行归结6.归结式放入S中，反复归结过程7.得到空子句8.命题得证爬山法算法过程Hill-Climingn=s;LOOP:IFGOAL(n)THENEXIT(SUCCESS);EXPAND(n){mi},计算h(mi),nextn=m;//minh(mi)的结点，h(n)表示山顶与当前位置n的高度差IFh(n)<h(nextn)THENEXIT(FAIL);n=nextn;GOLOOP;可分解产生式系统DATA 初始数据库{Di} DATA的分解式；每个Di元素都看成单独的数据库until{Di}的所有元素都满足结束条件,do：begin从{Di}中选一个不满足结束条件的D*从{Di}中删去D*在规则集中选择一条可应用于D*的规则RDR应用到D*得到的结果{di}D的分解式在{Di}上添加diend回溯策略递归程序BACKTRACK(DATA)1.ifTERM(DATA),returnNIL//谓词Termination判断DATA是否满足结束条件2.ifDEADEND(DATA),returnFAIL//DEADEND判断从DATA表示的状态是否能继续下去RULES APPRULES(DATA)//APPRULES是一个函数，返回适用于DATA的规则表LOOP:ifNULL(RULES),returnFAIL//谓词NULL判断RULES是否空表RFIRST(RULES)//挑选出规则表中第一条规则RULESTAIL(RULES)//把规则表中地第一条规则删去RDATA R(DATA)//把规则R用于DATA产生一个新的DATAPATH BACKTRACK(RDATA)//在新的DATA上递归地调用BACKTRACKifPATH=FAIL,goLOOP//判断是否失败，转移到另一规则进行测试returnCONS(R,PATH)//把试探成功的规则串成一个表图搜索过程过程：GRAPHSEARCHG s,OPEN(s)；建立一个搜索图G,它只含有起始结点s。建立一个OPEN表,它只含有起始结点s,用于存放未被扩展的结点CLOSED ()；LOOP:ifOPEN=(),thenreturnFAILn FIRST(OPEN),OPENTAIL(OPEN),CLOSEDCONS(n,CLOSED)5.ifn 目标集，thenreturn[s...n]M expand(n),G'G,G{M,G}//扩展n,建立集M使M仅含有n的后继者而不含有n的祖先，并把M中的结点加入到G中。对M中所有结点m:ifmG’，then建立指针mn,OPENCONS(m,OPEN)ifmG’，then决定是否应改变指针mnifmCLOSED,then决定是否应改变m的后代的指针对OPEN表中的结点重新排序；这种排序可以是任意的，也可以是启发式的goLOOP深度优先搜索过程DEPTH-FIRST-SEARCHG s,OPEN(s)；CLOSED ()；LOOP:ifOPEN=(),thenreturnFAIL；n FIRST(OPEN),OPENTAIL(OPEN),CLOSEDCONS(n,CLOSED)；5.ifn 目标集，thenreturn[s...n]；M expand(n),G'G,G{M,G}；ADD(M,OPEN)；标记M到n的指针；goLOOP宽度优先搜索过程BREADTH-FIRST-SEARCHG s,OPEN(s)；CLOSED ()；LOOP:ifOPEN=(),thenreturnFAIL；n FIRST(OPEN),OPENTAIL(OPEN),CLOSEDCONS(n,CLOSED)；5.ifn 目标集，thenreturn[s...n]；M expand(n),G'G,G{M,G}；ADD(OPEN,M)；标记M到n的指针；goLOOP与或图的AO*算法G={s},q(s)=h(s),ifs目标集thenSOLVED(s)TuntilSOLVED(s),dobegin计算局部解图G‘(从s跟踪标记的连接符)选出一个非终叶结点n G'Pexpand(n),ifP= thenq(n)elsep PifpGthenq(p) h(p)ifp 目标集thenSOLVED(p) T,G {G,P}〃扩展结点n，产生它的所有后继结点并把它们接入仔，若不在G中，则赋值h(p)S{n}untilS=,dobegin从S中移出一个结点m,该结点在G中的所有后代都不在S中q'(m)q(m)qi(m)=ci+q(n1i)+...+q(nki)q(m)=miniqi(m)标记对应于q(m)的连接符r,抹掉不同的连接符标记ifjSOLVED(njr)=TthenSOLVED(m)TifSOLVED(m)Vq(m)q'(m)then将向m发出标记的连接符的那些父结点加入到S中endend控制策略CLAUSES=SuntilNILeCLAUSES,dobegin在CLAUSES中选择两个不同的可归结的子句Ci和Cj计算Ci和Cj的归结式rijCLAUSES=CLAUSESV{rij}endmgu递归程序UNIFY(E1,E2)ifatom(E2)then交换E1,E2ifatom(E1)thenbeginifE1=E2,thenreturn NILifE1为变量thenbeginifE2中有E1,thenreturnFAIL//xf(x)elsereturn{E2/E1}endifE2为变量 then return {E1/E2}elsereturn FAILend //E1和E2都是表13.F1(CARE1),T1(CDRE1