大规模图上的最短路径问题研究
| 摘要 | 第1-7页 |
| ABSTRACT | 第7-10页 |
| 目录 | 第10-14页 |
| 表格 | 第14-15页 |
| 插图 | 第15-17页 |
| 算法 | 第17-18页 |
| 第一章 绪论 | 第18-30页 |
| 本章概要 | 第18页 |
| ·最短路径问题 | 第18-20页 |
| ·最短路径算法面临的挑战 | 第18-19页 |
| ·最短路径算法的研究趋势 | 第19-20页 |
| ·并行计算 | 第20-25页 |
| ·并行计算机体系结构 | 第20-21页 |
| ·并行程序编程模型 | 第21-22页 |
| ·并行程序优化 | 第22-25页 |
| ·论文的研究思路、内容和成果 | 第25-27页 |
| ·论文的研究思路和成果 | 第25-26页 |
| ·论文的组织结构 | 第26-27页 |
| ·论文中使用的数据集 | 第27页 |
| ·本章小结 | 第27-30页 |
| 第二章 最短路径算法综述 | 第30-50页 |
| 本章概要 | 第30页 |
| ·模型与问题描述 | 第30-31页 |
| ·图的定义与模型 | 第30-31页 |
| ·问题描述 | 第31页 |
| ·单源最短路径算法 | 第31-35页 |
| ·经典单源最短算法 | 第31-32页 |
| ·经典算法的优化 | 第32-34页 |
| ·经典算法的性能评测 | 第34-35页 |
| ·点到点的最短路径算法 | 第35-46页 |
| ·分层算法 | 第35-40页 |
| ·目标制导算法 | 第40-45页 |
| ·算法在静态图上的性能评测 | 第45-46页 |
| ·算法的理论分析 | 第46页 |
| ·基于动态图和时间依赖图的算法 | 第46页 |
| ·多源最短路径算法 | 第46-47页 |
| ·多源点到多汇点的最短路径算法 | 第46-47页 |
| ·全源最短路径算法 | 第47页 |
| ·并行算法 | 第47-49页 |
| ·基于CPU的并行算法 | 第48页 |
| ·基于GPU的并行算法 | 第48-49页 |
| ·本章小结 | 第49-50页 |
| 第三章 稀疏图上的全源最短路径算法优化 | 第50-70页 |
| 本章概要 | 第50页 |
| ·引言 | 第50-52页 |
| ·问题描述 | 第50页 |
| ·稀疏图上的全源最短路径算法 | 第50-51页 |
| ·相关定理 | 第51-52页 |
| ·利用增量计算优化标号修正算法 | 第52-60页 |
| ·优化标号初值 | 第52-55页 |
| ·进一步优化标号初值 | 第55-57页 |
| ·标号初始值对松弛算法性能的影响 | 第57-60页 |
| ·利用增量计算优化全源最短路径算法 | 第60-68页 |
| ·空间性能 | 第60-65页 |
| ·算法描述 | 第65-67页 |
| ·实验结果及分析 | 第67-68页 |
| ·本章小结 | 第68-70页 |
| 第四章 基于预处理的目标制导下界算法 | 第70-88页 |
| 本章概要 | 第70页 |
| ·引言 | 第70-71页 |
| ·问题描述 | 第70页 |
| ·研究概况 | 第70-71页 |
| ·目标制导下界算法 | 第71-75页 |
| ·A~*算法及其理论基础 | 第71-73页 |
| ·ALT算法 | 第73-75页 |
| ·ACT算法 | 第75-80页 |
| ·选取中心点 | 第76-77页 |
| ·利用REACH算法剪枝 | 第77-78页 |
| ·算法描述 | 第78-80页 |
| ·实验结果及分析 | 第80-85页 |
| ·预处理的时空性能分析 | 第80-81页 |
| ·参数选择 | 第81-83页 |
| ·性能比较 | 第83-85页 |
| ·本章小结 | 第85-88页 |
| 第五章 路网上的近似kNN检索 | 第88-96页 |
| 本章概要 | 第88页 |
| ·移动对象的k近邻(kNN)检索 | 第88-90页 |
| ·相关工作 | 第89页 |
| ·路网模型和问题描述 | 第89-90页 |
| ·近似kNN检索 | 第90-92页 |
| ·路网上的近似距离 | 第90-91页 |
| ·选取代表顶点集合 | 第91-92页 |
| ·kNN查询 | 第92页 |
| ·实验结果 | 第92-94页 |
| ·本章小结 | 第94-96页 |
| 第六章 OpenCL平台上的并行算法优化 | 第96-110页 |
| 本章概要 | 第96页 |
| ·基于OpenCL的异构计算 | 第96-102页 |
| ·OpenCL的概念 | 第96-97页 |
| ·平台模型 | 第97页 |
| ·执行模型 | 第97-98页 |
| ·内存模型 | 第98-100页 |
| ·编程模型 | 第100-102页 |
| ·基于OpenCL的并行单源最短路径算法优化 | 第102-106页 |
| ·现有算法 | 第102-104页 |
| ·改进 | 第104-106页 |
| ·实验结果分析 | 第106-107页 |
| ·本章小结 | 第107-110页 |
| 第七章 总结 | 第110-112页 |
| ·总结 | 第110-111页 |
| ·进一步的工作 | 第111-112页 |
| 参考文献 | 第112-122页 |
| 致谢 | 第122-124页 |
| 攻读博士期间发表的学术论文 | 第124页 |
