随机搜索的方法很低效,因为没有利用已经发现的较优解,而是选择十分离散的解来尝试。一个替代方法是登山法,其主要思想是,从一个随机解开始,向着临近解中的最优项出发,一直到无法找到更优解为止。就像从山坡下山,一直沿着最陡峭的方向行走,最终来到山谷:
在“组团出游”的问题里,从一个随机的时间安排开始,找到与之相邻的所有解(让某个人的出发或者返回航班做早一班或者晚一班的调整),在其中选择最优解,然后重复这一过程一直到没有更优解为止。
但是登山法有个很大的缺陷是,最后的解可能只是一个局部最优解,如下图。要找到全局最优解,要用到随机重复登山法。后面会用到更多的避免陷入局部最优解的方法。
这个系列来自《集体智慧编程》的第五章,完整golang代码在https://github.com/baixiaoustc/optimization