无信息搜索
宽度优先算法
按层次逐层遍历图或者树，直到遇到目标节点，采用FIFO队列，空间复杂度bm，时间复杂度bm（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
排名
密度估计
优化
学习范式
有监督学习，无监督学习，强化学习
学习模型
几何模型，逻辑模型，网络模型，概率模型
网友评论