我正在构建一个基于找到一个位置的"方便会面点"的应用程序.
目前我将"方便"定义为"最小化总行程距离".这与查找质心的问题不同,如下例所示(为方便起见,使用笛卡尔坐标而不是纬度和经度):
这些点的最小总行程位置为(0,0),总行程距离为12; 质心位于(0,4),总行程距离为16(4 + 4 + 8).
如果位置被限制在其中一个点上,问题似乎变得更简单,但这不是我想要的约束(不像,例如,这个类似的问题).
我似乎无法做到的是提出任何类型的算法来解决这个问题 - 建议欢迎!
我最近遇到过这个问题.假设x轴上有n个点,x [0],x [1] .. x [n-1].让与这些点中的每一个相关联的权重为w [0],w [1] ... w [n-1].从0到n-1之间的任何点开始,目标是覆盖所有点,使得w [i]*d [i]的总和最小化,其中d [i]是到达第i个点所覆盖的距离.起点.
示例:
假设点数为:1 5 10 20 40
假设权重为:1 2 10 50 13
如果我选择从点10开始并选择移动到点20然后到5然后再到40然后最终到1,那么加权和将变为10*0 + 50*(10)+ 2*(10 + 15)+ 13*(10 + 15 + 35)+ 1*(10 + 15 + 35 + 39).
我试图通过贪婪的方法解决它,从具有最大相关权重的点开始并移动到第二个最大权重点,依此类推.但算法不起作用.有人可以指点一下解决这个问题必须采取的方法吗？