人工智能导论学习笔记

课程是CS188伯克利大学人工智能导论
参考文献：

部分截图来自学校老师的教学PPT

https://zhuanlan.zhihu.com/p/61895500

https://zhuanlan.zhihu.com/p/64368643

https://zhuanlan.zhihu.com/p/148256240

https://zhuanlan.zhihu.com/p/272652797

https://blog.csdn.net/qq_45902301/article/details/125055544

https://blog.csdn.net/wangyong1034/article/details/105017736

https://blog.csdn.net/xing565244161/article/details/47253211

一、State Spaces and Search Problems 状态空间和搜索问题

为了创建一个理性计划agent，我们需要一种方法来对agent存在的环境进行数学表达。为此，我们必须正式表达一个搜索问题（search problem） ——给定agent的当前状态（state） （它在环境中的配置），我们如何尽可能最好地达到一个满足目标的新状态？讲一个问题公式化需要四个前提：

状态空间state space ：在给定世界中所有可能的状态
后继函数successor function ：包含一个状态和一个操作，并计算执行该操作的代价（cost） 和执行操作后世界的后继状态
起始状态start state ：agent最初存在时当前世界的状态
目标测试函数goal test ：一个函数，输入一个状态并决定它是否是一个目标状态

搜索问题

状态空间的大小

状态空间的定义

以下截图不完整，想看完整版的去看参考文献。

二、深度优先搜索（DFS）

完备（整）性、最优性、时间复杂度

若走到叶子节点，便会退回上一节点，遍历上一节点的其他相邻节点(2 ->3-> 4)。

这样一直重复，直到找到最终目标节点。

如你所见到的一样，这样的搜索方法像一根贪婪的蚯蚓，喜欢往深的地方钻，所以就自然而然的叫做深度优先算法了。

三、广度（宽度）优先搜索（BFS）

对于深度优先算法，强迫症就很不爽了，并表示：“为什么不干干净净，一层一层地从start节点搜索下去呢，就像病毒感染一样，这样才像正常的搜索的样子嘛！”于是便有了BFS算法。广度优先算法便如其名字，它是以广度为优先的，一层一层搜索下去的。

BFS总是先访问完同一层的结点，然后才继续访问下一层结点，它最有用的性质是可以遍历一次就生成中心结点到所遍历结点的最短路径，这一点在求无权图的最短路径时非常有用。

还是以图的方式来演示，下图中start为搜索的初始节点，end为目标节点:

我们先把start节点的相关节点遍历一次

接下来把第一步遍历过的节点当成start节点，重复第一步

一直重复一二步，这样便是一个放射样式的搜索方法，直到找到end节点

可以看出，这样放射性的寻找方式，能找到从start到end的最短路径(因为每次只走一步，且把所有的可能都走了，谁先到end说明这就是最短路)。

从实现的角度上，在广度优先遍历的过程中，我们需要用到队列：

1. 首先扩展最浅的节点

2. 将后继节点放入队列的末尾(FIFO)

BFS是从根节点(起始节点)开始，按层进行搜索，也就是按层来扩展节点。所谓按层扩展，就是前一层的节点扩展完毕后才进行下一层节点的扩展，直到得到目标节点为止。

四、一致代价搜索（UCS）

以下练习作为延伸理解

输入初始城市
Arad
输入目的城市
Bucharest
处理城市节点:Arad	父节点:None	路径损失为:0
	孩子节点:Zerind 路径损失为:75
		 添加孩子到优先队列
	孩子节点:Sibiu 路径损失为:140
		 添加孩子到优先队列
	孩子节点:Timisoara 路径损失为:118
		 添加孩子到优先队列
处理城市节点:Zerind	父节点:Arad	路径损失为:75
	孩子节点:Oradea 路径损失为:146
		 添加孩子到优先队列
	孩子节点:Arad 路径损失为:150
处理城市节点:Timisoara	父节点:Arad	路径损失为:118
	孩子节点:Arad 路径损失为:236
	孩子节点:Lugoj 路径损失为:229
		 添加孩子到优先队列
