概 述
本人完成了出租车经营策略研究中的基础分析、原地待命策略、低速巡游策略和选作中的城市POI分析与推荐。工程代码在压缩包的DSpj文件夹内。相关数据在data文件夹内。
一、环境说明
GUN GCC Compiler
Code::Blocks 13.12
Windows10 64bit
二、算法与数据结构介绍
2.1 geohash算法
将经纬度hash成一个long long。算法流程如下，比如(120, 30) 范围精度是0-180 唯独是0-90：
120>=(0+180)/2 故h[0]=1 30<=(0+90)/2 h[1]=0
120<=(90+180)/2 h[2]=0 30>=(0+45)/2 h[3]=1
120>=(90+135)/2 h[4]=1 30<=(22.5+45)/2 h[5]=0
以此类推二分得到每个坐标唯一的hash值。
因为用了64位，所以可以保证每个点的hash是唯一的。所以用这个确实可以查到最近的点，唯一的cheat是在分割线附近，比如经度90和经度89.9999999会有很大差别。但在线上的点很少，而且这种情况依然能查询到另外一边的最近的点，所以我觉得geohash非常适合这个pj。
这个算法的优点是代码简单且容易维护，准确度高速度快。缺点是分割线上不能保证最优解。但大部分情况有最优解，极小部分有较优解。
验证发现在前四十层分割线上1e-5范围内只有437个点
空间复杂度O(nlogn)
查询复杂度O(logn*E) E为从最hash值最接近的E个点找最近点。
2.2 A*搜索算法
A*搜索用于求指定起点和终点的最短路。估价函数采用当前点到终点的欧几里德距离。实现上用优先队列来弹出 到起点距离+估价值 最小的点，之后把所有相邻点插入优先队列。
这里给大家介绍一种双向A*的算法。
参考文档和完整的文档和源码下载地址：
网友评论