原文传递
一种基于商空间覆盖模型的最短路径搜索方法
| 专利名称： | 一种基于商空间覆盖模型的最短路径搜索方法 |
| 摘要： | 本发明公开了一种基于商空间覆盖模型的最短路径搜索方法，特征是先构建由一递 阶商空间覆盖网络链中各商空间覆盖网络的所有极大完全子图和其对应于初始网络的节 点信息构成的商空间覆盖模型，依据商空间覆盖模型获得要搜索的起、终点在不同商空 间覆盖网络的极大完全子图中对应位置的分层编号，比较其分层编号，从粒度较细商空 间中搜索路径，逐步细化商空间，直到粒度最细商空间，求得两节点的最短路径，从而 解决无向无权网络中最短路径的快速搜索问题，且可同时求出网络中多条最短路径；利 用本方法求两点间的最短路径，可达到网络资源的综合利用，解决交通网络中乘客最少 换乘次数，电力网络中能源的有效利用和帮助快速故障路径检测等问题。 |
| 专利类型： | 发明专利 |
| 国家地区组织代码： | 安徽;34 |
| 申请人： | 安徽大学 |
| 发明人： | 何富贵;张燕平;张 铃;赵 姝 |
| 专利状态： | 有效 |
| 申请日期： | 2008-07-24T00:00:00+0800 |
| 发布日期： | 2019-01-01T00:00:00+0800 |
| 申请号： | CN200810021103.0 |
| 公开号： | CN101330457 |
| 分类号： | H04L12/56(2006.01)I |
| 申请人地址： | 230039安徽省合肥市肥西路3号 |
| 主权项： | 1、一种基于商空间覆盖模型的最短路径搜索方法，根据无向无权网络极大完全子图 的特征形成递阶商空间覆盖网络链；其特征在于：从无向无权连通网络中作为粒度最细、 第0级商空间覆盖网络的初始网络开始，搜索网络中所有的极大完全子图，以极大完全 子图为节点，两极大完全子图的节点间有公共节点或边，定义两节点相连，得到粒度较 粗的商空间覆盖，为初始网络的一级商空间覆盖网络；然后再求初始网络的一级商空间 覆盖网络的所有极大完全子图，并记录极大完全子图对应于初始网络中的节点信息，以 该级的极大完全子图为节点、两极大完全子图的 |
| 所属类别： | 发明专利 |
检索历史
应用推荐
