学位论文 > 优秀研究生学位论文题录展示

商空间理论在网络路径分析中研究

作　者: 何富贵
导　师: 张燕平
学　校: 安徽大学
专　业: 计算机应用技术
关键词: 商空间理论粒计算网络路径网络分析
分类号: O242.1
类　型: 博士论文
年　份: 2011年
下　载: 115次
引　用: 1次
阅　读: 论文下载

内容摘要

粒计算理论之一——商空间理论,是张铃、张钹教授模拟人类智能解决问题思路而提出的人工智能求解问题的计算模型。商空间理论通过论域、属性和结构三元组(X,f,T)来描述问题,通过取不同粒,从而建立不同粒度的商空间,形成的一套问题求解的数学模型。其特色是用结构将论域中元素间的联系进行了清晰描述,将论域中的复杂问题转化到不同粒度世界上进行分析,在不同粒度世界之间进行求解,对不同粒度上的解进行合成得到原问题的解,以达到降低问题复杂度的效果。商空间理论作为粒计算的理论方法主要讨论的问题：(1)如何选择合适的粒——投影问题?(2)如何在不同的粒上进行问题求解——推理问题?(3)如何实现不同粒度空间上的解转化到原问题的解——粒度合成问题?商空间理论给出了两个标志性的原理：保假原理和保真原理,保障了问题(2)和(3),对于问题(1)只能在实际应用中具体问题需要具体对待。对于网络路径问题,是图论、人工智能领域的经典问题,其网络的规模决定了其问题的复杂度,也是路径算法的“瓶颈”,近年不少学者通过不同方式分解网络规模来降低计算复杂度,实现网络路径搜索。本文针对网络路径问题应用商空间理论,应用粒度分解方法将网络路径问题分解到不同粒度商空间中,从不同粒度空间形成的分层递阶商空间链中获取网络路径的解。对于网络路径分析,针对不同类型的网络讨论粒的选取问题,提出其路径算法,为网络路径分析提供一个商空间理论问题求解模型。本文的主要工作包括：1.研究商空间理论中粒的选取。在商空间理论中,其取粒度方式有根据论域、属性或结构进行划分三种方法来形成商空间。商空间理论区别于其他粒计算理论,引入了结构作为研究对象的拓扑信息。本文讨论网络结构中的粒的选取问题,针对不同基本类型的网络(无权网络、加权网络、有向网络)的粒的选取进行了讨论。2.提出加权网络的最佳路径。针对加权网络的结构类型的路径问题,根据边权的不同构建等价关系,作为基本粒,将加权网络粒度分解到不同边权上的商空间上,形成分层递阶商空间链,并基于分层递阶商空间链提出加权网络的最佳路径搜索算法。最佳路径通过局部最优实现全局最优,逼近最短路径。通过模拟数据实验验证其最佳路径逼近最短路径,并就成都市交通网络的行车路线对最佳路径和最短路径进行了比较,体现出最佳路径的特色。3.提出基于商空间理论的最短路径方法针对无向无权网络,以极大完全子图作为基本粒,形成相容关系商空间,构造出分层递阶商空间,实现无向无权网络的最短路径搜索。由于极大完全子图的求解具有高计算复杂度,不适合于大中型网络的最短路径求解。就一般网络,基于经典的Dijkstra和Floyd算法改进,提出一种根据网络最短路径步数来求解网络中所有最短路径的方法。4.提出大规模网络的社团最短路径算法。针对大规模网络的网络分析,其网络规模是图论路径算法的瓶颈,本文提出以社团为基本粒的多粒度网络分解方法,将大规模网络粒化为分层递阶商空间,实现大规模网络的预处理。利用分层递阶商空间中的数据信息来计算启发式路径搜索方法的估计函数,以实现大规模网络的点对点最短路径搜索。就多粒度网络分解中的大规模网络分割问题,本文提出的方法是以模块度作为评价准则,以节点网络属性作为启发式信息对网络进行分割,使得子图规模相当且具有社团群聚特征。社团子图规模相当使得经典的图论算法(如最小生成树算法)充分发挥其作用。通过美国不同规模的城市交通网络的实验,证实了以社团为基本粒的多粒度网络分解方法的实用性,并就网络点对点最短路径搜索同A*和ALT算法进行了比较,有一定地优越性。

全文目录

摘要  5-7
Abstract  7-11
目录  11-14
第一章绪论  14-21
  1.1 研究背景和意义  14-15
  1.2 研究现状  15-17
  1.3 论文的主要工作和创新点  17-18
  1.4 论文内容的组织安排  18-21
第二章商空间理论  21-31
  2.1 引言  21-22
  2.2 等价关系商空间理论  22-25
  2.3 相容关系商空间理论  25-26
  2.4 网络粒度选择  26-30
  2.5 本章小结  30-31
第三章商空间理论的最佳路径分析  31-49
  3.1 商空间分层网络模型  31-33
  3.2 最佳路径算法  33-35
  3.3 算法分析  35-42
    3.3.1 算法思想  35-37
    3.3.2 实例分析  37-42
    3.3.3 复杂度分析  42
  3.4 实验  42-47
    3.4.1 人工数据实验  42-45
    3.4.2 实际数据实验  45-47
  3.5 本章小结  47-49
第四章商空间理论在最短路径中的应用  49-69
  4.1 经典算法回顾  49-51
  4.2 无向无权商空间最短路径方法  51-60
    4.2.1 相容关系商空间网络模型  51-54
    4.2.2 搜索方法  54-56
    4.2.3 实例过程  56-60
  4.3 网络多条最短路径算法  60-68
    4.3.1 无权网络最短路径  61-64
    4.3.2 加权网络最短路径  64-68
  4.4 小结  68-69
第五章商空间理论的大规模网络最短路径分析  69-95
  5.1 引言  69-73
  5.2 大规模网络多粒度网络分解  73-76
    5.2.1 大规模网络分析的粒度选择  73-74
    5.2.2 大规模网络的多粒度网络分解  74-76
  5.3 启发式社团分割方法  76-81
    5.3.1 启发式社团分割方法  76-79
    5.3.2 社团核调整和社团合并  79-81
  5.4 大规模网络最短路径搜索  81-83
  5.5 实验  83-94
    5.5.1 与等级分层路径算法比较  83-86
    5.5.2 网络属性分析  86-88
    5.5.3 启发式社团分割分析  88-92
    5.5.4 大规模网络最短路径搜索分析  92-94
  5.6 小结  94-95
第六章总结与展望  95-98
  6.1 总结  95-97
  6.2 展望  97-98
图索引  98-100
Figure Index  100-102
表索引  102-103
Table Index  103-104
参考文献  104-112
致谢  112-113
个人简历学术论文与科研成果  113-115

商空间理论在网络路径分析中研究

内容摘要

全文目录

相似论文