论文部分内容阅读
欧氏障碍空间的最短路径问题(ESPO:Euclidean space Shortest Path with Obstacles)问题是网络分析中基础和核心问题一最短路径问题的更广义问题,是图论、S计算几何、网络设计、网络最优化等领域的基本理论问题,其中三维ESPO是NP-难问题,至今无其它有效解。它的突破将具有重要科学意义和巨大经济价值。本论文针对这一问题,进行了重要研究。 本论文分析了空间数据的基本特征以及空间数据的表达模型,提出了空间数据的“位”、“邻”、“近”、“势”的概念,完善了空间关系的描述。提出了空间衍生数据显式初始化带来的运算、存贮开销,以及对复杂、动态、连续地理过程的分析处理的不适应性,从整体上提出了当前GIS的空间分析存在的空间复杂性理论问题。 提出了新型“矢—栅”紧密结合型数据模型:“矢量为体,栅格为用,矢栅互换,利用长处”,这是一条新型GIS的建设路线。论述它全面解决空间问题的可行性、动态性、规范性,并给出了地图代数的“栅→矢”新方法和“矢→栅”中经典方法构成了一对“矢栅互换”支撑技术。并以三维形体集合运算,结合复杂的三维ESPO空间分析,三维点集精密绘图,在主要关键上给出了它的实验论证。 本文提出了MA—ESPO方法。理论上和实验上解决了著名的二维、三维障碍空间最短路径ESPO问题,并且把障碍物、源、汇图形都扩大到全形态图形,是著名Dijkstra问题的广义解。它是以地图代数栅格路径距离变换原理为基础发展、拓广而成,在理论上论证了该方法能在任意有限的障碍空间内,以指定精度,有效实现最短路径;在算法中实现了模板(2k+1)~3中正整数k动态扩大的自动机制和算法;并提供了大区域分段、分块技术作业的理论和技术保证:其时间复杂性为O(kn),k为不大的常数(其决定于区域大小的小型模板中元素);空间复杂性为O(n)。 给出了MA-ESPO统一方法实验软件。它在二维上,能提供3000~2范围内障碍空间最短路径ESPO广义问题解决实验验证,三维上,能提供200~3范围内障碍空