查找与给定地区代码最近的送货中心

Question

这是在一家公司面试过程中被问到的。假设有一个界面来查找与您所在区域最近的配送中心。你只需输入你的邮政编码/密码，它就能返回最近的配送中心。这样做的数据结构和算法是什么？比如，你的手机坏了，想去服务中心。你去公司网站，输入你的邮政编码，找出最近的维修中心。它是怎么做到的？

我提出了一个图+ hashmap解决方案，我将从给定节点返回相邻节点，地址将存储在hashmap w.r.t zipcode中，但这还不够好，因为面试官一直在使用地理属性，说没有给出两个中心之间的距离，所以您如何知道哪个是最近的，如果被问到最近的3个中心。当时我想不出任何解决办法。他还一遍又一遍地问我你需要什么数据来解决这个问题。知道这方面的方法是非常有帮助的，因为它已经困扰了我好几天了。谢谢

Answer 1

大多数算法只处理单点--仅取邮政编码区域的中心点就足够了。

对于一个最近的邻居来说，Voronoi图似乎是最好的选择。

它将空间划分成区域，这样，给定任何查询点，我们就知道哪个点是最近的。

取自维基百科

​

​

kd树也是一种选择：

k-d树是一个二叉树，其中每个节点都是一个k维点.每个非叶节点都可以被认为是隐式地生成一个分裂的超平面，该超平面将空间分成两个部分，称为半空间。该超平面左边的点用该节点的左子树表示，超平面的右点用右子树表示。超平面方向的选择方式如下:树中的每个节点都与一个k维相关联，超平面垂直于该维的轴。因此，例如，如果对于特定的拆分选择了"x“轴，那么在子树中具有比节点更小的"x”值的所有点都会出现在左边的子树中，而所有具有较大"x“值的点将出现在右侧的子树中。在这种情况下，超平面将由点的x值来设置，其法线是单位x轴。

找到k近邻要困难得多。有一个K近邻算法，但这是一个分类算法，所以我不确定它在这里有帮助。

一种选择是创建该区域的网格。然后，给定一个点，我们知道它在哪个单元格中，我们可以简单地查询该单元格及其邻居，直到我们找到所需的邻居数。

一个人在这里必须小心，因为下一个最近的点实际上可以在另一个细胞中，例如：

--------------
   |        B|
 A | X       |
   |         |
   |         |
--------------

给定点X，最近的点是A，但是如果我们简单地查看同一个单元格，B就会返回。我们还需要查看所有相邻的细胞，，在之后，我们找到了k点。

Answer 2

你需要整个道路网络，它是一个稀疏矩阵，包含所有节点之间的距离。您还需要包含服务中心的节点列表。有了这一点，我认为A*算法应该在确定给定位置与每个服务中心之间的距离时完成工作，然后取最少三个距离。我确信有更有效的算法，但我相信面试官应该专注于解决问题的方式，而不是要求实现细节，如数据结构。如果我要解决现实生活中的这样一个问题，我会先做一个文献研究。我不知道在面对这样的面试官时，什么样的策略是最好的，他是否会接受这样的回答。在深入研究细节之前，保持自信并提供解决方案的概述可能会更好。不过，不要后悔。从经验中获益，继续前进。你不知道上帝对你有什么恩惠。