• 原创美文
  • 经典文章
  • 情感美文
  • 伤感文章
  • 散文
  • 美文随笔
  • 感人文章
  • 人生哲理
  • 学生美文
  • 民族文化
  • 说说大全
  • 网名大全
  • 范文大全
  • 当前位置: 佩佩美文网 > 感人文章 > 正文

    (人工智能)人工智能考试整理-20210511020701

    时间:2021-05-12 07:26:48来源:佩佩美文网 本文已影响 佩佩美文网手机站

    (人工智能)人工智能考试

    整理

    智能定义(知识阈值理论)智能就是在巨大的搜索空间中迅速找到一个满意解的能力 智能的综合性走义:智能是知识和智力的总和。其中知识是智能行为的基础。

    智能的特征:1)具有记忆与思维能力

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

    2 )具有飙能力:通过感官获取外部信息的能力。

    3) 具有自适应能力

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

    4) 具有表达能力

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

    深蓝:能够模拟人的思维,进行博弈的计算机。1997年5月12日,一个名为“深蓝" (deepBlue )的IBM计算机系统战胜当时的国际象棋冠军盖利?卡斯帕罗夫

    图灵测试:两个房间,—个是人,—个是机器?测试者通过一系列的提问,如果提问题的人 无法分辨是人还是机器在回答问题,则认为该机器具有智能

    人工智能(Artificallntelligence ,简称 AI)又称机智能 machineintelligence f —般认为起 源于美国1956年的一次真季讨论(达特茅斯会议)在这次会议上,第一次提出了 "Artificallntelligence"这个词。

    AI的本质问题:研究如何制造出人造的智能机器或系统,来模拟人类的智能活动的能力,以 延伸人们智能的科学。

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

    1)综合数据库(GlobeDatabase )

    也称为:事实库z上下文等。

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

    2 )规则库(RuleBase )(问题本身知识、求解知识) 也称为规则基、规则集等。

    作用:存放规则知识。

    产生式规则的一般表达形式:

    IF (前提)…THEN(结论)…

    即:如果…那么?…

    例:1)数学定理

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

    THENA是高级动物

    关于不精确推理

    当规则的前提成立时,结论并非完全成立。这种推理称为不精确惟理。通常采用阈值方法来 解决此类问题。

    (3 )控制策略(Controlstrategy )

    a选择规则库中的规则与综合数据库的已知事实进行匹配,匹配成功的规则为可用规则,否 则为不可用规则。

    b规则冲突的解决(可用规则书>11

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

    产生式系统的特点:1模式化:所有规则具有相同的形式

    2结构化:规则见的关联比较简单,容易维护。

    3自燃性:规则表达了因果关系,比较符合人们的思维方式,容易理解。

    4单一性:智能处理因果关系问题。

    5效率低?规则匹配程很大。

     产生式系统的适用范围:1)知识杂乱、事实众多、无统一理论的领域

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

    3) 该领域的知识可分解为一组独立的动作,以便用规则加以表示。

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

    产生式系统一般性算法:1DATA-初始数据库

    2untilDATA満足结束条件条件之前do :

    3Begin

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

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

    END

    例1字符转换

    问题:设字符转换规则

    Aa B—?CA 人 Cf D

    BaC^GBaE—?F

    D—E

    已知:A,B

    求:F

    —、综合数据库

    {x}:其中x为字符

    二规则集

    IFAaBTHENC

    IFAaCTHEND

    二、控制策略

    顺序排队 四、初始条件{A.B} 五、结束条件:

    ?规则集

    役:空格移动代替数吗移动。至多有四种移动的可能:上、下、左、右: 定义:塑矩阵第i行j列的数码;

    其中:i0,j0表示空格所在的位置,则%矿0 (0代表空格) 空格左移规则:

    if j0-l21 then j0 = j0-l; SiOjO = 0

    解秤:如杲当前空格不在第一列,则空格左移一位,新的空格位置賦值为0: 同理;右移规则:if VI ^3 then j0=j0+l; S1OjO=0

    上移规则:if i0-lSl then iQ=iQ-l; SiQjQ=0

    下移规则:if i0+l = 3 then iQ= iQ+l; SiOjO= 0

    (D控制策略

    需要解决的问邈:?在当前可用的规刖中如何选择其中之一来实现状态的转换

    ?实时判斷是否到达目标状态

    b图搜索万式(Graphsearch )

    丄?不可撤回方式 基本策略:选择规则时只依靠局部知识(信息).而不考虑是否全局最佳选择,只能满足局 部优化条件,用过的规则不再撤回。

    特点:

    a方法简单,容易实现

    b具有一走的局限性,适用范围小(只可用于单极值情况)

    c可能会造成规则的多次重复使用。

    比如:爬山算法’,不可用于解决多极值问题。

    关于局部知识的利用:设计局部评价函数W(n)根据W(n)最大为原则来选择规则。

    例:八数码问题

    设:?W(n):不在位的数码个数n :任意状态

    目标状态:?W(n)=O (每个数码就位)

    W(n)= 52 8 32 S 32 8 316 41 4(-3)16 47 57 6 57 5-

    W(n)= 5

    2 8 3

    2 S 3

    2 8 3

    16 4

    1 4

    (-3)

    16 4

    7 5

    7 6 5

    7 5

    -W (11)= - 5

    S 6 ―>2

    1 7

    3

    2 8 3

    1 4

    其余2种 移动(略0

    此路径(略)

    C可解决局部极值问题设计方法:

    C可解决局部极值问题

    设计方法:

    a确走合适的回溯条件

    b充分利用可用知识来排列规则,减少回溯次数

    例:丿黴码游戏(主要讨论回溯条件)回瀝条/牛:a新产生的状态已经在搜索过程中出现;b应用规则的数星已经超过规走值(深度限制)c当前状态,无可用规则满足上述条件之一则产生回溯,每次回溯一层。3 ?图搜索方式2 8

    例:丿黴码游戏(主要讨论回溯条件)

    回瀝条/牛:

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

    b应用规则的数星已经超过规走值(深度限制)

    c当前状态,无可用规则

    满足上述条件之一则产生回溯,每次回溯一层。

    3 ?图搜索方式

    2 8

    1 6

    2 8

    1 6

    7

    卩艮怎披索深度-6 列Lin扌彳F歹q次序: &移.上移、右移、

    下移

    可用规则;上、右

    深度=4

    可用现则:左?右?下

    深度=5

    止匕4疋态与

    滓度=3的

    I狀态相同.

    ,笨=6

    左J "

    8 3

    2 0 4

    17 5

    8 3

    2 6 4

    17 5

    -与滓度=?

    习疋态才目同

    I且滓度=6

    )不可撤回方式:沿 Y路径单向延伸搜索

    2)回溯方式:可修正搜索路径

    3 )图搜索方式:展开式搜索,可保留完整的搜索树。

    产生式系统分类

    1?一般性产生式系统

    根据规则的应用方式,一般性产生式系统可以分为三种类型:

    1)正向系统(数据驱动)

    采用正向推理方式,即由初始状态推理到目标状态,正向系统里的规则是正向使用的:规则的 前提成立,那么规则的结论成立。

    2) 反向系统(目标驱动系统)

    采用反向推理方式:即由目标状态反向推理找到初始状态。反向系统的规则是反向使用的: 先假设规则的结论成立,在寻找使其成立的前提条件。

    3) 双向系统

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

    例:数学证明思路

    ?可交换产生式系统

    定义:满足下列性质的产生式系统称为可交换产生式系统

    a给走可以用于数据库D的规则集R ,对于使用R中的任何规则后产生的任何 集R仍然可用。(规则适用性)

    b如果目标条件被D满足,则应用R中的任何规则于D上所产生的任何嫌库仍可满足目

    标条件。(数据库可用性)

    c应用R

    c应用R中一个规则序列于D上后.得到的娄

    库不随这规则序列次序变化而变化。(规则

    次序无关性)

    ?可分解产生式系统 定义:任何待求解的数据库都可以分解为若干个独立处理分呈的产生式系统称为可分解产生 式系统。

    求解方法:将初始数据库分解为几个可独立处理的分呈,用规则分别求解,生成新的数据库, 再分解,再求解z知道结束。

    可分解产生式系统的一般性算法:AND节点层OR节点层状态空间图

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

    AND节点层

    OR节点层

    状态空间图

    AI领域的知识分类

    a陈述性知识:用于描述综合数据库的状态。(如事实等)

    b过程性知识:用于规则中表达问题的知识.(如客观规律等)

    c控制性知识:用于构駆制策略的知识(算法、数据结构等)

    AI系统的一个难题:知识表达问题,要能够客观的描述现实,简化求解过程,有效的提高求 解效率,降低求解代价。

    产生式系统的搜索策略

    艸太凸向? cb冷片=i"刁西亦右冇T彌<1叶太细 比抽知刁(妒|出zpG隹 a \

    分解 求解 分解 求解

    初始数锯库 A分量集 A祈数锯库 A… —目标

    搜索策略的基本思路:搜索空间必须包含解路径,如果问题有解,且尽呈缩小搜索空间。

    捜索策略的评价准则:总体费用最低

    费用的划分:a规则应用的费用:执行规则时所花的费用b控制费用:选择规则所花的费用。

    ?回溯策略

    ?图搜索策略

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

    6 ) h函数与A啲关系7 )关于单调性限制8 ) A★算法示例

    例四皇后问题

    四皇后问題旦删算法披索图

    说明: ① 红色箭头是鼠终的辭略径、?其余珞径全部产生包滋

    ②当前可用规则时月非列次序为自然和岸序. 如:Rir.

    图搜索的结果:「一个完整的搜索图G。2 —个解路径,用指针表示的解路径。

    ProcedureGraphSearch

    lG=G0(G0=s),open=(s)//s:初始状态

    2closed=()

    3Loop:ifopen=()thenexit(fall)

    4nMirst(open)remove(nropen)radd(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表中的节点r goloop

    深度优先算法

    Procedruedepth ?First?Search

    lG=G0(G0=s),open=⑸.closed=0//s:初始状态

    2Loop:ifopen=()thenexit(fall)

    3n—first(open)

    4ifgoal(n)thenexit(success)

    5remove(nQpen).add(n,closed)

    6{mj}^expand(n)y/mj不含n的先辈节点

    7open^add(open f mj)//mj 不在 open , closed 中

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

    8goloop

    讨论1:如果问题有解,有深度优先搜索算法,是否能够找到解?

    不一定?解空间是否有限?

    讨论2 :本算法的改逬之处是open中节点按照深度优先排列,但是没有对深度加以控制,

    可能造成搜索代价太大

    A C

    B t

    初始状态

    AR曰标状态3nWirst(open)

    A

    R

    曰标状态

    4ifgoal(n)thenexit(success)

    5remove(n,openLadd(n,closed)

    6{mj}^expand(n),//mj不含n的先辈节点

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

    8goloop

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

    讨论:竞度优先算法和深度优先算法可能出现组合爆炸。都没有利用任何启发式信息,所以

    称为无信息搜索策略pen—add(open , mj)//mj不在open , closed中

    宽度优先例题:

    由_张桌子T、三个积木A、B、C组成一个积木世界,初始状态是A在B上,B在桌子上,

    C在桌子上;目标状态是:A、B、C依次从上至IJT排列在桌子上。如图

    解:1)状态描述(Pl , P2 , P3 )表示按A、B、C顺序依次分别在P1T2.P3上其中Pi是

    积木或者桌子。初始状态时(B、T、T),目标状态可以表示(B、C、T)

    2 )定义操作:move(x,y)表示将积木x移到Y上;

    约束条件:aX顶部必须是空的b如果Y是积木,Y的顶部必须是空c同一种状态出现不得多 -次.

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

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

    4)程序何时结束5)改用深度优先如何?

    启发式图搜索策略:基本概念

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

    找到

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

    评价函数的目的:把最有希望得到最佳解或者解的排列在前面。

    路径:给定节点序列(nO , nl , ...nk \如果该序列中的任一节点ni-1都有后继节点ni f则

    该节点序列为从nO到nk的一条路径,路径长度为K

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

    设:路径山任两点间的耗散值为才C(ni,nj)f则从ni到nk的路径耗散值为

    C(ni,nj)=C(ni/nj)+C(njfnk)

    最佳踣径耗散值:最佳路径上的实际耗散值r记为:K(nirnj).

    K(ntnj)<=C(nLnj)

    定义几个函数

    gXn)=k(s,n):从初始节点s到当前节点n的最佳路径的耗散值。

    h*(n)=k(n,t):M当前节点n到目标节点t的最佳路径的好三者。

    3)f?)=gF)+hrn):从初始节点s通过当前节点n到目标节点t的最佳I洛径的耗散值。

    4)评价函数:f(n)=g(n)+h(n)具中f, gzh分别是f*, g* f h啲估计值。

    (圧 UQdo 出 C 尿亠 E 尽嵯殳UTU)JJ(>llu=UQ£(>ILUvaLUs主 (甘 p ① sop - u ① do T)^Mfsu 丽旧1^(T、uodo)ppe!uedo (a鈕區gKIJtp眶皿丽至、u 昴s 皿raoJN+alusfalusJm+I

    淫护3卅gU 如K-T、、(u)puedxQ!=lu)9 (P① SOPSPPAU ① dQu)① >OLU ①」s (SS①yns)七x①u①ql(u)-eo6七寸 oq(u ① do)ls」亍 Um (=ej)七 x①UQsru ① do 七0.0010 检奖翟<、(s)q+(s)6=(s=? OHP ① SOSSTU ① do、(SH0D)0DHDT “ ?#< i (cn。館旺tBsp

    ?燎噩(u)ph(u)6 -

    副叵国載<事 doo-068

    Is— - U①do" fl-u ① do0H回罡」lu af(uedo_JUJ)ppe ?p ① sop 田 ^EEl U 丽n3^(」cuc)Jl(-IE=UQ£(」lu)v(-luru)±

    2 ) f(n)=h(n)只考虑未来的发展趋势〃爬山算法

    那么可以得到两种特殊的算法:爬山算法和分支界限算法。

    爬山算法:procedureHill_Climbing

    ln=s2Loop:ifgoal(n)thenexit(success)3{mi}—expangd(n),计算每个 h(mi) nextn^-h(mi)最小值的节点 4ifh(n)vh(nextn)thenexit(fail)5n—nextn 6goloop优点,缺点

    分支界限算法 f(n) = g(n) : ProcedureBranch_Bound

    lqueue(s-s)rg⑸=0//queue中保存的是从s出发的路径。

    2Loop : ifqueue=Othenexit (fail)

    3path-FIRST(queue)小-LAST(pATH)//取第一^蹿圣,及该路径的歸节点n

    4ifgoal(n)thenexit(success)

    5{mj}—expand(n),计算 g(mj)=g(nfmj)

    rennove(s?n,queiie),add(s-mj,queue)

    〃删除原来的路径,添加长度力n-的路径。

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

    7GOLOOP

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

    动态规划算法:Proceduredynamic_Programming

    lqueue(s-s)rg⑸=0〃queue中保存的是从s出发的路径。

    2Loop : ifqueue=Othenexit (fail)

    3path-FIRST(queue), n一1_人5丁9人叩)//取第一^路径,及该路径的最后节点n 4ifgoal(n)thenexit(success)

    匚 r;、厶—八■夕\ ,4-隹3" ^9 trvx a\ _ / rvx a\

    a—15

    动态观戈勺原理的找索EB

    有多重路径的情况。

    C动态规划改进的代价.比如上例中,增加一个城市。

    A算法总结:1初始状态f open= ( s )

    2正常情况下(非成功非失败)f取open中的第一^节点n ,将n由open转移到closedo

    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 )( n ),即h ( n )以n )为上界,则称该算法称为A★算

    法。

    如果令h ( n ) =0 ,则满足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存在路径f则

    A★算去一走结束。

    定理2对于无限图.如果存在s到t路径.则A★算法一定成功结束。

    推论2.1: open表中任一满足f(n)^(s)的节点n最终都将被A★选作扩展节点。

    定連3 :如果存在节点s到目标节点t路径■则A★算法一走瞬至憬佳解结束。

    推论3.1: A★选来扩展的节点都有f(n)纹⑸

    小结1如果存在节点s到目标节点t路径,则A煩法一走能找到最佳解结束。

    2open表中所有满足f(n)纹(s)的节点n最终都将A★选作扩展节点.

    3A★选来扩展的节点都有f(n)0f(s)4frs)作为A啲一个衡呈上限。

    h函数和¥算法的关系:本节重点来讨论h函数(即启发信息量)对A*W法搜索效率的影 晌总结。

    定义:给定两个A★算法A1和A2 ,都有f(nl)=g(nl)+h(nl) .f(n2)=g(n2)+h(n2)如果对于

    所有非目标节点n ,有h(nl)

     讨论:启发信息与h国数值成正比。极端情况下,完全没有启发信息时h=0,则此时/V算 法就是竞度优先算法。

    定理:给定两个A★算法A1和A2如果A2的启发式信息比A1多,则在任何存在节点s到 目标节点t的路径上,搜索结束时,由A2扩展的每一个节点必定被A1扩展。(A1扩展的节 点多),注意搜索空间小?不代表能够找到最佳解。

    当h=0时,除最下面一层节点外,所有节点都逬入closed表。求解路径如图红线所示。

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

    h函数单调性限制

    单调性限制的作用是:避免重复计算某些节点的f值(主要对连通图而言)以便减少搜索代 价。

    单调性定义:给走一个启发函数h f如果对于所有节点ni和nj(nj是ni的子节点)f如果满 足 h(ni)-h(nj)

    上式可以写成h(ni)-

    定連5 :如果好h(n)满足单调性限制条件,则/V算法扩展了节点n之后,就找到了到达节 点n的最佳路径,即:如果/V选中节点n ,在单调性限制条件下.有g(n)=g*(n)

    A六算法示例:迷宫问题.定迷宫图如下,找出从入口到岀口的最短路径。

    解1)综合数据库定义状态集:{(x,y) |l

    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)

    ) A★算法f因数走义f(n)=g(n)+h(n),设每一步的耗散值为1 (单位耗散值)

    定义:g(n=d(n)从初始节点s到当前节点n的搜索深度。h(n)= |-xn| + |-yn|

    其中是(xg , yg )目标节点的坐标r ( xn r yn )是当前节点的坐杭 显然满足:h(n)

    ) Open表节点排序,先按f值排序,如果f值相同,则深度优先,

    关于f函数值的意义的讨论:为了调整g和h在h中的作用比例f设f=g+Mh

    1)令w=0则f=g ,此时,A★成为竞度优先算法。特点:可扩大搜索范围便于找到最佳解, 但是费用比较大。

    2 )令w为一个大的整数,则加大了 h在f函数中的作用力度。其意义在于:不考虑到目前 已经消耗的费用,只关心当前节点到目标节点剩余的搜索工作呈。

    本章算法汇总1 ?回溯策略2 ?图搜索策略

    A 算法:(n)=g(n)+h(n)l.当 h(n)=0g(n)=-d(n)深度优先 2.当 g(n)=0 爬山算法

    3?当h(n)=0分支界限算法各分支只保留一个动态规划算去4,h(n)=0g(n)=d(n)^度优先算

    A★算法:分支界限算法动态规划算法竞度优先算法

    本章例题汇总1?四皇后问题回溯策略2积木世界问题宽度优先

    3八数码问题A算法4八城市s-t分支界限算法。5迷宫问题A★算法

    命题逻辑

    主要内容1)命题的表示、命题的演算2 )命题演算中的公式及其应用3 )命题逻辑推理 命题是—个能确走真的或假的的判断。

    补充二谓词逻

    2-4赣范式

    感谢阅读

    • (人工智能)人工智能考试整理-20210511020701 相关文章: