爬山法和模拟退火算法通常用来求解TSP的最短路径问题。爬山法的一个最大的缺点就是，它只能获取一个局部最优的解，但是无法获取一个全局最优的解。而模拟退火算法，它以一定的概率接受较差的解，因此，可以在一定程度上避免局部最优的问题。而迪杰斯特拉算法虽然能够得到最短路径，但是由于需要大量的计算，比较消耗性能，因此，实际应用中并不多。关于爬山法和模拟退火算法的介绍，百度上不是很清楚，其他的一些资料上也介绍的不是很详细。找了一篇比较靠谱的解释和介绍，如下（
点击打开链接
和
点击打开链接
）：
局部搜索是解决
最优化问题
的一种
启发式算法
。对于某些计算起来非常复杂的最优化问题，比如各种NP完全问题，要找到最优解需要的时间随问题规模呈指数增长，因此诞生了各种启发式算法来退而求其次寻找次优解，是一种近似算法（Approximate algorithms），以时间换精度的思想。局部搜索就是其中的一种方法。
对于
组合问题
，给出如下定义：
请点击此处输入图片描述
其中，S为搜索空间（解空间），其中的每一元素都是问题一个可能解。解决组合问题，即是找到一个s* ∈ S，使得目标函数f值最小。s*称为全局最优解。
对于
邻域动作
定义如下：
邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。例如：对于一个bool型问题，其当前解为：s = 1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，当将邻域动作定义为互换相邻bit时，得到的邻居解的集合N(s)={0101,1001,1010}.
2、过程描述
局部搜索算法从一个初始解开始，通过邻域动作，产生其邻居解，判断邻居解的质量，根据某种策略，来选择邻居解，重复上述过程，至到达终止条件。不同局部搜索算法的区别就在于：邻域动作的定义和选择邻居解的策略，也是决定算法好坏的关键（
集中性
和
发散性
，Intensification and Diversification）。
版权声明：本文为lyp5257918原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。