2021SPR《人工智能》课程复习笔记

内容纲要

第一章 总论

现代人工智能(Artificial Intelligence,简称AI),一般认为起源于美国1956年的一次夏季讨论(达特茅斯会议),在这次会议上,第一次提出了“Artificial Intelligence”这个词。

AI是一门新兴的边缘学科,是自然科学与社会科学的交叉学科。
AI的交叉包括:逻辑、思维、生理、心理、计算机、电子、语言、自动化、光、声等。
AI的核心是思维与智能,构成了自己独特的学科体系。
AI的基础学科包括:数学(离散、模糊)、思维科学(认知心理、逻辑思维学、形象思维学)和计算机(硬件、软件)等。

第二章 一般图搜索

图搜索是搜索过程可以用图结构的形式呈现的一类搜索算法。图可以更加形象与清晰地描述搜索过程。

扩展节点

生成某一节点的所有后继节点,并给出他们之间的耗散值。

图搜索要素

问题状态:问题求解过程中的一个状态,对应于图G_i=(E,V)
初始状态:问题求解之前的状态,对应于图G_0=(E,V)=S
目标状态:包含求解目标的状态,对应于图G_n=(E,v)=T
问题的解:从TS的反推
状态空间:问题求解过程中所有可能状态的集合

图搜索基本思想

  • 从给定的初始节点出发
  • 迭代地选择节点扩展,得到新的状态
  • 扩展到目标状态停止,或者没有节点可扩展为止
  • 从目标状态反推到初始节点,得到问题的解

需要使用的数据结构

OPEN表:存储还未扩展的节点
CLOSED表:存储已经扩展过的节点
状态图G:已扩展出的节点呈现出的状态

补充说明

一般图搜索是一类无信息搜索,盲目扩展所有节点,与问题本身无关。
一般图搜索算法是很多算法的基础,通常通过在搜索前:

  • 根据条件降低搜索规模
  • 根据问题的约束条件进行剪枝
  • 利用搜索过程中的中间解,避免重复计算
  • 利用问题启发式信息,减少搜索空间

第三章 启发式搜索

利用启发式信息引导算法搜索,达到减少搜索范围,降低问题复杂度的目的。

启发信息的使用

强:降低搜索工作量,但可能导致找不到最优解
弱:导致工作量加大,极限情况下变盲目搜索,但可能可以找到最优解
关键点:如何利用启发式信息,尽可能有效地找到问题的近似最优解
人:有关问题的求解经验+算法设计

启发式图搜索基本思想

基于一般图搜索算法,定义一个评价函数f,对当前的搜索状态进行评估,从Open表中找出一个最有希望的节点来扩展。

评价函数

f^*(n) = g^*(n) + h^*(n)
g^*(n) 从根节点到当前节点的最短路径长
h^*(n) 从当前节点到目标节点的最短路径长

因为在运行中,我们无法得知真正的最短路径,所以采用估计值来代替。

爬山法

只考虑与目标之间的差距,即g(n) = 0

最佳图搜索A*算法

如果在上述算法中,恒有h(n) \leqslant h^*(n),那么算法变为A*算法。
在A*算法运行过程中,有:
f^*(S) = f^*(T) = h^*(S) = g^*(T) = f^*(n)
其中n是最佳路径S→T上的节点。

A*定理和推论

定理1:对于有限图,A*算法一定终止。
算法每次循环从OPEN表里去掉一个节点,而有限图的OPEN表内只有有限个节点加入。所以无论算法是否找到解都会正常停止。
定理2:若算法不终止,则OPEN表上的点的f值将越来越大。
定理3:A*结束前,Open表中必存在f(n)≤f^*(S)
定理4:若问题有解,算法终止时一定找到最优解,即可纳。
定理5:OPEN表上任一具有f(n)≤f^*(s)的节点n,最终都将被算法选作扩展的节点。
定理6:A*选作扩展的任一节点n,有f(n)≤f^*(s)
定理7:设对同一个问题定义了两个A*算法A1和A2,若A2比A1有较多的启发信息,即对所有非目标节点有h_2(n) > h_1(n),则在具有一条从s到t的路径的隐含图上,搜索结束时,由A2所扩展的每一个节点,也必定由A1所扩展,即A1扩展的节点数至少和A2一样多。

算法改进

因A算法第6步对m_1类节点可能要重新放回到OPEN表中,因此可能会导致多次重复扩展同一个节点,导致搜索效率下降。

解决的途径:

  • 对h加以限制:对h增加适当的限制,使得第一次扩展一个节点时,就找到了从S到该节点的最短路径。
  • 对算法加以改进:对算法加以改进,避免或减少节点的多次扩展。

改进的条件:

  • 可采纳性不变
  • 不多扩展节点
  • 不增加算法的复杂性

算法描述

