爬山算法是一种局部搜索。它从一个现成的解出发每次只看周围的解哪一个更好就走过去直到周围都不如当前这一点就停下来。「更好」由目标函数决定。要爬到最高就选函数值更大的邻居要找最低成本就选函数值更小的邻居。每一步只往更优的方向走所以叫爬山。用一条高度线看这个过程。横轴是位置纵轴是高度目标是站到最高处。位置0123456高度1325416邻居就是左右相邻的一格。从位置 1 出发高度是 3。左边高度 1右边高度 2都更低算法停在这里。这是一个局部最高点整条线的最高点在位置 6高度是 6它走不到。从位置 4 出发高度是 4。左边位置 3 的高度是 5比 4 高于是走到 3。到了 3 以后左边 2、右边 4 都更低又停住。这次停在高度 5仍然不是全局最高。从位置 5 出发高度是 1。右边位置 6 的高度是 6走到 6 后两边都没有更高的格子停在全局最高点。同一个算法起点不同停下来的地方就不同。它只保证停在一个「周围都更差」的点不保证这是整张图里最好的点。每一步如果把所有邻居都看完再挑最好的那个叫最陡上升。邻居很多时也可以碰到第一个更好的就走不必把全部邻居算完。为了不总停在同一个局部高点可以从多个随机起点各爬一次留下其中最高的结果。配送路线、排课、参数调节都可以这样用当前方案改一小步对调两个城市、挪一节课总代价变好就接受变差就保持原样直到小改都不再变好。和退火算法的区别两者都是从当前解走到邻居差别在于变差的那一步收不收。爬山只在邻居更好时才移动。周围都更差就停住所以会停在局部最高点。用前面那条高度线从位置 1高度 3出发左右是 1 和 2都更低爬山停在 3到不了位置 6 的高度 6。模拟退火在邻居更差时仍按概率接受。差得越多、温度越低接受概率越小Pe^(−Δ/T)从高度 3 走到高度 2Δ1。温度 T2 时Pe−1/2≈0.61这一步有大约六成机会被留下。留下之后才有机会继续走到后面的全局最高点。温度再降下去差步越来越难被接受搜索逐渐稳定。所以爬山的结果由起点和邻居决定同一起点反复跑停的地方相同。退火每次跑都可能走不同的路用降温换一次跳出局部高点的机会。