欧氏障碍空间的最短路径问题解法

¹佛山市城市规划勘测设计研究院,佛山市岭南大道北62号528000;²武汉大学资源与环境科学学院,武汉市珞喻路129号430079;³安徽大学资源与环境科学学院,合肥市九龙路111号230601;⁴湖北省交通运输厅通信信息中心,武汉市建设大道428号430030

基金项目: 国家自然科学基金资助项目(40701155);;国家863计划资助项目(2009AA12Z224)

详细信息

Solution of Euclidean Shortest Path Problem Space with Obstacles

¹ Foshan Urban Planning Design and Surveying Research Institute,North 62 Lingnan Road,Foshan 528000,China;² School of Resources and Environmental Science,Wuhan University,129 Luoyu Road,Wuhan 430079,China;³ School of Resources and Environmental Science,Anhui University,111 Jiulong Road,Hefei 230601,China;⁴ Communications Inalformation Center,Department of Transportation of Hubei Province,428 Jianshe Avenue,Wuhan 430030,China

Funds: 国家自然科学基金资助项目(40701155);;国家863计划资助项目(2009AA12Z224)

摘要: 提出了利用地图代数栅格路径距离变换原理求解欧氏障碍空间最短路径问题的方法(MA-ESPO),实现了二维障碍空间最短路径的一个栅格解法,并且把障碍物、源、汇图形都扩大到任意形态图形。给出了基于地图代数的障碍空间下距离变换方法(MA-DTO),其简便地生成了整个障碍空间所有点的趋源距离,从而成为E2生成所定义障碍空间下各任意形态图形的Voronoi图的实际方法。
- 障碍空间 /
- 最短路径 /
- 网络分析 /
- NP难 /
- 地图代数 /
- 栅格路径
Abstract: MA-ESPO method was put forward.Both in theory and in experiments,MA-ESPO can completely resolve 2D ESPO in raster method.Further more,obstacles,source shapes and destination shapes in MA-ESPO can be shapes in all form.It's the generalized solution of the method Dijkstra.MA-DTO(map algebra-distance transformation with obstacles) that actually generates all distance toward fountain of all points in the whole obstacle space was given at last.This method prepares the key work of finding shortest path for all points in the space,thereby comes to be the key technique for Voronoi generation of arbitrarily shaped figures in E2 obstacle space.
- space with obstacles /
- shortest path /
- network analysis /
- NP-hard /
- map algebra /
- path between two raster centers