面试官问:如何实现饿了么|美团商家推荐
截图
需求背景:推荐10公里范围内的商家，根据喜好度等因素排名！取决于骑手的配送距离，这个配送距离大概率要基于统筹算法，满足调度配送的最优化。
假如你是个CRUD程序员缺乏算法基础可以这样设计。
有两个基础条件可以利用起来。
静态数据:商家的地理位置(经纬度)
动态数据:客户的地理位置，需要实时计算。
方案一:将所有商家的经纬度信息投影到平面坐标中。
将经纬度投影到平面坐标轴中
来自网络图片，侵权必删
表设计:第一张表是商家表，字段:[商家编号，商家名称，餐饮类型，坐标位置，喜好度等字段，配送时间](星级表示)转换为(5200*横坐标+纵坐标)，中国的东西距离是5200公里，南北距离是5500公里。投影坐标横坐标纵坐标长度是5200*2000个单元格，纵坐标长度是5500*2000个单元格。这个表实际存在的记录为实际商家数量，坐标位置可以用公式转换为(转换公式是:5600*经度°+纬度，1米的距离单位是赤道的一千万分之一来划分)，这里的配送时间是路径规划问题，不在这里阐述方案！
第二张表是商家10公里范围的所有坐标，直线距离划分，字段是[位置是经纬度转换过后的数值转换公式同上]，这张表的字段有[商家编号，经纬度位置，距离]，经纬度位置建立索引即可。
下面是投影的坐标轴，每个单元格的边长是1M,"客户坐标"代表原点，注意，客户坐标一定是落在正方形的四个角上的任意一个点，商家位置是固定在1*1的单元格上的四个点上的任意一个点上
002
最终可以用一个SQL查出结果出来，基于获取了当前买家的坐标位置的情况下。
Select 商家名称 From 商家表 a，商家10公里范围坐标 b where a.商家编号=b.商家编号 AND b.经纬度位置="买家所在位置"
and distance<=10*1000
或者另外的方案是不用第二张表，以买家为原点，以一米为拓展园心，辐射出10公里以外的一个大圆圈，先查出10公里范围内的所有坐标落在圆心内的所有商家坐标。然后再计算出点到圆心的距离。
Order by a.排名，b.距离 Desc Limit 20
这样做的优势是不需要实时计算两点之间的距离，并且可以用CRUD思维面向程序员开发!缺点是:存储的数据量大，因为转换成了平面坐标，一个点(商家位置原点)需要从东南西北四个方向建立四个平面矩阵。并且需要链接对角线，相当于需要穷举矩阵的数量，每个矩阵的有4条记录，空间复杂度总记录数是:4*穷举的矩阵数量。
另外可以用概率型的退火算法(类似蚁群算法)，还有一种思路是动态规划算法。但这两种算法貌似都不能完全避免实时计算两点距离的步骤。
优化点:K-V缓存已访问过的数据，key为坐标值，value为访问过的商家列表。
网友评论