人工智能考试整理.docx

人工智能考试整理.docx

《人工智能考试整理.docx》由会员分享，可在线阅读，更多相关《人工智能考试整理.docx（28页珍藏版）》请在冰点文库上搜索。

人工智能考试整理

智能定义〔知识阈值理论〕智能就是在巨大的搜索空间中迅速找到一个满意解的能力

智能的综合性定义:

智能是知识和智力的总和。

其中知识是智能行为的根底。

智能的特征:

1〕具有记忆与思维能力

存贮有感官得到的外界信息并加以处理〔如分析，计算，联想、决策等〕

2〕具有感知能力：

通过感官获取外部信息的能力。

3〕具有自适应能力

通过与外部世界交互学习，积累经验，增长知识，以适应环境变化。

4〕具有表达能力

通过语言、手势、表情等方式完成信息的输出。

深蓝：

能够模拟人的思维，进行博弈的计算机。

1997年5月12日，一个名为“深蓝〞〔deepBlue〕的IBM计算机系统战胜当时的国际象棋冠军盖利.卡斯帕罗夫

图灵测试：

两个房间，一个是人，一个是机器，测试者通过一系列的提问，如果提问题的人无法分辨是人还是机器在答复以下问题，那么认为该机器具有智能

人工智能〔ArtificalIntelligence，简称AI〕又称机智能machineintelligence，一般认为起源于美国1956年的一次夏季讨论〔达特茅斯会议〕在这次会议上，第一次提出了“ArtificalIntelligence〞这个词。

AI的本质问题：

研究如何制造出人造的智能机器或系统，来模拟人类的智能活动的能力，以延伸人们智能的科学。

产生式系统由三个局部组成

1〕综合数据库〔GlobeDatabase〕

也称为：

事实库，上下文等。

作用:

存放问题求解的过程中产生的状态描述信息。

2〕规那么库〔RuleBase〕（问题本身知识、求解知识）

也称为规那么基、规那么集等。

作用：

存放规那么知识。

产生式规那么的一般表达形式：

IF〔前提〕…THEN（结论）…

即：

如果…那么….

例：

1〕数学定理

2〕IFA是一种动物ANDA是哺乳动物ANDA吃肉

THENA是高级动物

关于不精确推理

当规那么的前提成立时，结论并非完全成立。

这种推理称为不精确推理。

通常采用阈值方法来解决此类问题。

〔3〕控制策略〔ControlStrategy〕

a选择规那么库中的规那么与综合数据库的事实进行匹配，匹配成功的规那么为可用规那么，否那么为不可用规那么。

b规那么冲突的解决〔可用规那么书>1〕。

c将选中的规那么的结论放入综合数据库。

产生式系统的特点：

1模式化：

所有规那么具有相同的形式

2结构化：

规那么见的关联比拟简单，容易维护。

3自燃性：

规那么表达了因果关系，比拟符合人们的思维方式，容易理解。

4单一性：

智能处理因果关系问题。

5效率低，规那么匹配过程很大。

产生式系统的适用范围：

1〕知识杂乱、事实众多、无统一理论的领域

2〕该领域的知识能够抽象出来

3〕该领域的知识可分解为一组独立的动作，以便用规那么加以表示。

概括说的说：

问题空间从一个状态到另一个状态的转移序列独立的领域可采用产生式系统模拟。

产生式系统一般性算法：

1DATA←初始数据库

2untilDATA满足结束条件条件之前do：

3Begin

在规那么集中选择某一可用于DATA的规那么R

DATA←R应用到DATA后得到的结果

END

例1字符转换

问题：

设字符转换规那么

A∧B→CA∧C→D

B∧C→GB∧E→F

D→E

：

A,B

求：

F

一、综合数据库

{x}：

其中x为字符

二、规那么集

IFA∧BTHENC

IFA∧CTHEND

IFB∧CTHENG

IFB∧ETHENF

IFDTHENE

三、控制策略

顺序排队

四、初始条件{A,B}

五、结束条件：

例2八数码游戏

问题：

一个3×3棋盘有八张牌1,2，…8及一个空格，空格周围的牌可以向空格移动。

求解：

给定一个初始状态s一个目标状态G，求S到G的走步序列。

产生式系统的根本控制策略

概括的讲：

产生式系统控制策略---搜索

1〕不可撤回方式

2〕试探性方式

a回溯方式〔Backtracking〕

b图搜索方式〔Graphsearch〕

1.不可撤回方式

根本策略：