* 初始化open_set和close_set;
* 将起点加入open_set中,并设置优先级为0(优先级最高);
* 如果open_set不为空,则从open_set中选取优先级最高的节点n:
    * 如果节点n为终点,则:
        * 从终点开始逐步追踪parent节点,一直达到起点;
        * 返回找到的结果路径,算法结束;
    * 如果节点n不是终点,则:
        * 将节点n从open_set中删除,并加入close_set中;
        * 遍历节点n所有的邻近节点:
            * 如果邻近节点m在close_set中,则:
                * 跳过,选取下一个邻近节点
            * 如果邻近节点m也不在open_set中,则:
                * 设置节点m的parent为节点n
                * 计算节点m的优先级
                * 将节点m加入open_set中

与或图搜索

超图:定义它的边(这里叫超边,hyperedge)可以和任意个数的顶点连接。
k-均匀超图:超图的每个边连接的顶点个数都是相同的,即为个数k。
能解节点

  • 终节点是能解节点
  • 若非终节点有“或”子节点时,当且仅当其子节点至少有一能解时,该非终节点才能解
  • 若非终节点有“与”子节点时,当且仅当其子节点均能解时,该非终节点才能解

不能解节点

  • 没有后裔的非终节点是不能解节点。
  • 若非终节点有“或”子节点,当且仅当所有子节点均不能解时,该非终节点才不能解
  • 若非终节点有“与”子节点时,当至少有一个子节点不能解时,该非终节点才不能解

第四章 不确定性搜索

局部搜索算法

通常考察一个算法的性能通常用局部搜索能力全局收敛能力这两个指标。局部搜索是指能够无穷接近最优解的能力,而全局收敛能力是指找到全局最优解所在大致位置的能力。
局部搜索是解决最优化问题的一种启发式算法。对于某些计算起来非常复杂的最优化问题,比如各种NP完全问题,要找到最优解需要的时间随问题规模呈指数增长,因此诞生了各种启发式算法来退而求其次寻找次优解,是一种近似算法(Approximate algorithms),以时间换精度的思想。局部搜索就是其中的一种方法。

伪代码描述

LOCAL-SEARCH
    随机选择一个可能的初始解x
    扩展x的邻域P(x)
    如果满足结束条件,停止循环:
        选择P(x)中的一个子集P'(x)
        评估其中的最优解y
        如果f(x)>f(y)
            x := y
            P(x) := P(y)
        否则
            P(x) := P(x) - P'(x)
    输出结果

存在的问题和改进

陷入局部最优而非全局最优
  • 每次并不一定选择邻域内最优的点,而是依据一定的概率,从邻域内选择一个点,指标函数优的点,被选中的概率比较大,而指标函数差的点,被选中的概率比较小。
  • 变更步长
  • 随机生成初始点,取最佳

第五章 博弈搜索

博弈问题的基本假设:

  • 两个棋手交替地走棋
  • 比赛的最终结果,是赢、输和平局中的一种
  • 可用图搜索技术进行,但效率很低
  • 博弈的过程,是寻找置对手于必败态的过程
  • 双方都无法干预对方的选择

基本思想:

  • 下棋的双方是对立的
  • 一方为“正方”,这类节点称为“MAX”节点
  • 另一方为“反方”,这类节点称为“MIN”节点
  • 正方从所有子节点中,选取具有最大评估值的节点
  • 反方从其所有子节点中,选取具有最小评估值的节点
  • 反复进行这种选取,就可以得到双方各个节点的评估值。这种确定棋步的方法,称为极小极大搜索法。

对各个局面进行评估
评估的目的:对后面的状态提前进行考虑,并且以各种状态的评估值为基础作出最好的走棋选择。
评估的方法:用评价函数对棋局进行评估。赢的评估值设为+∞,输的评估值设为-∞,平局的评估值设为0。
评估的标准:由于下棋的双方是对立的,只能选择其中一方为评估的标准方。

a-b剪枝法

MAX节点的评估下限值a
作为正方出现的MAX节点,当它的第一个MIN子节点的评估值为a时,对于其它的子节点,如果有高过a的,就取那最高的值作为该MAX节点的评估值;如果没有,则该MAX节点的评估值为a。

MIN节点的评估上限值b
作为反方出现的MIN节点,当它的第一个MAX子节点的评估值为b时,则对于其它子节点,如果有低于b的,就取那个低于的值作为该MIN节点的评估值;如果没有,则该MIN节点的评估值取b。

a剪支法
设MAX节点的下限为a,则其所有的MIN子节点中,其评估值的a上限小于等于a的节点,其以下部分的搜索都可以停止了,即对这部分节点进行了a剪支。

b剪支法
设MIN节点的上限为b,则其所有的MAX子节点中,其评估值的b下限大于等于b的节点,其以下部分的搜索都可以停止了,即对这部分节点进行了b剪支。

蒙特卡洛树搜索

根据模拟的输出结果,按照节点构造树。每个节点必须包含两个重要信息:

  • 根据模拟结果估计的值
  • 该节点被访问的次数

第六章 约束满足问题

地图着色问题

地图着色是指分配地图的每一个面一种颜色,使得相邻的面(指有公共边界边)具有不同的颜色。

定义

  • 考虑图形中全部节点(N个)
  • 变量取值范围集合S
  • S中的元素赋值给V_i \in {V}
  • 约束:如果E(i,j)存在,那么V_i \neq V_j

特点:没有优化目标

一般图搜索策略

留下评论