-
公开(公告)号：CN101788999A
公开(公告)日：2010-07-28
申请号：CN200910251662.5
申请日：2009-12-30
Applicant: 安徽大学
IPC: G06F17/30
Abstract: 本发明公开了一种网络图中最短路径的二分查找追踪方法，特征是根据最短路径步数矩阵提取源节点到汇节点的最短路径步数，对其折半拆分为前、后步数；在最短路径步数矩阵的源节点行向量中搜索步数等于前步数的节点，为前步数节点集；在最短路径步数矩阵的汇节点列向量中搜索步数等于后步数的节点，为后步数节点集；取前、后步数节点集的交集为中间节点；以交集中每节点为基准，用上述方法求源节点与该节点、该节点与汇节点的中间节点，直到需求解节点间最短路径步数为1为止；将所求的中间节点顺次插到对应位置得源到汇节点的所有最短路径；利用本发明方法查找两点间所有最短路径，可对应于实际数据中抽象出网络图的择优路径选择提供多种方案。
-
公开(公告)号：CN101114968A
公开(公告)日：2008-01-30
申请号：CN200710131394.4
申请日：2007-08-31
Applicant: 安徽大学
Abstract: 本发明基于复杂网络商空间模型的路径搜索方法，特征是先利用等价关系对网络进行逐步粗化分类，构成递阶商空间链，得到每个节点的分层编号的商空间模型；然后在商空间模型中找到要搜索的起点和终点的分层编号，根据对应递阶商空间链中从细到粗的商空间，从最后一个编号开始比较，从粒度最粗的商空间开始搜索两点的连通路径，接着在较粗的商空间中搜索细的商空间，一直到最细的商空间为止，根据任意两节点的分层编号可以直观的发现两节点的“最佳路径”的路径分布状况，根据其递阶商空间链可以找出网络中任意两节点的“最佳路径”；再依据该模型从最粗的商空间开始搜索两点的连通路径，逐步细化，一直到搜索到最细的商空间，搜索出“最佳路径”。
-
Patent Agency Ranking
公开(公告)号：CN101330457A
公开(公告)日：2008-12-24
申请号：CN200810021103.0
申请日：2008-07-24
Applicant: 安徽大学
Abstract: 本发明公开了一种基于商空间覆盖模型的最短路径搜索方法，特征是先构建由一递阶商空间覆盖网络链中各商空间覆盖网络的所有极大完全子图和其对应于初始网络的节点信息构成的商空间覆盖模型，依据商空间覆盖模型获得要搜索的起、终点在不同商空间覆盖网络的极大完全子图中对应位置的分层编号，比较其分层编号，从粒度较细商空间中搜索路径，逐步细化商空间，直到粒度最细商空间，求得两节点的最短路径，从而解决无向无权网络中最短路径的快速搜索问题，且可同时求出网络中多条最短路径；利用本方法求两点间的最短路径，可达到网络资源的综合利用，解决交通网络中乘客最少换乘次数，电力网络中能源的有效利用和帮助快速故障路径检测等问题。
-
公开(公告)号：CN101114967A
公开(公告)日：2008-01-30
申请号：CN200710131393.X
申请日：2007-08-31
Applicant: 安徽大学
Abstract: 本发明复杂网络商空间模型的构建方法，特征是利用商空间理论中的等价关系对网络进行逐步粒度粗化分类，形成一个递阶商空间链，再根据每个节点在递阶商空间链上不同商空间中的位置给出各节点的分层编号，形成复杂网络商空间模型。根据本发明构建的复杂网络商空间模型中任意两节点的分层编号可以直观地找出两节点的“最佳路径”的路径分布状况，并可根据其递阶商空间链找出网络中任意两节点的“最佳路径”。依据该模型可从粒度最粗的商空间开始搜索两点的连通路径，逐步细化，一直到搜索到粒度最细的商空间，从而可快速搜索出任意两点的“最佳路径”；还可利用计算机来构建复杂网络商空间模型和快速搜索复杂网络中的“最佳路径”。
-
公开(公告)号：CN100542117C
公开(公告)日：2009-09-16
申请号：CN200710131394.4
申请日：2007-08-31
Applicant: 安徽大学
Abstract: 本发明基于复杂网络商空间模型的路径搜索方法，特征是先利用等价关系对网络进行逐步粗化分类，构成递阶商空间链，得到每个节点的分层编号的商空间模型；然后在商空间模型中找到要搜索的起点和终点的分层编号，根据对应递阶商空间链中从细到粗的商空间，从最后一个编号开始比较，从粒度最粗的商空间开始搜索两点的连通路径，接着在较粗的商空间中搜索细的商空间，一直到最细的商空间为止，根据任意两节点的分层编号可以直观的发现两节点的“最佳路径”的路径分布状况，根据其递阶商空间链可以找出网络中任意两节点的“最佳路径”；再依据该模型从最粗的商空间开始搜索两点的连通路径，逐步细化，一直到搜索到最细的商空间，搜索出“最佳路径”。
-
公开(公告)号：CN101330457B
公开(公告)日：2011-03-23
申请号：CN200810021103.0
申请日：2008-07-24
Applicant: 安徽大学
Abstract: 本发明公开了一种基于商空间覆盖模型的最短路径搜索方法，特征是先构建由一递阶商空间覆盖网络链中各商空间覆盖网络的所有极大完全子图和其对应于初始网络的节点信息构成的商空间覆盖模型，依据商空间覆盖模型获得要搜索的起、终点在不同商空间覆盖网络的极大完全子图中对应位置的分层编号，比较其分层编号，从粒度较细商空间中搜索路径，逐步细化商空间，直到粒度最细商空间，求得两节点的最短路径，从而解决无向无权网络中最短路径的快速搜索问题，且可同时求出网络中多条最短路径；利用本方法求两点间的最短路径，可达到网络资源的综合利用，解决交通网络中乘客最少换乘次数，电力网络中能源的有效利用和帮助快速故障路径检测等问题。
-
公开(公告)号：CN101330417A
公开(公告)日：2008-12-24
申请号：CN200810021101.1
申请日：2008-07-24
Applicant: 安徽大学
Abstract: 本发明公开了一种无向无权网络的商空间覆盖模型及其构建方法，特征是利用商空间理论和相容关系对网络求极大完全子图，逐步粒度粗化形成一递阶商空间覆盖网络链，得到粒度由细到粗的各级商空间覆盖网络所有极大完全子图及其在初始网络中的节点信息而形成的商空间覆盖模型；根据该商空间覆盖模型中各级商空间覆盖网络的极大完全子图在初始网络中的节点信息，可直观找出网络的两节点间的最短路径长度，根据模型可以找到初始网络两节点在不同粒度商空间覆盖网络的位置，从粒度粗的商空间覆盖网络开始搜索两点间的连通路径，逐步细化，一直到搜索到粒度最细的商空间，从而可快速搜索出任意两点的最短路径；还可利用计算机来构建商空间覆盖模型。
-
-
-
-
-
-
Search Results
7
records
(took 0.029 seconds)
