1. 概述

CH(Contraction Hierarchies)是道路网络最短路径算法之一，其应用收缩(contract)节点的方法将节点分层，显著提高了最短路径的搜索速度。

CH算法涵盖数据预处理和路径搜索两个方面，预处理通过收缩节点生成路网图的层次结构，搜索过程利用层次图搜索

理解CH算法需要弄懂两个问题：

• 怎么通过收缩(contract)节点
• 怎么在分层后的网络中进行路径查询

2. 整理思想

• 道路网形成的带权有向图G(V,E,c)是一个平面结构
• 对于路网图G中的节点，按照某些维度、对每个节点都定义一个优先级level，某种程度上可以认为这个优先级就是节点在图G中的重要性
• 然后沿垂直方向将图中的每个节点做沉降，使得每个节点在垂直方向上的高度与其在图G中的优先级一致，沿着节点的高度形成层次结构
• 寻找s→t的最短路径时，分别从s和t做正向和反向Dijkstra，Dijkstra的每一步都沿着高度大于当前节点高度的方向搜索，形成两个端点开始向上爬图的搜索过程，双方相遇的某个顶点即为最短路径。由此降低节点搜索规模、加速搜索性能
• 由于G中搜索是向上方向，因此当沉降某个节点v破坏了剩余节点的连通性和最短距离时，需要在剩余节点中添加shortcut边E’保持图的语义不变，形成图G*(V,E+E’,c+c’)

综述

• 以CH为代表的strong hierarchy 算法，依赖于道路等级特性进行数据预处理，响应时间快，对于等级特性差的metric加速效果变差(最短距离比最短时间慢10倍)，缺点是不能很好的支持各种metric
• 以A*、ALT为代表目标启发式算法，算法特点是相比CH,可以更好的支持多种metric，算法缺点是响应时间较慢
• 基于图分割的路径规划算法，把路网处理为多层overlay graph,算法的特点是图分割和响应时间和metric相互独立，适用于CRP算法的设计思路

业界应用现状

前几日，一个刚学编程的老朋友问了我一个问题：

int i = 0;
i = i ++;
printf(“%d\n”, i);

为什么打印i的值是1而不是0？

这种undefined的问题在网上是讨论烂了的。一般会纠结这种问题的同学，多半是看了本烂书。

我给这位老朋友看了一篇裘宗燕先生的文章，他立马就明白了问题所在，并不再纠结于类似的问题了。

1996年，公牛vs超音速第六场，那一年我还未满6岁，观看的第一场NBA比赛，最终87比75，乔丹获得了复出后的第一座冠军奖杯，正式拉开了他第二个三连冠的序幕。

1997年，公牛4比2战胜了爵士，总冠军。

1998年，同样是4比2，公牛战胜了爵士，乔丹第二个三连冠。在后来的好多年记忆里，我对乔丹的画面都定格在这第六战的最后一刻：

比赛还剩下22.7秒，卡尔马龙在低位三秒区附近要位，接到斯托克顿的传球，准备背身单打，此刻，乔丹鬼魅般的出现在他身后，断下了球。接着缓慢运球推进到前场，看了看计时器，大约还剩10秒的时候，压低重心，一个加速启动向右前方突破，然后突然拉回，跳投命中，已经被晃开的拜伦拉塞尔只能无奈的看着这一切。

接着，乔丹退役了。

年幼时的小孩，不知愁滋味，只是发觉没有了乔丹的NBA似乎没什么意思了，再也找不到一个打球像他那么飘逸灵动，仿佛只要他在场就不担心会输球的球员了。以至于在后来好多年里，在我眼里的篮球明星只有乔丹一人。

然而，有意思的是，同样是1996年，也就是我开始看球的第一年，一个叫做科比布莱恩特的小伙子来到了NBA。

本文整理自之前我在公司内部培训上的演讲ppt

编译概要

阶段：

• 词法分析
• 语法分析
• 语义分析
• 代码优化
• 代码生成

划分：

• 编译前端，包括词法分析、语法分析、语义分析
• 编译后端，包括代码优化、代码生成

流程：