最短距离旅行 - 共同会面点

Question

我遇到了这个问题,其中2-D网格上有许多房屋(给出了它们的坐标),我们基本上必须找到哪个房屋可以用作会合点,以便每个人的行进距离最小化.让我们假设沿x或y轴的距离占1个单位,与对角线邻居的距离取(例如)1.2个单位.

我真的不能想到一个很好的优化算法.

PS:不是作业问题.而我只是在寻找一种算法(而不是代码),如果可能的话,还有它的证据.

PS#2:我不是在寻找穷举解决方案.信不信由你,这确实打动了我:)

Answer 1

如前所述,在曼哈顿距离的情况下,中位数给出了解决方案.从众所周知的事实来看,这是一个明显的结论,即中位数最小化绝对偏差的平均值:

E|X-c| >= E|X-median(X)|任何常数c.

在这里,您可以找到离散案例证明的示例:https:
//stats.stackexchange.com/questions/7307/mean-and-median-properties/7315#7315

Answer 2

这可能确实效率很低，但要循环遍历所有房屋，然后循环所有其他房屋。（嵌套 for 循环）使用距离公式计算 2 栋房子之间的距离。然后你就得到了每栋房子之间的距离。查找距离最近的房屋的一种快速简便的方法是将每个人对于给定房屋的步行距离相加。总步行距离最短的房子是首选的会议区域。