选择规那么时只依靠局部知识〔信息〕，而不考虑是否全局最正确选择，只能满足局部优化条件，用过的规那么不再撤回。

特点：

a方法简单，容易实现

b具有一定的局限性，适用范围小〔只可用于单极值情况〕

c可能会造成规那么的屡次重复使用。

比方：

‘爬山算法’，不可用于解决多极值问题。

关于局部知识的利用：

设计局部评价函数W（n）,根据W（n）最大为原那么来选择规那么。

例：

八数码问题

设：

-W（n）:

不在位的数码个数n：

任意状态

目标状态：

-W（n）=0〔每个数码就位〕

最不利状态-W（n）=-8

〔每个数码都不在规定的位置〕

2.回溯方式

根本策略：

试探性的选择一条规那么，如果发现此规那么不适宜，那么退回去另选其他规那么。

关键在于回溯条件的设定。

特点：

a实用性好（相对不可回撤方式）

b适用范围较大，在一定程度上能防止盲目性

c可解决局部极值问题

设计方法：

a确定适宜的回溯条件

b充分利用可用知识来排列规那么，减少回溯次数

例：

八数码游戏〔主要讨论回溯条件〕

回溯条件：

a新产生的状态已经在搜索过程中出现；

b应用规那么的数量已经超过规定值（深度限制）

c当前状态，无可用规那么

满足上述条件之一那么产生回溯，每次回溯一层。

3.图搜索方式

根本策略：

它是一种展开式搜索方法，把问题空间看成一张隐含图，从中搜索出一条解路径。

特点：

a实用性好

b能保存完整的搜索树

c对于解空间较大的问题而言，搜索代价较大。

例：

八数码问题

这是一个典型的宽度优先策略，所以搜索代价比拟大。

总结：

三种控制策略的特点

1〕不可撤回方式：

沿一条路径单向延伸搜索

2）回溯方式：

可修正搜索路径

3〕图搜索方式：

展开式搜索，可保存完整的搜索树。

产生式系统分类

1.一般性产生式系统

根据规那么的应用方式，一般性产生式系统可以分为三种类型：

1〕正向系统〔数据驱动〕

采用正向推理方式，即由初始状态推理到目标状态，正向系统里的规那么是正向使用的:

规那么的前提成立，那么规那么的结论成立。

2）反向系统〔目标驱动系统〕

采用反向推理方式：

即由目标状态反向推理找到初始状态。

反向系统的规那么是反向使用的：

先假设规那么的结论成立，在寻找使其成立的前提条件。

3〕双向系统

由数据、目标双向驱动，最后终止在某个中间状态。

例：

数学证明思路

2.可交换产生式系统

定义：

满足以下性质的产生式系统称为可交换产生式系统

a给定可以用于数据库D的规那么集R，对于使用R中的任何规那么后产生的任何数据库，规那么集R仍然可用。

（规那么适用性）

b如果目标条件被D满足，那么应用R中的任何规那么于D上所产生的任何数据库仍可满足目标条件。

（数据库可用性）

c应用R中一个规那么序列于D上后，得到的数据库不随这规那么序列次序变化而变化。

〔规那么次序无关性〕

3.可分解产生式系统

定义：

任何待求解的数据库都可以分解为假设干个独立处理分量的产生式系统称为可分解产生式系统。

求解方法：

将初始数据库分解为几个可独立处理的分量，用规那么分别求解，生成新的数据库，再分解，再求解，知道结束。

可分解产生式系统的一般性算法：

1DATA←初始数据库

2{Di}←DATA，Di库：

独立的分量数据库

3until{Di}的所有元素都满足结束条件之前，do：

4begin5从{Di}中选择一个不满足结束条件的D*

6把D*从{Di}中删除

7从规那么集R中选一条可用于D*的规那么r，设D是人应用于D*的结果是D的分解式。

8在{Di}添加di

9end

AI领域的知识分类

a陈述性知识：

用于描述综合数据库的状态。

〔如事实等〕

b过程性知识：

用于规那么中表达问题的知识.〔如客观规律等〕

c控制性知识：

用于构成控制策略的知识〔算法、数据结构等〕

AI系统的一个难题：

知识表达问题，要能够客观的描述现实，简化求解过程，有效的提高求解效率，降低求解代价。

产生式系统的搜索策略

状态空间：

由给定问题的所有可能的状态组成的空间〔相当于全集G〕

搜索空间：

按某种策略在状态空间中选取的局部空间〔G的子集〕

解路径〔解空间〕：

求解问题的一条有效路径。

搜索策略的根本思路：

