HIT算法设计课程阅读报告.docx

Reading3提出了一种新颖实用的解决方案COLA,用于在大型道路网络上进行基于指数的近似CSP处理。COLA主要利用道路网络的两个重要属性。首先,真实的道路网络通常(大致)是平面的,因此可以有效地分割成分区,每个分区仅包含相对较少数量的边界顶点。因此,COLA分区网络,在分区上构建覆盖图,并在边界顶点对之间索引一组选定路径。其次,在实践中,在道路网络中经常存在相对少量的标志性顶点,这些顶点通常出现在CSP结果中。