论人工智能

无信息搜索

宽度优先算法

按层次逐层遍历图或者树，直到遇到目标节点，采用FIFO队列，空间复杂度b^{m，时间复杂度b}m（b为分支数，m为深度）

深度优先算法

按深度优先，遍历图或者树，直到遇到目标节点，采用栈，空间复杂度b*m，空间复杂度为m

深度受限搜索

如果某些问题，深度是无限的，则深度优先算法就会发生无限循环而导致搜索失败，可以对深度m设定m<d，对超过d深度的节点不进行搜索，当然，此策略有可能导致无解或者出现非最优解

以上两种算法，时间复杂度和空间复杂度随着深度的增加，呈现指数性的增长，所以必须采取更优的算法来进行搜索

一致代价搜索

采用优先队列管理待遍历的节点，取目前代价最小的节点进行扩展，直到遇到目标节点

双向搜索

对于初始状态和目标状态，启动两个搜索，一个从初始状态出发，一个从目标状态出发，当两者相遇时，则得到解

启发式搜索/有信息搜索

此策略通过对问题的特有信息进行扩展，而采用更有效的策略进行扩展节点的选择，因此能够找到比无信息搜索更有效的解，时间复杂度和空间复杂度都会减少许多

一般使用通过定义以下两个函数对问题进行知识提取

• 评价函数f(n)，用于选择一个节点进行扩展
• 启发式函数h(n)，作为f的一个组成部分

最佳优先搜索

一致性代价搜索只有f(n)，代表从初始状态出发，到当前节点的总代价，然后通过优先队列进行排序，获取代价最小的节点进行扩展。

最佳优先所有采用与一致性代价搜索同样的算法，但是在计算f(n)的时候，加入h(n)的额外信息，进行问题更有效的搜索

h(n)：从当前状态到目标节点的代价估计

贪婪搜索

f(n) = h(n)，

对每个状态进行h(n)的估计，计算出每个节点到达最终状态的代价估计，并进行排序，每次进行节点扩展时，只选取跟目标节点最靠近的节点进行扩展

例如在求解最短路径时的过程如下

ai-greedy

它的解有可能不是最优解

最坏的时间复杂度为b^m

空间复杂度为b*m

A*搜索

对贪婪算法进行优化加入g(n)函数

g(n)：从初始状态到当前节点的总代价

f(n) = g(n) + h(n)

可以得到最优解

解8数码问题

ai-8puzzle

h(n)的确定

• h1(n) = 错子数
• h2(n) = 每个棋子到目标状态的曼哈顿距离之和

ai-manhattan

超越经典搜索

对于以上两节有以下特征，并可以得到一系列路径构成一个解

• 可观察
• 确定性
• 已知环境

但是对于NP的很多问题，都不具备这些条件，而且对于到达目标的路径并不关心，需要通过局部搜索来进行求解

局部搜索

它是一种不介意路径的算法，使用一个当前节点，并通常仅移动该节点到相邻节点，把当前状态变成一个更优的状态，通常搜索后不保留该路径，它非常适用于许多优化算法

优点

• 使用内存少
• 在很大或无限状态空间中，能发现合理解

爬山法

通过设定一个评价函数e(n)，通过转换当前状态，得到一系列的下一状态，并取e(n)最好的一个状态为下一状态。评价函数是一个对当前状态优劣的一种判断

例如在解决n皇后问题

e(n)：皇后之间的冲突数之和

ai-8quenue-climb

缺点

• 容易达到局部最大值
• 容易停留在高原
• 在山岭的情况下难以爬行

针对以上问题，有以下爬山法的变形

随机爬山法

在向上移动的过程中，随机的选择下一步，选择的概率随向上移动的斜率而变化，与最斗爬山法相比，收敛速度会变慢

首选爬山法

通过随机生成后继节点，直到生成一个比当前状态好的点。对于某个状态有许多后继时，用此策略好

随机重启爬山法

通过随机生成多个初始状态，然后各自进行爬山，获取最佳的那个目标状态

局部束搜索

相对于局部搜索只保留一个当前状态，局部束搜索通过保留k个状态进行搜索，可以增大到达目标的概率

例如在解决旅行商问题，选择k=2

ai-tsp-multik

• 随机生成k个初始状态
• 计算初始状态的所有后继状态
• 通过评价函数e(n)和优先队列，获取最优的k个状态进行下一次迭代，直到遇到解

变形

随机束搜索

通过概率随机选择k个后继节点，选择节点的概率与e(n)成正比关系

模拟退火算法

在迭代的开始，状态具有大的随机性选择下一个状态，当随着迭代的增加，模拟温度的冷却，状态的选择随机性不断降低，最终达到一个稳定的状态

过程

