一种基于商空间覆盖模型的最短路径搜索方法

摘要

本发明公开了一种基于商空间覆盖模型的最短路径搜索方法，特征是先构建由一递阶商空间覆盖网络链中各商空间覆盖网络的所有极大完全子图和其对应于初始网络的节点信息构成的商空间覆盖模型，依据商空间覆盖模型获得要搜索的起、终点在不同商空间覆盖网络的极大完全子图中对应位置的分层编号，比较其分层编号，从粒度较细商空间中搜索路径，逐步细化商空间，直到粒度最细商空间，求得两节点的最短路径，从而解决无向无权网络中最短路径的快速搜索问题，且可同时求出网络中多条最短路径；利用本方法求两点间的最短路径，可达到网络资源的综合利用，解决交通网络中乘客最少换乘次数，电力网络中能源的有效利用和帮助快速故障路径检测等问题。

主权项

一种基于商空间覆盖模型的最短路径搜索方法，首先对初始网络中的节点按照一定的顺序标号，根据无向无权网络极大完全子图的特征形成递阶商空间覆盖网络链；其特征在于：从无向无权连通网络中作为粒度最细、第0级商空间覆盖网络的初始网络开始，搜索网络中所有的极大完全子图，以极大完全子图为节点，两极大完全子图的节点间有公共节点或边，定义两节点相连，得到粒度较粗的商空间覆盖，为初始网络的一级商空间覆盖网络；然后再求初始网络的一级商空间覆盖网络的所有极大完全子图，并记录极大完全子图对应于初始网络中的节点信息，以该级的极大完全子图为节点、两极大完全子图的节点间有公共节点或边定义为两节点相连，得到粒度较粗的商空间覆盖，构成初始网络的二级商空间覆盖网络，求初始网络的二级商空间覆盖网络的所有极大完全子图，并记录该级的极大完全子图对应于初始网络中的节点信息；继续依此操作直至在商空间覆盖网络的极大完全子图对应于初始网络的节点信息中初始网络的任意两节点对都在同一个极大完全子图中；各商空间覆盖网络按构成先后顺序排列形成一个递阶商空间覆盖网络链；按递阶商空间覆盖网络链的顺序，记录各个商空间覆盖网络的所有极大完全子图和各个极大完全子图对应于初始网络的节点信息为商空间覆盖模型；对于无向无权的不连通网络，先求出各个连通分支，再对每个连通分支按无向无权连通网络来求解其商空间覆盖模型；从而得到一个递阶商空间覆盖网络链中各个商空间覆盖网络的所有极大完全子图构成的极大完全子图集和极大完全子图对应于初始网络的节点信息的商空间覆盖模型；然后在此商空间模型基础上进行路径搜索：在商空间模型的极大完全子图对应于初始网络的节点信息中找出要搜索的起点和终点在不同商空间覆盖网络的极大完全子图集中的对应位置的分层编号，并在分层编号前面加上附加在初始网络中的标号，比较初始网络起点和终点的分层编号，找出自左到右方向其编号相等的第一个位置，找到在递阶商空间覆盖网络链中的对应商空间覆盖网络极大完全子图集；再从其在递阶商空间覆盖网络链中左边邻居的商空间覆盖网络开始搜索初始网络起点到终点的路径，其路径用分层编号中该起点和终点所分别对应的编号来表示，接着再搜索初始网络起点到终点在其左边邻居商空间覆盖网络中的路径，其路径的起点和终点是分层编号对应的编号，中间节点是递阶商空间覆盖网络链中右边邻居的商空间覆盖网络中得到路径的从左到右两节点的交集；依次类推，直到递阶商空间覆盖网络链中最左边的商空间覆盖网络即为初始网络，实现从粗粒度商空间覆盖网络逐步搜索到细粒度商空间的过程，从而得到初始网络的起点到终点的最短路径。