樊登爬山算法
㈠ 算法式和爬山法的区别
爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解。
算法式:把解决问题的方法一一进行尝试,最终找到解决问题的答案。特点册链:问题解决的系列搜索,采用试误州巧孙的方式解决问题,优点:一定可以找到某种解决问题的方法,缺点:耗时耗力。
爬山法与手段目的分析法的区别:
使用爬山法的每一步都在逐渐接近最终目标,不存在中途折回的情况;在使用手段目的分析法时,人们有时为了达到目的,不得不暂时扩大目标状态与初始状态的差异,以有利于达到最终目标。
比如,两兵交战,若敌我力量悬殊,我军可采取迂回战术曲线救国,先假装宽咐投降,获取情报,再一举反攻。
㈡ 爬山算法(Hill Climbing)解决旅行商问题(TSP)
旅行商问题 TSP(Travelling Salesman Problem)是数学领域中着名问题之一。
TSP问题被证明是 NP完全问题 ,这类问题不者宽腔能用精确算法实现,而需要使用相似算法。
TSP问题分为两类: 对称TSP (Symmetric TSP)以及 非对称TSP (Asymmetric TSP)
本文解决的是对称TSP
假设:A表示城市A,B表示城市B,D(A->B)为城市A到城市B的距离,同理D(B->A)为城市B到城市A的距离
对称TSP中,D(A->B) = D(B->A),城巧升市间形成无向图
非对称TSP中,D(A->B) ≠ D(B->A),城市间形成有向图
现实生活中,可能出现单行线、交通事故、机票往返价格不同等情况,均可以打破对称性。
爬山算法是一种局部择优的方法,采用启发式方法。直观的解释如下图:
爬山算法,顾名思义就是 爬山 ,找到第一个山峰的时候就停止,作为算法的输出结果。所以,爬首衫山算法容易把局部最优解A作为算法的输出,而我们的目的是找到全局最优解B。
如下图所示,尽管在这个图中的许多局部极大值,仍然可以使用 模拟退火算法(Simulated Annealing) 发现全局最大值。
必要解释详见注释
此处根据经纬度计算城市间距离的公式,请参考 Calculate distance between two latitude-longitude points? (Haversine formula)
此处初始化数据源可以使用 TSPLIB 中所提供的数据,此程序大致阐述爬山算法的实现。
编写于一个失眠夜
菜鸟一枚,欢迎评论区相互交流,加速你我成长•ᴗ•。