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

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

杨传勇, 胡海, 胡鹏, 曹枫

文章导航 > 武汉大学学报 ● 信息科学版 > 2012 > 37(12): 1495-1499

杨传勇, 胡海, 胡鹏, 曹枫. 欧氏障碍空间的最短路径问题解法[J]. 武汉大学学报 ● 信息科学版, 2012, 37(12): 1495-1499.

引用本文:

杨传勇, 胡海, 胡鹏, 曹枫. 欧氏障碍空间的最短路径问题解法[J]. 武汉大学学报 ● 信息科学版, 2012, 37(12): 1495-1499.

YANG Chuanyong, HU Hai, HU Peng, CAO Feng. Solution of Euclidean Shortest Path Problem Space with Obstacles[J]. Geomatics and Information Science of Wuhan University, 2012, 37(12): 1495-1499.

Citation:

YANG Chuanyong, HU Hai, HU Peng, CAO Feng. Solution of Euclidean Shortest Path Problem Space with Obstacles[J]. Geomatics and Information Science of Wuhan University, 2012, 37(12): 1495-1499.

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

杨传勇¹,
胡海²,
胡鹏^2,3,
曹枫⁴

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

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

作者简介:
杨传勇，高级工程师，博士，现主要从事智能交通和３Ｓ集成理论和技术研究。

中图分类号: P208

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

[1]	李改肖, 吕程, 彭认灿, 董箭. 一种利用双侧凸包扩张模型的路径快速规划算法 . 武汉大学学报 ● 信息科学版, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
[2]	徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕. 利用等距同构建立多尺度空间实体相似性度量模型 . 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
[3]	汤青慧, 唐旭, 崔晓晖, 胡石元, 刘耀林. 基于动态通达网络模型的最优航程规划方法 . 武汉大学学报 ● 信息科学版, 2015, 40(4): 521-528. doi: 10.13203/j.whugis20140387
[4]	王伟, 漆炜, 陈能成, 杨国诚. 顾及地价空间分布规律的城市基准地价以价定级方法研究 . 武汉大学学报 ● 信息科学版, 2011, 36(6): 747-751.
[5]	呙维, 龚健雅, 朱欣焰. 一种基于层次拓扑模型的分布式最短路径算法 . 武汉大学学报 ● 信息科学版, 2009, 34(7): 864-868.
[6]	白轶多, 胡鹏, 夏兰芳, 郭峰林. 关于k次短路径问题的分析与求解 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 492-494.
[7]	王海军, 关兴良, 夏文芳. 顾及障碍空间的城镇土地定级方法研究 . 武汉大学学报 ● 信息科学版, 2008, 33(1): 97-100.
[8]	胡鹏, 范青松, 胡海. 椭球上的测地变换和Voronoi图的生成——地理空间度量 . 武汉大学学报 ● 信息科学版, 2007, 32(9): 825-828.
[9]	王海军. 基于注水模型的网络分析方法研究 . 武汉大学学报 ● 信息科学版, 2007, 32(5): 419-422.
[10]	胡海, 刘经南. 障碍空间最大空隙的地图代数解法MA-MAXG(Ω) . 武汉大学学报 ● 信息科学版, 2006, 31(8): 700-703.
[11]	胡鹏, 李圣权, 亢江妹. 空间数据问题与GIS发展的思考 . 武汉大学学报 ● 信息科学版, 2005, 30(9): 796-800.
[12]	胡鹏, 刘沛兰, 胡海, 杨传勇. 地球信息的度量空间和Global GIS . 武汉大学学报 ● 信息科学版, 2005, 30(4): 317-321.
[13]	胡鹏, 耿协鹏, 曹枫. 图形的形态变换和地图代数凸壳算法 . 武汉大学学报 ● 信息科学版, 2005, 30(11): 1003-1007.
[14]	祝国瑞, 唐旭, 王平. 基于影响特征的点状定级因素分析 . 武汉大学学报 ● 信息科学版, 2004, 29(8): 736-739,751.
[15]	翁敏, 毋河海, 杜清运, 蔡忠亮. 基于公交网络模型的最优出行路径选择的研究 . 武汉大学学报 ● 信息科学版, 2004, 29(6): 500-506.
[16]	胡鹏, 杨传勇, 胡海, 李圣权. GIS的基本理论问题——地图代数的空间观 . 武汉大学学报 ● 信息科学版, 2002, 27(6): 616-621.
[17]	刘耀林, 范延平, 唐旭. 最短路径方法在土地定级中的应用 . 武汉大学学报 ● 信息科学版, 2000, 25(6): 510-515,557.
[18]	乐阳, 龚健雅. Dijkstra最短路径算法的一种高效率实现 . 武汉大学学报 ● 信息科学版, 1999, 24(3): 208-212.
[19]	游涟, 张洁. 地图代数系统居民地编绘工艺过程及评价 . 武汉大学学报 ● 信息科学版, 1996, 21(1): 69-72.
[20]	李秋萍, 陈宇, 栾学晨. 利用网络游记分析不同类型游客的旅游流网络特征差异——以云南省为例 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20210045

WeChat

点击查看大图

计量

文章访问数: 1058
HTML全文浏览量: 29
PDF下载量: 799
被引次数: 0

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

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

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

作者简介:
杨传勇，高级工程师，博士，现主要从事智能交通和３Ｓ集成理论和技术研究。

收稿日期: 2012-09-08
刊出日期: 2012-12-05

中图分类号: P208

关键词:

摘要: 提出了利用地图代数栅格路径距离变换原理求解欧氏障碍空间最短路径问题的方法(MA-ESPO),实现了二维障碍空间最短路径的一个栅格解法,并且把障碍物、源、汇图形都扩大到任意形态图形。给出了基于地图代数的障碍空间下距离变换方法(MA-DTO),其简便地生成了整个障碍空间所有点的趋源距离,从而成为E2生成所定义障碍空间下各任意形态图形的Voronoi图的实际方法。

English Abstract

杨传勇, 胡海, 胡鹏, 曹枫. 欧氏障碍空间的最短路径问题解法[J]. 武汉大学学报 ● 信息科学版, 2012, 37(12): 1495-1499.

引用本文:

杨传勇, 胡海, 胡鹏, 曹枫. 欧氏障碍空间的最短路径问题解法[J]. 武汉大学学报 ● 信息科学版, 2012, 37(12): 1495-1499.

YANG Chuanyong, HU Hai, HU Peng, CAO Feng. Solution of Euclidean Shortest Path Problem Space with Obstacles[J]. Geomatics and Information Science of Wuhan University, 2012, 37(12): 1495-1499.

Citation:

YANG Chuanyong, HU Hai, HU Peng, CAO Feng. Solution of Euclidean Shortest Path Problem Space with Obstacles[J]. Geomatics and Information Science of Wuhan University, 2012, 37(12): 1495-1499.

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

我要投稿

投稿攻略

联系我们

二维码