内容简介：面临这样一个问题, 粗略一看就是tsp问题, 你只要保证分配好的所有配送员的总路线最短就可以了. 但是, 实际上, 我们可以简化问题. 这里我们要引入一个前提和一个猜想.因为, 最小生成树有好几个多项式时间的算法, 因此, 我们这次不仅仅解决了300单的分配问题, 3000单, 30000单, 都没有问题了. 只要满足单一起点(仓库/发货点)这个条件.最小生成树的主力算法有两个:
面临这样一个问题, 粗略一看就是tsp问题, 你只要保证分配好的所有配送员的总路线最短就可以了. 但是, 实际上, 我们可以简化问题. 这里我们要引入一个前提和一个猜想.
- 前提: tps问题可以和最小生成树对应起来, 对于最小生成树的遍历, 就自动形成一条路径, 而且这条路径可以保证<2倍的最短路径. 因为最小生成树的深度遍历导致走了两边. 而最小生成树本身的总长度肯定小于最短路径. 如下图示意.
- 猜想: 那么我们可以认为, 一组点, 他们的最小生成树比较小, 那么他们的路径在很大的概率上也会比较短.
方案: 我们可以使用最小生成树做订单分配
因为, 最小生成树有好几个多项式时间的算法, 因此, 我们这次不仅仅解决了300单的分配问题, 3000单, 30000单, 都没有问题了. 只要满足单一起点(仓库/发货点)这个条件.
最小生成树的主力算法有两个:
- 克鲁斯卡尔kruskal
- 普利姆prim
我们逐一介绍一下:
克鲁斯卡尔
- 从一个点集中找到最短的路线, 加到树里面,
- 然后剩下的里面继续找最短的, 如果能连在一起就连在一起, 否则就保持森林状态,
- 直到某一个线段加进来之后, 森林里面的最后两棵树也连在一起形成一棵大树, 那么算法停止.
普利姆
- 从一个点集中任意找一段路线, 加到树里面
- 然后, 此时树里面有2个点, 那么查找距离这两个点最近的点, 把他加到树里面.
- 此时树里面有3个点, 再加入离这三个点最近的点.
- 直到所有点都加入, 算法终止.
从描述我们可以看出来, 克鲁斯卡尔的开销要大一些, 因为他要做所有距离的排序, 而普利姆每次都是一个不大的范围里面找最近的一个值. 不过克鲁斯卡尔其实有很大的优化空间, 这里要引入一个概念: 邻域.
- 邻域: 一个点相邻的一个或者多个点组成的一组点就是一个邻域.
- 克鲁斯卡尔可以只保留每个点最近的3-5个距离进行排序, 最终组成树, 不过这样可能形成森林, 但是, 没关系, 最后再补充需要的几个距离就可以了. 这个思路非常有用, 未来的线性规划方案就用到了这个思路.
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
技术元素
[美] 凯文·凯利 / 张行舟、余倩、周峰、管策、金鑫、曾丹阳、李远、袁璐 / 译言·东西文库／电子工业出版社 / 2012-5 / 55.00元
我会将我不成熟的想法、笔记、内心争论、草稿以及对其他文章的回应都写在《技术元素》中，这样我就能知道自己到底在想些什么。——KK “技术元素”（technium)是凯文•凯利专门创造出来的词语。“技术元素不仅仅包括一些具象的技术（例如汽车、雷达和计算机等），它还包括文化、 法律、社会机构和所有的智能创造物。”简而言之，技术元素就是从人的意识中涌现出来的一切。KK把这种科技的延伸面看成一个能产生......一起来看看 《技术元素》 这本书的介绍吧!