搜索空间必须包含解路径，如果问题有解，且尽量缩小搜索空间。

搜索策略的评价准那么：

总体费用最低

费用的划分：

a规那么应用的费用：

执行规那么时所花的费用b控制费用：

选择规那么所花的费用。

1.回溯策略

2.图搜索策略

3.启发式图搜索策略1〕A算法2〕爬山算法3〕分支界限算法4〕动态规划算法5〕A*算法

6〕h函数与A*的关系7〕关于单调性限制8〕A*算法例如

例四皇后问题

定义综合数据库：

设：

DATA={ij︱1<=i,j<=4},其中：

ij表示棋子所在行列如：

24表示第二行第四列有一枚棋子

因为棋盘上可放入的棋子数为0～4个

所以集合中元素数位0～4个，即length〔DATA〕=0～4

图搜索的实质是从问题空间中找出一张包含目标节点的子图。

图搜索的结果：

1，一个完整的搜索图G。

2一个解路径，用指针表示的解路径。

ProcedureGraphSearch

1G=G0（G0=s）,open=（s）//s:

初始状态

2closed=（）

3Loop:

ifopen=（）thenexit（fall）

4n←first（open）remove（n,open）,add（n,closed）

5ifgoal（n）thenexit（success）

6{mj}←expand（n）,//mj不含n的先辈节点

7open←add（open，mj）//mj不在open，closed中

标记mj每个到n节点指针

确定是否需要修改已在open，closed中的每个节点到n的指针

确定是否需要修改已在closed中的每个节点的后继节点原来的指针。

8按照某种方式排列open表中的节点，goloop

深度优先算法

Procedruedepth-First-Search

1G=G0（G0=s）,open=（s）,closed=（）//s:

初始状态

2Loop:

ifopen=（）thenexit（fall）

3n←first（open）

4ifgoal（n）thenexit（success）

5remove（n,open）,add（n,closed）

6{mj}←expand（n）,//mj不含n的先辈节点

7open←add（open，mj）//mj不在open，closed中

标记mj每个到n节点指针，按照节点深度递减顺序排列open中的节点

8goloop

讨论1：

如果问题有解，有深度优先搜索算法，是否能够找到解？

不一定.解空间是否有限？

讨论2：

本算法的改良之处是open中节点按照深度优先排列，但是没有对深度加以控制，可能造成搜索代价太大

宽度优先算法：

Procedruebreadth-First-Search

1G=G0（G0=s）,open=（s）,closed=（）//s:

初始状态

2Loop:

ifopen=（）thenexit（fall）

3n←first（open）

4ifgoal（n）thenexit（success）

5remove（n,open）,add（n,closed）

6{mj}←expand（n）,//mj不含n的先辈节点

7open标记每个到n节点指针，按照节点深度递增顺序排列open中的节点

8goloop

理论上可以利用宽度优先搜索能够找到解，如果问题有解的话。

讨论：

宽度优先算法和深度优先算法可能出现组合爆炸。

都没有利用任何启发式信息，所以称为无信息搜索策略pen←add（open，mj）//mj不在open，closed中

宽度优先例题：

由一张桌子T、三个积木A、B、C组成一个积木世界，初始状态是A在B上，B在桌子上，C在桌子上；目标状态是：

A、B、C依次从上到下排列在桌子上。

如图

解：

1〕状态描述〔P1，P2，P3〕表示按A、B、C顺序依次分别在P1,P2,P3上其中Pi是积木或者桌子。

初始状态时〔B、T、T〕,目标状态可以表示〔B、C、T〕

2〕定义操作:

move（x,y）表示将积木x移到Y上；

约束条件:

aX顶部必须是空的b如果Y是积木，Y的顶部必须是空c同一种状态出现不得多于一次。

1〕解题过程2〕open表和closed表

3〕节点样子画出整个图G和解路径

4〕程序何时结束5〕改用深度优先如何？

启发式图搜索策略：

根本概念

启发式图搜索的实质是利用启发信息有目的地进行搜索，减少搜索的盲目性。

降低搜索空间找到最正确解

启发式信息用于解决open表中节点的排列次序问题，方法是利用一个评价函数计算open表中节点的评价函数值，按照函数值从小到大排列所有节点。

评价函数的目的：

把最有希望得到最正确解或者解的排列在前面。

路径：

给定节点序列〔n0，n1，…nk〕。

如果该序列中的任一节点ni-1都有后继节点ni，那么该节点序列为从n0到nk的一条路径，路径长度为K

路径耗散值：

路径耗散值等于该路径上所有相邻节点间耗散值的总和。