处理城市节点:Sibiu	父节点:Arad	路径损失为:140
	孩子节点:Oradea 路径损失为:291
	孩子节点:Arad 路径损失为:280
	孩子节点:Fagaras 路径损失为:239
		 添加孩子到优先队列
	孩子节点:Rimnicu Vilcea 路径损失为:220
		 添加孩子到优先队列
处理城市节点:Oradea	父节点:Zerind	路径损失为:146
	孩子节点:Zerind 路径损失为:217
	孩子节点:Sibiu 路径损失为:297
处理城市节点:Rimnicu Vilcea	父节点:Sibiu	路径损失为:220
	孩子节点:Sibiu 路径损失为:300
	孩子节点:Craiova 路径损失为:366
		 添加孩子到优先队列
	孩子节点:Pitesti 路径损失为:317
		 添加孩子到优先队列
处理城市节点:Lugoj	父节点:Timisoara	路径损失为:229
	孩子节点:Timisoara 路径损失为:340
	孩子节点:Mehadia 路径损失为:299
		 添加孩子到优先队列
处理城市节点:Fagaras	父节点:Sibiu	路径损失为:239
	孩子节点:Sibiu 路径损失为:338
	孩子节点:Bucharest 路径损失为:450
		 添加孩子到优先队列
处理城市节点:Mehadia	父节点:Lugoj	路径损失为:299
	孩子节点:Lugoj 路径损失为:369
	孩子节点:Drobeta 路径损失为:374
		 添加孩子到优先队列
处理城市节点:Pitesti	父节点:Rimnicu Vilcea	路径损失为:317
	孩子节点:Rimnicu Vilcea 路径损失为:414
	孩子节点:Craiova 路径损失为:455
	孩子节点:Bucharest 路径损失为:418
		 替换状态: Bucharest 旧的损失:450 新的损失:418
处理城市节点:Craiova	父节点:Rimnicu Vilcea	路径损失为:366
	孩子节点:Drobeta 路径损失为:486
	孩子节点:Rimnicu Vilcea 路径损失为:512
	孩子节点:Pitesti 路径损失为:504
处理城市节点:Drobeta	父节点:Mehadia	路径损失为:374
	孩子节点:Mehadia 路径损失为:449
	孩子节点:Craiova 路径损失为:494
处理城市节点:Bucharest	父节点:Pitesti	路径损失为:418
	 目的地已经找到了
从城市: Arad 到城市 Bucharest 查找成功
Arad->Sibiu->Rimnicu Vilcea->Pitesti->Bucharest

五、启发式搜索

六、贪婪最佳优先搜索（GBS）

七、A*算法

启发式搜索通常是松弛问题

1.启发函数的特性

2.启发函数是一致（可采纳的）的条件

3.A*的可采纳、一致性、最优性、完备性和缺点

A*搜索与一致代价搜索类似，

除了A*使用g+h而不是g。

A*搜索既是完备的也是最优的。

4.启发函数在A*的作用

（1）一种极端情况，如果h(n)是0，则只有g(n)起作用，此时A* 算法演变成Dijkstra算法，就能保证找到最短路径。
（2）如果h(n)总是比从n移动到目标的代价小（或相等），那么A* 保证能找到一条最短路径。h(n)越小，A* 需要扩展的点越多，运行速度越慢。
（3）如果h(n)正好等于从n移动到目标的代价，那么A* 将只遵循最佳路径而不会扩展到其他任何结点，能够运行地很快。尽管这不可能在所有情况下发生，但你仍可以在某些特殊情况下让h(n)正好等于实际代价值。只要所给的信息完善，A* 将运行得很完美。
（4）如果h(n)比从n移动到目标的代价高，则A* 不能保证找到一条最短路径，但它可以运行得更快。

所以h(n)的选择成了一个有趣的情况，它取决于我们想要A* 算法中获得什么结果。h(n)合适的时候，我们会非常快速地得到最短路径。如果h(n)估计的代价太低，我们仍会得到最短路径，但运行速度会减慢。如果估计的代价太高，我们就放弃最短路径，但A* 将运行得更快。

八、曼哈顿距离和欧几里得距离

欧几里得距离就是上面的绿线，即欧氏距离

九、约束满足问题

十、约束图 Constraint Graphs

