算法兩個實際生活中的問題

Question

有哪些，我苦苦尋找的答案兩個實際的問題：

1. 餐廳服務：當我用我的訂餐應用程序（如FoodPand，Zomato，等等），當我登錄時，應用會檢測到我的位置，並據此建議附近的餐館（可能範圍足夠好，以便所選餐廳可以提供食物）。

2. 駕駛室服務：當我使用出租車服務（如尤伯杯或OLA），他們也檢測到我的位置，當我嘗試預訂了一輛出租車，並建議可當時附近的出租車。

問： 如何找到最近的餐館和出租車最近做？他們實際使用哪種特定的算法？由於兩種情況都有所不同，因爲一種情況下搜索數據是靜態的，另一種情況下會不斷變化

我對這個問題採取：

1. 做的題目有些頭腦風暴之後，我才知道，由於餐廳是固定的實體，我們可以通過KD樹將它們映射（它允許存儲空間索引）。根據客戶的位置，我們可以在KD樹上搜索以找出附近的一組餐館。 KD樹的創建需要O（n）個時間並且搜索花費O（logn）時間，n是樹中n個點的數量。這種方法似乎對我來說足夠了，因爲我沒有意識到比這更好的方法，我仍然在尋找答案。

2. 在出租車服務的情況下，出租車的位置不是靜態的（與餐館服務不同）。因此，爲每個改變的出租車位置創建KD樹似乎都是一種開銷。鑑於出租車的當前位置，我怎麼能找到5個最近的出租車？駕駛室實際使用哪種算法？

任何見解將不勝感激。

P.S. ：我還遇到了K最近鄰搜索算法，這又會導致KD樹。

Answer 1

存在稱爲Quadtree的數據結構作爲二維動態k-D樹的解決方案。但實際上，實際實施可能不涉及繁重的數據結構。你可能會覺得更簡單的方法是這樣一個，這可能潛在跑贏動態kd樹：

1. 鴻溝地圖爲矩形網格
2. 在駕駛室改變其位置（含GPS座標POST請求），檢查它是否仍然在矩形以其他方式改變矩形的內部信息
3. 當用戶想找到最近的出租車，只是定位在網格中的矩形，並找到最近的一個用窮舉搜索

你可能會想「爲什麼？」。實際上，在上述簡單的方法中，添加併發和並行化會更容易，但修改k-d樹可能非常困難。