文章目录引言局部搜索算法爬山法模拟退火局部波束搜索遗传算法连续空间局部搜索不确定动作搜索使用部分可观察信息搜索在线搜索问题总结
引言
这是优化的内容，用状态(包括很多参数)描述一个对象。 如果将这些参数作为坐标轴，则得到超空间(函数定义域)。 超空间中的点分别对应于某个函数值，我们在空间中寻找函数的最大值。
介绍各种算法，核心是寻找描述上节课h(n ) ——状态分数的函数。
局部搜索算法局部是指只关心状态，不关心路径，从一点到另一点。
登山法类似于梯度下降思想，但形式上只是相反。 是寻找状态空间邻域中参数的最优解。 我相信大家都能做到。
很明显，经常找不到全局最优解。
例如，即使是平坦的区域，无论向哪个方向，最大值都不会变化。 此时，有随机的登山法，如随机选择后继者直到上升等。
但是，这样也不行。 可能会被困在局部最优解中。 这样，如果随机生成初始点，设登山法发现解的概率为p，则通过重复1/p次的登山法，几乎可以找到最佳解。 也就是说，随机生成初始点，反复登山。
模拟退火给出初始点，在他周围随机寻找点，优于他就更新到这一点，否则概率p接受这一点，每次接受“更差”点，p的值呈指数下降。
在这里记录我对这个算法的理解
如果充分减慢温度(接收概率)的降低，则找到全局最佳解的概率接近1
我们考虑特殊情况，如果我的温度不下降，总是按50的概率接收，也就是说，只要存下纯粹的随机算法，在时间无限的时候，就一定能找到全局最优解。 但实际上没有无限尝试的机会，必须收敛结果。 此操作会降低找到全局最优解的可能性，但会显著提高性能。
时间和准确度处于矛盾的平衡，这个概率从1降低到0.999，但可以将时间消耗从无限变为有限。 模拟退火可以说是完全随机的妥协。
局部波束搜索重复随机选择k个点，搜索所有k个点生成的状态，获取最佳k个的过程。 这和遗传算法有点相似，但没有k个点的交集，所以是无性繁殖。
局部波束算法也存在爬山法局部最优的问题，容易聚集在所有点的区域附近。随机束算法为了解决这个问题，没有选择最好的k个后继者，而是随机选择k个更好的后继者。
遗传算法随机生成k个状态，编码状态，使用某个算法(最容易交换一部分)。 于是，很多新的状态就会作为“孩子”得到。 从这些“孩子”中选出k个最好的，重复过程。
简而言之，具体很复杂，但思想很容易理解。
连续空间中局部搜索连续空间的搜索难度在于各状态的下一个分支是无限的。 的基本思想仍然是梯度法，但由于自变量较多，方程的梯度=0无法求出闭合解。 (列的方程式没有解，每次都必须经过数值推理。 )但是局部的坡度)，可以沿着那个方向爬。
也有更快的攀登方法。 这些可以去看优化算法。 cqdmj法、共轭梯度法、伪cqdmj法等，有空请整理。
使用不确定动作搜索时，在相同条件下，一个状态可能会转变为多个状态。 整个过程不再是树，而是序列。
就像你开车一样，街道很短，但可能会堵车。 小路很长，但比较畅通。 你决策的结果也取决于你无法观测的外在条件。 在这种时候，你的策略也被称为应急策略。
通常，我们想找的是能稳定达成目标的解，我们的最终解应该是树，无论怎么走在树的分支上，最终都会到达满意的状态点。
果然，一般的搜索，只是一个值得选择的节点，需要在所有的子树中找到解，这一点在最后的解上。
因为在搜索过程中会发生循环，所以可以将其视为无限生长的树(或有环的图)。 在检索树的过程中hash状态，遇到相同的状态时会遇到循环，也不需要继续进行检索。
即使使用部分可观察信息检索，也首先没有观察信息检索
即使我不知道自己处于什么状态，我也能找到最好的决策。
来波浪是不合适的，但我认为可以说明问题的例子。 我肚子痛，请检查一下身体，看看自己在吃什么药。 但是，检查结束后直接痛死我很害怕。 所以吃了所有治疗肚子疼的药，然后你也不知道。 总之有防止肚子痛的药。
这个例子当然是在胡说八道，但它告诉我们，即使不知道我们处于什么状态，也有可能做出走到目标点的决策。
例如，状态(1，1，0 )表示患了病1，2，如果没有病3，则所有状态共有8种，但通过吃所有的药)为0，0，0。 解决方法是魔法。 因为状态太多了。 先解开满足一个状态的路径，然后才能看到这些路径是否满足其他状态； 也可以将这些状态打包在一起，无论内部情况如何进行编码； 或者，使用巧妙的动态描述，如可以吃一剂药治疗四种疾病。 不使用(0，0，0，0 )这一表达，直接打包成某种疾病0。
然后是可观察检索/部分观察
开始觉得不会写，只是状态的定义和转移的问题。 我觉得这本书无法用语言表达了。 在线搜索问题失去了上帝的观点，一步一步来看吧。 我(特工)出生在迷宫里。 我现在出去。 我只能朝前后左右四个方向走。 有标志和我位置的传感器，但不知道迷宫的长度。
虽然还是树，但是只有到了一个节点才能看到后续的节点。 很明显它一直回到朔
的过程。最差情况每个点要走两次（dfs） 随机行走算法爬山法，这回是真爬山，爬到了一个小坡上面（局部最优）。按之前的再随机一个出生点再爬，但是不行，因为这是真爬山。那我就随便走走，往右走走虽然变低了但是却可以看到一座可能更高的山（启发式函数h(n)这里我当作目测山高），那我就会往那里走。 总结
我发现这门课越来越玄学，真的全靠感受。给的都只是思想，细节实现要靠自己，也要根据实际问题。