我们来介绍第二个CSP的例子：地图着色问题。这类问题是指，我们要用一些给定的颜色来给地图上色，并且相邻区域的的颜色必须不同。

约束满足问题常用约束图来表示，其中节点代表变量，边则代表变量之间的约束。有许多种不停的约束，每一种的解决方式也都不同：

一元约束：CSP中一元约束包括一个单变量。它们不在约束图中表示，而只是在必要时用来给它们约束的变量的域进行剪枝。
二元约束：二元约束包含两个变量。它们在约束图中表示为传统图的边。
多元约束：在CSP图中，包含三个或更多变量的约束也能用边来表示，它们看起来只是有一点点非常规。

我们来看一下澳大利亚地图的染色：

这个问题中的约束就是相邻区域颜色不能相同。于是，通过在每两个相邻的区域之间画一条边，我们能得到澳大利亚地图染色问题的约束图：

约束图的价值在于能帮助我们提取CSP的结构的有效信息。通过分析CSP的图，我们能确定关于它的一下信息，比如其连接/约束是稀疏还是紧密，或者它是否是树状的。在我们详细讨论求解约束满足问题时我们会深挖这些问题。

十一、约束满足问题求解回溯搜索

约束满足问题的传统解法是使用一种叫做回溯搜索（Backtracking search） 的算法。回溯搜索是对专门针对约束满足问题的DFS的最优化，主要改善了两个法则：

规定变量的顺序，并按照这个顺序选择变量的赋值。因为赋值是可以互换的（例如，令WA=Red，NT=Green 等价于令NT=Green，WA=Red），这是有效的。
在给变量选择赋值时，只选择不与已经分配了的值冲突的赋值。如果不存在这样的值，回溯并返回前一个变量，并改变其赋值。

迭代回溯过程的伪代码如下：

为了让这个过程更直观，我们来看一下分别用深度优先搜索和回溯搜索解决地图染色问题的局部搜索树：

注意DFS在意识到问题之前已经把所有部分都涂成了红色，即便如此，也没有往正确的方向做出多少改变。另一方面，回溯搜索在一个值没有违背任何约束时将其赋值给一个变量，这样能明显减少回溯的次数。虽然回溯搜索相比较深度优先搜索的霸王硬上弓要有了很大的改进，我们仍然可通过过滤、变量/值的排序和结构上的探索进一步提高速度。

回溯 = DFS + 变量排序 + 失败（不相容）回溯

十二、过滤Filtering

1、前向检验

2、弧相容

弧相容就是值域被删除的点要检查其所有相邻点的值域有无违反约束

十三、前向搜索额外补充

前向检测是一种深度优先搜索策略，它是回溯法的一种扩展。它采用了“向前看”的策略，即对一个变量进行赋值时，修改约束条件下相关变量的值域。其过程如下：

选择一个变量。
遍历变量值域。
根据变量的赋值，调整相关变量的值域空间。若不会导致DWO(Domain Wipe Out)则往下递归。
若有解则结束。否则恢复相关变量的值域空间，并回到步骤2。
该局部状态无解（对于步骤1选择变量，可使用启发式搜索优化。如MRV启发式，优先选择值域空间小的变量。）

十四、排序 MRV LCV

我们已经提到过，在解决CSP问题时，我们对涉及到的变量和值都进行排序。在实践中，使用两个基本原则——最小剩余值（minimum remaining values） 和最少约束值（least constraining value） 来“动态”地计算下一个变量和相应的值，通常要高效得多：

最小剩余值Minimum Remaining Values (MRV) ：当选择下一个要赋值的变量时，用MRV策略能选择有效剩余值最少的未赋值变量（即约束最多的变量）。这很直观，因为受到约束最多的变量也最容易耗尽所有可能的值，并且如果没有赋值的话最终会回溯，所以最好尽早赋值。
最少约束值Least Constraining Value (LCV) ：同理，当选择下一个要赋值的值时，一个好的策略就是选择从剩余未分配值的域中淘汰掉最少值的那一个。要注意的是，这要求更多的计算（比方说，对每个值重新运行弧相容/前向检测或是其他过滤方法来找到其LCV），但是取决于用途，仍然能获得更快的速度。