基于C++实现的map-match，使用隐马尔科夫链（HMM），正确率可达到95%
- 数据点、带时间的数据点：使用struct Posi 、 Posi_t。前者用于road里的数据点，后者用于track里的数据点。
- 图：使用邻接表，用vector数组实现。定义struct road存储路段id，数据点个数，路段长度，开始的点，结束的点以及道路等级。里面还有一个Posi型vector存储点信息。
- 轨迹Posi_t的vec组成的vec。
- 格子：长度、数量均可变，用二维vector实现
- 当前的概率与最对应的前置状态：用map实现
- 最短距离：用map<int,double>型的vector，每个map代表始发点，其中第一个int是到达点的id，第二个double是最短路的长度。
-
cqlt_pp_eu：输入两个点，返回二者的欧拉距离。定义为内联函数。
-
read（）：先读取道路信息，忽略道路等级的string，顺便得到道路的长度、道路最西、最南的值。由于输入数据把两条相反的路放在相邻位置，如果是二者终点、起点相同，则二者为友路。然后读取轨迹信息。
-
initial（）：根据read得到的经纬度最小值，结合定义的格子大小，计算每条路上每个点应该属于哪个格子，然后把路的id插入格子里，同时插入周围的8个格子中。插入完成后对格子中去除重复边。
-
no_dunjiao：输入三个点，第一个点是轨迹点，另外两个个是路段起始点。返回一个布尔值，判断路段起始点是否是钝角。都不是则返回false。
-
cqlt_s：输入三个点，返回这三个点对应三角形的面积。
-
cqlt_posi_to_edge，输入一个点和一个边，利用刚刚的面积和路段距离计算该点到此边的距离，并判断垂线是否在路段上。返回路段和点的距离。
-
cqlt_start_to_posi：输入一个点和一条边，返回这个点到路段开始点的距离
-
Dijkstra（）：用优先队列优化的版本。对shortestlens经行修改。首先循环始发点，对于每个始发点，创建一个<double,int>型小端优先队列double是首发点到顶点为int值最短路径长度。每次pop一个pair出来，判断是否经过pair对应的顶点会不会更优。当q为空时、最短路径长度已经超过约定值、已经有50条最短路时就结束，将结果加入shortestlens中。最开始是存路径，用一个单独的函数计算距离。但是这样会带来额外的时间开销。所以直接往map里存距离就行，避免重复计算，直接预处理。但是这样就会带来一个问题，就是有可能会访问到不存在的元素，所以需要判断key是否在map里。
-
cqlt_p2p_onroad：输入2点和2点对应的匹配上的边，利用刚刚的Dijkstra算法得到的路径距离，返回二者在地图上的路径长度。
-
guancegailv：输入一点和一边，根据点和边的距离，以及道路等级，由正态分布概率公式得到观测概率：
-
zhuanyigailv：输入两点两边，计算出两点在地图上的距离dis，然后计算出转移概率。其中β是和t有关的超参，随着两点时间差越来越大，β就越来越大：
-
match：输入一条轨迹，一个空的vector存储前向边，和一个空的vector存储最后的概率。根据轨迹得到所在格子，如果是第一个点就只计算观测概率，之后所有的点还要计算状态转移概率。将遍历每个点的所有边，将状态转移概率与所有前向边概率相乘。然后找到乘积最大的一项，得到对应的前向边与概率，乘观测概率，更新，然后开始下一次遍历。这样结束就得到每一点中所有匹配边的前向边以及最终的概率，这两个就是要修改的“返回值”。
-
print：传入前向边矩阵和最终概率矩阵，找到最大概率的一项，在前向边矩阵中向前遍历，直到最开始。然后输出遍历结果。
1.准确度优化： 1.距离计算：由于1度大概对应111km实际长度，所以会有个系数，让每个点都乘以这个系数，可以得到相应的优化。（有小作用） 2.反向路：在匹配的时候，由于两条相邻的反向路，有可能会带来观测概率的不准确。于是判断道路方向与前进方向是否相同。如果相反，如果这条路有友路，就采用其友路，如果没有友路，就采用长度第二的路。（作用不大） 3.匹配的边的范围：将原来较大的格子缩小为1/3，每次匹配不仅将原来的格子放进去，而且把周围8个格子的边也加进来（作用较大） 4.输出时检查重复边：由于不会绕圈，所以一条边除了相邻时会重复，距离2-5条边如果出现了重复边，那么就应该把这之间的其它边置为当前边。（作用很大） 5.归一化：在匹配过程中，把概率置为0-1之间，避免越乘越小，以至于精度不够。（作用不大） 6.道路等级：由于等级越高的道路数量会越少，所以从概率上将，匹配到高等级的道路概率会略小于普通道路。 7.道路限速：根据轨迹的速度大小与道路限速比较，越接近的就转移概率越大。（作用不大，并且会带了较大的内存开销，会爆内存，因此没有启用） 2.时间优化： 1.采用emplace_back代替push_back，提高性能。（作用不大） 2.在遍历的时候提前得到size，而不是每次都调用size函数（作用不大） 3.在向格子里插入边的时候直接插在周围8个格子里，而不是在匹配过程中加边的时候一个格子一个格子的加边，直接对所在格加边就行（作用很大，不但时间减小，而且内存也显著减小） 4.在向格子里加边完成后对格子里的边去重。（作用非常大，尽管看似比较蠢，但是由于匹配的边数量急剧减少，避免大量重复计算） 5.格子的大小：如果减小每个格子的大小，就会减少边的数量，就减少时间（作用很大，但是会降低准确率） 6.直接在Dijkstra里得到距离，直接预处理出，而不是通过另一个函数计算距离（作用很大） 7.在Dijkstra里，结束的判断标志可以适当减小，与格子长度相匹配（作用很大，还会同时降低空间消耗） 8.在对准确率要求不高的时候关闭准确率优化，可以提高速度。
需要调节的参数一共2个，分别是Dijkstra中的停止距离l，格子的大小h,l和h越大，带来的时间开销就越大，但是准确度就越高。 算法可以达到70、90、93的准确度。 70准确度下，l=0.0005，h=0.001 90准确度下，l=0.0006，h=0.0016 93准确度下，l=0.0008，h=0.0024
假设： 输入的边数为e，顶点数为n，平均每个边有a个顶点； 输入的轨迹数为m，平均每个轨迹有b个顶点； 格子数为x，平均每个格子去重前有y个边，去重后又z个边。 则：
时间复杂度：
- 读入函数复杂度为O（ea+mb）
- 初始化函数复杂度为O（ea+x2ylogy）
- 迪杰斯特拉算法复杂度为O（nzlogz）（由于边数和顶点数大致相等，只会在一个格子大小的范围内dijkstra）
- 每次得到观测概率和状态转换概率的复杂度为O（a），因为要对边逐段分析。
- 每个轨迹的每个点需要匹配O（z2）次，每次都要求状态转移概率（除了第一次）以及观测距离，所以每次匹配的复杂度为O（z2ab）
- 每次输出的的复杂度为O（b+z）
- 一共要匹配m次 因此，程序的时间复杂度为: O（ea+mb+ea+ x2ylogy+ nzlogz+mz2ab+ b+z） = O (ea+m z2ab + x2ylogy+ nzlogz）
空间复杂度：
- 存边的空间复杂度为O（ea）
- 存轨迹的空间复杂度为O（mb）
- 存最短距离的空间复杂度为O（nz）
- 存前向边的空间复杂度为O（mbz2），概率矩阵空间复杂度为O（mz） 因此，程序的空间复杂度为： O（ea+ mb+ nz+ mbz2+ mz） = O（ea+mbz2+nz）