设：

路径山任两点间的耗散值为才C（ni,nj）,那么从ni到nk的路径耗散值为C（ni,nj）=C（ni,nj）+C（nj,nk）

最正确路径耗散值：

最正确路径上的实际耗散值，记为：

K（ni,nj）.

K（ni,nj）<=C（ni,nj）

定义几个函数

1〕g*（n）=k（s,n）:

从初始节点s到当前节点n的最正确路径的耗散值。

2）h*（n）=k（n,t）:

从当前节点n到目标节点t的最正确路径的好三者。

3）f*（n）=g*（n）+h*（n）:

从初始节点s通过当前节点n到目标节点t的最正确路径的耗散值。

4）评价函数：

f（n）=g（n）+h（n）,其中f，g，h分别是f*，g*，h*的估计值。

通常约定:

f（n）按照升序排列。

讨论：

有上述定义，得:

1）g（n）>=g*（n）2）当h=0且g（n）=d（n）时，f（n）=d（n）既宽度优先策略，d（n）:

节点深度。

3〕h（n）称为启发函数。

A算法：

1G=G0（G0=s）,open=（s）,closed=（），f（s）=g（s）+h（s）//s:

初始状态

2Loop:

ifopen=（）thenexit（fall）

3n←first（open）h（）

4ifgoal（n）thenexit（success）

5remove（n,open）,add（n,closed）

6{mj}←expand（n）,//mj不含n的先辈节点

计算f（n,mi）=g（n,mi）+h（mi）,（自s经过n，mi到目标节点的耗散值）

open←add（open，mj）标记mj到n的指针（mj不在open，closed中）

iff（n,mk）

iff（n,mL）

add（mL,open）,把mL放回到open中

7Open中的节点按f值升序排列

8goloop

例八数码问题

令：

g（n）=d（n）节点深度

h（n）=w（n）不在位的数码个数（启发函数）

那么f（n）=d（n）+w（n）

如初始节点s的f值f（0）=d（0）+w（0）=0+4=4

有4个数码不在位。

对于f（n）=g（n）+h（n）,如果单独考虑g（n）或者h（n）,即，

1）f（n）=g（n）只考虑搜索过的路径已经消耗的费用；//分支界限算法

2〕f（n）=h（n）只考虑未来的开展趋势//爬山算法

那么可以得到两种特殊的算法：

爬山算法和分支界限算法。

爬山算法：

procedureHill_Climbing

1n=s2Loop:

ifgoal（n）thenexit（success）3{mi}←expangd（n）,计算每个h（mi）

nextn←h（mi）最小值的节点4ifh（n）

6goloop优点，缺点

分支界限算法f（n）=g（n）：

ProcedureBranch_Bound

1queue（s-s）,g（s）=0//queue中保存的是从s出发的路径。

2Loop：

ifqueue=0thenexit〔fail〕

3path←FIRST（queue），n←LAST（pATH）//取第一条路径，及该路径的最后节点n

4ifgoal（n）thenexit（success）

5{mj}←expand（n）,计算g（mj）=g（n,mj）

remove（s-n,queue）,add（s-mj,queue）

//删除原来的路径，添加长度加一的路径。

6queue队列中分支按g值升序排列

7GOLOOP

例以下图右八城市，城市间的耗散值已经给出，利用分支界限算法给出从S到t的最正确路径。

动态规划算法：

Proceduredynamic_Programming

1queue（s-s）,g（s）=0//queue中保存的是从s出发的路径。

2Loop：

ifqueue=0thenexit〔fail〕

3path←FIRST（queue），n←LAST（pATH）//取第一条路径，及该路径的最后节点n

4ifgoal（n）thenexit（success）

5{mj}←expand（n）,计算g（mj）=g（n,mj）

remove（s-n,queue）,add（s-mj,queue）

//删除原来的路径，添加长度加一的路径。

6仅保存queue中到达某一公共节点路径中耗散值最小的路径，余者删除；queue队列中分支按g值升序排列

7GOLOOP

讨论a动态规划与分支界限差异在于去掉公共路径的冗余局部，提高效率。

b如果问题空间是树结构，动态规划与分支界限相同。

因为对于树结构不存在到达同一节点有多重路径的情况。

C动态规划改良的代价。

比方上例中，增加一个城市。

A算法总结：

1初始状态，open=〔s〕

2正常情况下〔非成功非失败〕，取open中的第一个节点n，将n由open转移到closed。

3扩充节点n，将新节点参加到open中

4修改某些节点的路径

5open中节点按照升序排列

