人工智能基础——搜索算法

引言

本学期开设了人工智能基础这门课程，使用了《人工智能 一种现代方法》作为教材，整本书将尽一千多页。我觉得他内容其实很不错，但是阅读难度还是比较大的，对于问题的阐述有点过于复杂了，需要比较强大的阅读能力，并且难以圈划重点。
因此，我打算在每节课结束后，用自己的理解，笼统地整理一下各种算法的实现，主要注重思想，而不会实际去演示。

第一课——搜索算法

什么是搜索

其实我相信大家都至少学过dfs或者bfs（最基本的两种搜索算法），但是我还是稍微讲一些对搜索的理解。
用我的话来说，搜索就是通过状态之间的转移关系穷尽所有的状态，然后找到满足目标或是最好的某个状态。
首先什么是状态，状态是对于对象而言的，比方说对象是一个人，那么身高、体重、年龄等就是我们的状态。状态的选择对问题的求解是十分重要的。状态的选择要恰到好处，要恰好包括目标在问题求解中的全部信息，无用的信息反而会徒增计算量和内存。
然后是状态之间的转移，我们假设目标任务是减肥。我们的转移条件其实就是我们的决策，比如说今天我打算锻炼30分钟，那么我消耗了很多卡路里，体重自然会下降。假设我打算躺一天不运动，那么体重就会上升。你可能会觉得这个问题很蠢，那我每天努力锻炼身体不就可以越来越瘦了吗。你很聪明，你已经学会贪心算法了（bushi 。但是，你真的做得到每天锻炼吗，我们再给你加一个状态，锻炼积极性，每周最多锻炼多少分钟，一旦这周锻炼时间超过了，你就不再愿意锻炼了。那么你就不能每天都一直锻炼了。
不管是状态还是转移过程，都可能非常复杂，如何定义这两者是解决问题的关键。效率与性能之间的矛盾就在这里体现出来了，如果几个简单的特征就可以变现出状态的大部分特征，那多余的状态大可不要。
好像又跑题了，下一个是搜索的停止条件，拿我的例子很简单，比如说降到某个体重就算结束。但是达到目标体重的方式并不是只有一种，比如说你要求在几天内减到某个体重，那么太慢到达目标点的路径就不可选。
最后，如何求解上面说的这些东西呢？搜索就是暴力，第一天，我们循环训练时间5，10，15，20分钟，第二天也是一样。那么两天一共就是4x4=16种状态，随着天数越多（深度越大），状态也越来越堵，把所有的状态都走一遍，选出你要的状态，搜索的过程就完成了。

草，我废话太多了，这些都可以不看，进入正题了，后面会很简洁

无信息搜索

无信息搜索就是除了问题本身的状态，没有其他信息。你可能对其他信息不是太明白。等你看了有信息搜索就明白了。

BFS（广度优先）

继续减肥问题，第一个状态训练0天，体重200斤（状态0），第一天训练五分钟（状态1），第一天训练10分钟（状态2）。。。，当穷尽第一天所有选择后再到第二天。

一致代价搜索

现在深度不代表天数了，天数变成状态，有的运动要花两天，可能减更多体重。我还是想尽快内减到100斤，那我的搜索就是先选择天数花的比较少的。

DFS（深度优先）

减肥问题，n天减到100斤，第一天锻炼5分钟（状态1），第二天锻炼5分钟（状态2）。。。第n天锻炼五分钟（状态n），在状态没有被判定失败之前，搜索会顺着之前的一直继续，也就是说，整个搜索过程中，我们一直保持着一条完整的计划（训练完一天做下一天的打算）。失败后，则回到前一天的状态，选择前一天的其他状态转移方式。

深度受限搜索

很简单，假设要减到100斤（没规定几天内完成），我训练了一千天，还是没达成目标，那我不可能继续盲目训练下去（无穷无尽），那我自然会在深度超过某个值的时候停止，说明这个计划有问题。

迭代加深DFS

我想瘦十斤，我不确定自己到底要花几天，反正不能超过一百天，但我直接用100天来搜索，要花费的时间空间太长了。那我先假设只要五天，搜完五天内的所有状态，成功就直接结束了。没成功则搜索六天内的所有状态，一直到一百天。的确，这种算法重复生成了很多状态，但事实上，即便是最后还是花了一百天才搜索万，实际上也不过是直接搜索一百层的常数倍的复杂度，但一旦答案深度没那么深，就赚大了。

双向搜索

双向搜索一定要放图片

很直观吧，如果有start开始搜索，分支的面积（圆）将非常的大。但是要注意的是这个状态必须是可逆的，就是从goal开始的搜索符合实际意义。

有信息搜索（启发式）

有额外信息的搜索，直接看例子。

罗马尼亚度假问题

经典问题，这是一张罗马尼亚地图（真实地图）。问从Arad到Bucharest最近的路径。

你们肯定学过最短路算法（比如说狄杰斯特拉），但这里不太一样，我们将用到额外信息（这里使用h(n)，代表离目标点的欧式距离），在拥有这种条件时，如何更快找到答案。

贪婪搜索

很简单，就是每次都走往hn最小的点（即去的点离目标的直线距离最近）。这种做法随便想想也知道可能根本找不到可行解，既难找到最优解，还可能死循环。

A*搜索

f(n)=g(n)+h(n)
g(n)是走到这里花的时间，h(n)是离目标点的估计距离（直线距离），f(n)就变成了经过n到目标点的估计，然后进行一致性搜索。
很显然，这种做法是有实际意义的，我不能只看我去的地方是不是里目标点近，而是要看我走到那里的距离加上哪里离目标点的距离最近。
这种算法在h(n)选择合理时是最优的。（想想也知道，我们用一致性搜索，那f(n)满足一致性搜索的时候肯定是正确的）
可采纳性：h(n)永远小于n实际到目标点的距离，满足这个条件树型的搜索就一定是最优的了。
一致性：h(n)<=cost(n,n’)+h(n’),h(n)，cost(n,n’)指n到相邻某点距离。满足这个条件图搜索一定最优。
证明：画等值线，想搞清楚自己去研究。核心就是，在所有可行的里面，最优解一定是最先被搜索到的。

存储受限的启发式搜索

迭代深度算法：前面说过了，对bfs可以+1+1，但是对于一致性搜索，如果递增的是个实数，就不可以+1+1了。

递归最佳优先搜索（RBFS）

dfs剪枝，记录最好的可行解，后面搜索超过了就剪断

简化内存受限（SMA*）

就是搜索完的子树先删掉，记录给父节点。然后最后如果发现最优解在这颗子树里面，再回来重新搜索一遍。

启发式函数

我觉得这是魔法，但我是麻瓜
找一个好的h(n)，你可以去研究一下马尔可夫决策过程
这才是核心，自己去研究吧