解决两个现实生活问题的算法

Question

我正在努力寻找两个现实生活问题的答案:

1. 餐厅服务:当我使用我的订餐应用程序(例如 FoodPand、Zomato 等)时，该应用程序会在我登录时检测我的位置，并相应地建议附近的餐厅(可能在范围足够好，以便所选餐厅可以提供食物)。

2. 出租车服务:当我使用出租车服务(例如 Uber 或 Ola)时，当我尝试预订出租车时，他们也会检测我的位置，并建议当时附近可用的出租车.

问题: 如何找到最近的餐馆和最近的出租车？他们实际使用哪种具体算法？由于这两种情况有所不同，因为搜索数据在一种情况下是静态的，而在另一种情况下不断变化。

我对这个问题的看法:

1. 在对这个主题进行了一些头脑 Storm 之后，我发现由于餐馆是固定的实体，我们可以将它们映射到 KD 树(它允许存储空间索引)。根据顾客的位置，我们可以在 KD 树上进行搜索，找出附近的一组餐馆。 KD树的创建需要O(n)时间，搜索需要O(logn)时间，n是树中节点的数量。这种方法对我来说似乎足够好，因为我不知道还有比这更好的方法，并且仍在寻找答案。

2. 就出租车服务而言，出租车的位置不是静态的(与餐厅服务不同)。因此，为出租车的每个更改位置创建 KD 树似乎是一项开销。根据出租车的当前位置，我如何找到离我最近的 5 辆出租车？出租车实际使用哪种算法？

任何见解都将受到高度赞赏。

附注:我还遇到了 K 最近邻搜索算法，它再次导致 KD 树。

Answer 1

存在名为 Quadtree 的数据结构作为二维动态 k-D 树的解决方案。但实际上，真正的实现可能不涉及繁重的数据结构。您可能会想到像这样的更简单的方法，它可能会优于动态 k-D 树:

1. 将 map 划分为矩形网格
2. 当出租车改变位置时(发布包含GPS坐标的请求)，检查它是否仍在矩形内，否则更改矩形的内部信息
3. 当用户想要找到最近的出租车时，只需在网格中找到其矩形并通过穷举搜索找到最近的出租车即可

你可能会想“为什么？”。实际上，在上面的简单方法中，添加并发和并行化会更容易，但修改 k-d 树可能会很困难。