值得重视的一点：

A算法失败的唯一原因是open表为空

思考题：

图中：

s是起始点t是目标节点；如果存在从s到t的一条最正确路径。

而n是最正确路径上的一点。

1〕f*（s）f*（n）f*（t）的关系

2〕如果f*（s）=10,g*（n）=4问h*（n）=?

A*算法〔最正确图搜索算法〕：

A*算法定义：

对于算法A，如果有h〔n〕≤h*〔n〕,即h〔n〕以h*〔n〕为上界，那么称该算法称为A*算法。

如果令h〔n〕=0，那么满足h〔n〕≤h*〔n〕

这就是分支界限算法和动态规划算法。

再令g（n）=d（n）（d（n）是节点深度〕那么f（n）=d（n）;

A*算法就是宽度优先算法。

宽度优先算法能找到最正确解。

例：

第二章中八数码问题令h（n）=w（n）=不在位数字个数。

算法可采纳性：

给定任意图，设存在从开始节点s到目标节点t的路径。

如果算法能够结束在s到t的最正确路径上，那么称该算法是可采纳的。

A*是具有可采纳性。

定理1对于有限图，如果从s到t存在路径，那么A算法一定成功结束。

推论1.1因为A*算法是A算法的一个特例。

所以在有限图上如果如果从s到t存在路径，那么A*算法一定成功结束。

定理2对于无限图，如果存在s到t路径，那么A*算法一定成功结束。

推论2.1：

open表中任一满足f（n）≦f*（s）的节点n最终都将被A*选作扩展节点。

定理3：

如果存在节点s到目标节点t路径，那么A*算法一定能找到最正确解结束。

推论3.1：

A*选来扩展的节点都有f（n）≦f*（s）

小结1如果存在节点s到目标节点t路径，那么A*算法一定能找到最正确解结束。

2open表中所有满足f（n）≦f*（s）的节点n最终都将被A*选作扩展节点。

3A*选来扩展的节点都有f（n）≦f*（s）4f*（s）作为A*的一个衡量上限。

h函数和A*算法的关系：

本节重点来讨论h函数〔即启发信息量〕对A*算法搜索效率的影响总结。

定义：

给定两个A*算法A1和A2，都有f（n1）=g（n1）+h（n1），f（n2）=g（n2）+h（n2）如果对于所有非目标节点n，有h（n1）

讨论：

启发信息与h函数值成正比。

极端情况下，完全没有启发信息时h=0，那么此时A*算法就是宽度优先算法。

定理：

给定两个A*算法A1和A2如果A2的启发式信息比A1多，那么在任何存在节点s到目标节点t的路径上，搜索结束时，由A2扩展的每一个节点必定被A1扩展。

（A1扩展的节点多），注意搜索空间小，不代表能够找到最正确解。

当h=0时，除最下面一层节点外，所有节点都进入closed表。

求解路径如图红线所示。

当考虑到h时，被扩充的节点只有s、c、j，解路径相同

h函数单调性限制

单调性限制的作用是：

防止重复计算某些节点的f值〔主要对连通图而言〕以便减少搜索代价。

单调性定义：

给定一个启发函数h，如果对于所有节点ni和nj（nj是ni的子节点），如果满足h（ni）-h（nj）≤c（ni,nj）h（t）=0,那么称h满足单调性限制。

上式可以写成h（ni）-≤h（nj）+c（ni,nj），可以理解为三角不等式。

定理5：

如果好h（n）满足单调性限制条件，那么A*算法扩展了节点n之后，就找到了到达节点n的最正确路径，即：

如果A*选中节点n，在单调性限制条件下，有g（n）=g*（n）

A*算法例如：

迷宫问题，定迷宫图如下，找出从入口到出口的最短路径。

解1〕综合数据库定义状态集：

{〔x，y〕∣1≤x，y≤4}，其中〔x，y〕表示任意节点的坐标，所以问题表示为求解从〔1,1〕到〔4,4〕的最短路径。

2规那么集〔定义4条移动规那么〕，右移R1：

if〔x，y〕then〔x+1，y〕

左移R2：

if〔x，y〕then〔x-1，y〕

上移R3：

if〔x，y〕then〔x+1，y+1〕

下移R4：

if〔x，y〕then〔x+1，y-1〕

两种解法：

宽度优先，设定h（n）

3〕A*算法f函数定义f（n）=g（n）+h（n），设每一步的耗散值为1〔单位耗散值〕

定义：

g（n=d（n）从初始节点s到当前节点n的搜索深度。

h（n）=∣-xn