5 近似法
文章插图
并不计算出最优解，相反，它只计算出“足够好”的解 。通常利用近似法解决那些计算成本很高又因为其本身十分有价值而不愿放弃的问题 。推销员问题（见第16章）是一个通常会用近似法去解决的问题 。
设想一位推销员需要设计一条去往好几个城市工作的路线 。推销员问题的目的是找到最短的可能路径，以便推销员能够在回到出发点前恰好每座城市都只去过一次 。由于推销员问题可能存在一种最优的策略，但计算的代价很高，因此可以采用启发式的方法得到一个近似解 。当最优策略行不通时，启发式的方法是我们能够接受的一种比最优策略稍逊一些的策略 。
推销员问题可以用图表的方式来描绘 。把推销员必须前往的城市在格子中用点标记出来 。然后按照如下启发式的方法来寻找这些点之间的最短路径 。从推销员出发的位置开始只有一个点，将这个点涂黑 。所有其他的点在加入路线图之前都是白色的，当它们加入时也同样涂黑 。接下来，对于每一个还没有加入到路线图中的点v，计算最后一个加入到路线图中的点u和v之间的距离 。通过这种方法，选择离u最近的那个点，将其涂黑并加入路线图中 。重复这个过程直到所有的点都已经涂黑 。最后，再次将出发点加入路线图使其闭合，这样就完成了整个路线图 。
推荐阅读
- 细思极恐的诡异经历 诡异的事情发生了
- 玛雅第五个预言为什么没有实现 玛雅人的五大预言最后一个为什么没有成功
- 面试官：知道时间轮算法吗？在Netty和Kafka中如何应用的？
- 灵异真实故事民间 灵异民间故事
- 怀念已故的亲人,珍惜身边的亲人 对亲人的眷恋
- 启元世界：打造AI决策智能体，用小样本实现10的26次方复杂空间决策
- 泥盆纪末大灭绝 泥盆纪大灭绝的原因
- 世界大战里的外星人 人类大战外星人
- 基本的茶具有哪些,选择适合自己的那杯花草茶
- 菊花粥材料及制作介绍,菊花水果茶的做法