• 随机生成初始状态
• 随机生成相邻状态
• 随机选择一个相邻节点是否大于当前节点的e(n)
• 如果评价更高，则选择为下一节点，否则生成概率p，如果p在当前迭代的概率内，则选择此更坏的节点为下一个节点，否则进行下一个相邻节点的比较
• 如果选择节点的e达到要求或者迭代进行到一定深度，则返回解

遗传算法

模拟生命的进化过程生成优化问题的解

• 开始时生成k个随机状态，称为种群
• 对种群进行e(n)评价，并进行选择
• 种群内两两杂交，并遗传产生后代
• 后代在一定概率内对其中的某个基因进行突变
• 不断迭代上述过程，并最终产生一个较优解

例如8皇后问题

ai-8quenue-inhre

蚁群优化

pending

鸟群优化

pending

对抗搜索

搜索	对抗搜索
通过寻找目标的启发式方法	对对手可能的回应而行动的策略
启发式可以找到最优解	时间受限只能找到近似解
以当前节点和目标节点的距离作为评价函数	以局势的好坏作为评价函数
单智能体	多智能体

Minmax策略

Max君先行，Min君后手，Min君企图让Max君的收益最小化，Max君企图让自己的收益最大化，那么就有了下图

ai-minmax

此搜索为深度优先算法，先遍历叶子节点，向上递归，直到到达当前节点，时间复杂度为b^m，空间复杂度为m

多人博弈

在不考虑联盟等关系时有下图

ai-minmax-multi

Alpha-beta减枝

在MinMax策略中，需要遍历整棵树的所有节点，才能得出当前节点的下一步的策略，但其实在很多情况下，并没有必要去遍历每个节点，例如在得到一个子树的min为m，那么在另一个子树搜索时发现有比m更小的值，则可以直接放弃改子树的遍历，如下图

ai-alpha-beta

图中的x,y是可以直接放弃的节点

非完美实时决策

即使alpha-beta已经对算法做出了优化，但是为了达到实时决策，在必须遍历一个树的深度时，也是不能忍受的，因此在决策时，可以通过e评价函数，判断下一步的局势，来决定最佳的移动

例如对于象棋，通过下一步走子，通过对每个棋子的加权和来作为评价函数

随机博弈

通过在Minmax中加入随机概率的节点，可以让Minmax策略应用于随机博弈，例如扑克

ai-minmax-stochastic

蒙特卡罗树搜索

alphago-tree

由于在非常多的对抗搜索中，并不能在固定时间内穷尽所有可能，或者状态集是无穷的，此时可以通过蒙特卡洛模拟，然后通过最终模拟结果的反馈进行树的局部更新，随着游戏的进行，树对每个节点的估计从粗略慢慢向准确靠近

CSP约束满足问题

CSP: Constraint Satisfaction Problem

CSP问题在每个状态间建立了约束条件，导致原来的搜索难度大大增大，需要用到启发式和组合搜索结合来寻找最优解

例子：

• 8皇后问题
• 地图着色问题
• 数独

约束传播

• 节点一致性

  例如在地图着色问题，SA不能为green

• 弧一致性

  例如SA的颜色不能等于AU的颜色

• 路径一致性

  例如如果SA为green，AU为red，那么MM必须为blue

• k一致性

  推广到k个节点的关系

回溯策略

通过对当前节点的所有可能进行深度遍历，一旦发现破坏了约束，则放弃测移动，而进行下一个可能的深度遍历

ai-backtrace-4quene

优化回溯

• 通过对所有当前节点的合法值进行排序，选择最少合法值得变量进行优先遍历
• 通过选择在确定某个节点后，产生对相邻节点排除最多可能得选择，为变量进行遍历

局部搜索

通过定义e函数，使用爬山法，进行局部搜索

推理系统

贝叶斯网络

P(case|effect) = P(effect|case)*P(cause)/P(effect)

物理意义：很多情况下，我们很容易从数据中得到从原因到结果得所有概率，但是我们很多时候得推断都是先知道结果，来反推是什么原因导致这样得结果

例如

ai-bayes

机器学习

人类学习VS机器学习

ai-ml

归纳学习VS演绎学习

ai-learningtype

三大学派

联结主义

亦称仿生主义/生理学派。例如感知机，神经网络和深度学习

符号主义

亦称逻辑主义，心理学派，计算机主义，例如关联规则，决策树和随机森林

行为主义

亦称进化主义，控制论学派。例如强化学习

三大视角

任务

分类

ai-classify

回归

ai-regression

聚类

基于连接性聚类

对象与其附近的对象更相关

ai-cluster-agnes

基于中心点聚类

ai-cluster-k

基于分布聚类

ai-cluster-static

基于密度聚类

ai-cluster-midu

降维

线性降维

PCA

ai-pca

非线性降维

isomap/lle/KFD/MDS

排名

密度估计

优化

学习范式

有监督学习，无监督学习，强化学习

学习模型

几何模型，逻辑模型，网络模型，概率模型