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

暂无

一种基于商空间覆盖模型的最短路径搜索方法 \n技术领域\n[0001] 本发明属于网络拓扑技术领域，具体涉及一种无向无权网络最短路径搜索方法，\n特别是基于商空间覆盖模型的路径搜索方法。 \n背景技术\n[0002] 对于求解网络拓扑的最短路径问题，典型的算法是迪杰斯特拉(Dijkstra)算法\n和弗洛伊德(Floyd)算法，Dijkstra算法适合于求解单源点最短路径问题，Floyd算法在求\n解所有点之间的最短路径效果比较好，但这两种方法对于最短路径搜索问题都属于试探型\n搜索算法，其搜索过程没有给定搜索目标和方向。 \n[0003] 在互联(Internet)网技术中，网络路由器的选择问题上目前还是以Dijkstra算\n法来选择最短路径；在交通网络、特别是数字化交通地图中，为了使用户能在任意的起点与终点之间找出最短线路，其系统的功能实现上最主要的是最短路径算法的设计，目前还是\n以Dijkstra算法为主；在电力网络中快速故障路径检测和路径选择中，至今还是用试探型\n搜索算法来求解最短路径的思想来解决问题；对于大型网络，这试探型搜索算法算法影响\n实际环境下的应用效果。 \n[0004] 据《问题求解理论及应用-商空间粒度计算理论及应用》(第2版)(清华大学出\n版社，张铃、张钹著，2007年3月第2版，第1-6，12-14，27-36，38-39，90-105页)介绍，商空间理论的粒度思想模仿了人类采用概略地、由粗到细、不断求精的多粒度分析法。至今对于最短路径搜索问题的粒度分析法还只是数学领域上的一般形式，尚未涉及具体的分类算\n法。 \n[0005] 专利申请号为20071013393.x的《一种复杂网络商空间模型的构建方法》就可抽\n象为无向加权网络的实际对象，根据网络中边上权值的不同利用等价关系对节点粒度分\n类，形成一系列不同权值上的网络，把这些不同粒度上的网络看成是初始网络的商空间网\n络，按照边上权值由大到小排序商空间网络形成一个递阶商空间链。这种复杂网络商空间\n模型挖掘出了网络中隐藏的信息，为复杂对象的最佳路径问题求解提供了方便。专利申请\n号为20071013394.4的《一种基于复杂网络商空间模型的路径搜索方法》根据复杂网络商\n空间模型提出了一种快速最佳路径搜索方法。但这两个专利申请是就可抽象为无向加权网\n络的实际对象的最佳路径问题来讨论的，而可抽象为无向无权网络的实际对象因为其结构\n特点是相容关系的特征，无法根据等价关系来构建模型。其搜索方法是求解最佳路径，无法获得无向无权网络中的最短路径。 \n[0006] 据《离散数学》(第2版)(国防工业出版社，于筑国编著，2007年11月，第115-117页)中的相容关系，也只是定义了相容关系和覆盖，阐述了相容关系和完全覆盖的一一对\n应关系，但没有将相容关系、完全覆盖应用到最短路径的搜索问题上，其中相容关系中的完全覆盖即为网络拓扑中的极大完全子图。 \n[0007] 至今对于大规模复杂网络的最短路径搜索方法还是经典的Dijkstra算法和\nFloyd算法，未见将商空间理论和粒度计算应用到网络最短路径搜索问题上。\n发明内容\n[0008] 本发明目的是提出一种基于商空间覆盖模型的最短路径搜索方法，以解决无向无\n权网络中最短路径的快速搜索问题。 \n[0009] 本发明基于商空间覆盖模型的最短路径搜索方法，首先对初始网络中的节点按照\n一定的顺序标号，根据无向无权网络极大完全子图的特征形成递阶商空间覆盖网络链；其\n特征在于：从无向无权连通网络中作为粒度最细、第0级商空间覆盖网络的初始网络开始，搜索网络中所有的极大完全子图，以极大完全子图为节点，两极大完全子图的节点间有公\n共节点或边，定义两节点相连，得到粒度较粗的商空间覆盖，为初始网络的一级商空间覆盖网络；然后再求初始网络的一级商空间覆盖网络的所有极大完全子图，并记录极大完全子\n图对应于初始网络中的节点信息，以该级的极大完全子图为节点、两极大完全子图的节点\n间有公共节点或边定义为两节点相连，得到粒度较粗的商空间覆盖，构成初始网络的二级\n商空间覆盖网络，求初始网络的二级商空间覆盖网络的所有极大完全子图，并记录该级的\n极大完全子图对应于初始网络中的节点信息；继续依此操作直至在商空间覆盖网络的极大\n完全子图对应于初始网络的节点信息中初始网络的任意两节点对都在同一个极大完全子\n图中；各商空间覆盖网络按构成先后顺序排列形成一个递阶商空间覆盖网络链；按递阶商\n空间覆盖网络链的顺序，记录各个商空间覆盖网络的所有极大完全子图和各个极大完全子\n图对应于初始网络的节点信息为商空间覆盖模型；对于无向无权的不连通网络，先求出各\n个连通分支，再对每个连通分支按无向无权连通网络来求解其商空间覆盖模型；从而得到\n一个递阶商空间覆盖网络链中各个商空间覆盖网络的所有极大完全子图构成的极大完全\n子图集和极大完全子图对应于初始网络的节点信息的商空间覆盖模型； \n[0010] 然后在此商空间模型基础上进行路径搜索：在商空间模型的极大完全子图对应于\n初始网络的节点信息中找出要搜索的起点和终点在不同商空间覆盖网络的极大完全子图\n集中的对应位置的分层编号，并在分层编号前面加上附加在初始网络中的标号，比较初始\n网络起点和终点的分层编号，找出自左到右方向其编号相等的第一个位置，找到在递阶商\n空间覆盖网络链中的对应商空间覆盖网络极大完全子图集；再从其在递阶商空间覆盖网络\n链中左边邻居的商空间覆盖网络开始搜索初始网络起点到终点的路径，其路径用分层编号\n中该起点和终点所分别对应的编号来表示，接着再搜索初始网络起点到终点在其左边邻居\n商空间覆盖网络中的路径，其路径的起点和终点是分层编号对应的编号，中间节点是递阶\n商空间覆盖网络链中右边邻居的商空间覆盖网络中得到路径的从左到右两节点的交集；依\n次类推，直到递阶商空间覆盖网络链中最左边的商空间覆盖网络即为初始网络，实现从粗\n粒度商空间覆盖网络逐步搜索到细粒度商空间的过程，从而得到初始网络的起点到终点的\n最短路径。 \n[0011] 上述基于商空间覆盖模型的路径搜索可具体操作如下： \n[0012] 先针对具体网络拓扑依据商空间理论给出具体组成元素的表达形式： \n[0013] 对已给定的无向无权网络G(X，E)，由节点z∈X构成节点集X，符号∈表示“属\n于”，由所有的边e构成边集E，边e上的权值由0，1构成；根据相容关系，将网络G(X，E)中在同一极大完全子图节点归为一覆盖，将有公共节点或边的两覆盖定义为一边，形成网络\nG(X，E)的商空间覆盖网络； \n[0014] 当无向无权网络G(X，E)为连通网络时，记节点集X＝X0，边集E＝E0，求解网络\nG(X0，E0)中的所有极大完全子图，将网络G(X0，E0)中在同一极大完全子图的节点归为一覆盖，再将每个覆盖当作一个节点，将有公共边或节点的两覆盖定义为一边，构成网络G(X0，E0)的一级商空间覆盖网络G1(X1，E1)，其中X1是由网络G(X0，E0)中的极大完全子图构成，E1表示网络G(X0，E0)中的极大完全子图之间存在交集； \n[0015] 对于网络G1(X1，E1)，求解网络G1(X1，E1)中的所有极大完全子图，并记录极大完全子图对应于初始网络G(X0，E0)中的节点信息；在极大完全子图对应于初始网络G(X0，E0)的节点信息中，判断初始网络G(X0，E0)的任意两节点对都是否在同一个极大完全子图中，如果在，网络G1(X1，E1)为最粗的商空间覆盖网络Gk(Xk，Ek)，否则对于网络G1(X1，E1)将在同一极大完全子图的节点归为一覆盖，再将每个覆盖当作一个节点，有公共边或节点的两覆盖\n定义为一边，构成网络G1(X1，E1)的一级商空间覆盖网络，记为网络G(X0，E0)的二级商空间覆盖网络G2(X2，E2)，其中X2是由网络G1(X2，E2)中的极大完全子图构成，E2表示网络G1(X1，E1)中的极大完全子图之间存在交集； \n[0016] 依次类推，对于网络Gi(Xi，Ei)，求解其所有极大完全子图，并记录极大完全子图对应于初始网络G(X0，E0)中的节点信息，在这些信息中判断初始网络G(X0，E0)的任意两节\n点对都是否在同一个极大完全子图中：如果在，则网络Gi(Xi，Ei)为最粗的商空间覆盖网络Gk(Xk，Ek)；否则对于网络Gi(Xi，Ei)将在同一极大完全子图的节点归为一覆盖，再将每个覆盖当作一个节点，有公共边或节点的两覆盖定义为一边，构成网络Gi(Xi，Ei)的一级商空间覆盖网络，记为网络G(X0，E0)的i+1级商空间覆盖网络Gi+1(Xi+1，Ei+1)，其中Xi+1是由网络Gi(Xi，Ei)中的极大完全子图构成，Ei+1表示网络Gi(Xi，Ei)中的极大完全子图之间存在交集； \n[0017] 直到最粗的商空间覆盖网络Gk(Xk，Ek)，求解网络Gk(Xk，Ek)中的所有极大完全子图，并记录极大完全子图对应于初始网络G(X0，E0)中的节点信息；在极大完全子图对应于初始网络G(X0，E0)的节点信息中，初始网络G(X0，E0)的任意两节点对都在同一个极大完全子图中； \n[0018] 各商空间覆盖网络按构成先后顺序排列形成一个递阶商空间覆盖网络链G(X0，\nE0)，G1(X1，E1)，…，Gi(Xi，Ei)，…，Gk(Xk，Ek)； \n[0019] 按照递阶商空间覆盖网络链G(X0，E0)，G1(X1，E1)，…，Gi(Xi，Ei)，…，Gk(Xk，Ek)的顺序，记录各个商空间覆盖网络的极大完全子图和各个极大完全子图对应于初始网络的节\n点信息即为商空间覆盖模型； \n[0020] 当无向无权网络G(X，E)为不连通网络时：先求出网络G(X，E)的各个连通分支，\n再对每个连通分支用求无向无权连通网络的方法获得其商空间覆盖模型； \n[0021] 对于要搜索的初始网络起点a与终点b之间的最短路径，根据商空间覆盖模型中\n极大完全子图对应于初始网络的节点信息，先在递阶商空间覆盖网络链G(X0，E0)，G1(X1，E1)，…，Gi(Xi，Ei)，…，Gk(Xk，Ek)中搜索起点a和终点b在不同商空间覆盖网络 Gi(Xi，Ej)(0≤i≤k)的极大完全子图集中对应位置的分层编号，记录起点a和终点b在商空间覆\n盖网络Gi(Xi，Ej)(0≤i≤k)的极大完全子图集中所有位置，并在分层编号前面加上附加\n0 1 k 0\n在初始网络中的标号，令起点a和终点b的分层编号表示为(a，a0，a0，…，a0)，(b，b0，\n1 k i i\nb0，…，b0)，其中a0、b0，0≤i≤k，包含多个编号，比较初始网络起点和终点的分层编号，j-1 j-1\n找出自左到右方向其编号相等的第一个位置j，有a0 等于b0 ，即起点a和终点b都不包\n含在商空间覆盖网络G(X0，E0)，G1(X1，E1)，…，Gj-2(Xj-2，Ej-2)中任何一个极大网络子图中，而在商空间覆盖网络Gj-1(Xj-1，Ej-1)，Gj(Xj，Ej)，…，Gk(Xk，Ek)中找到极大网络子图使得起点a和终点b包含在其中；取起点a到终点b在初始网络j-1级商空间覆盖网络Gj-1(Xj-1，\nj-1 j-1 j-1 j-2 j-1\nEj-1)中的路径lj-1为(m0 ，m1 )，其中m0 为起点a的分层编号的第j-1个编号a0 ，m1\nj-2 j-1 j-1\n为终点b的分层编号的第j-1个编号b0 ；如果m0 、m1 有多个编号，只取其中的任何一\n个； \n[0022] 在初始网络j-2级商空间覆盖网络Gj-2(Xj-2，Ej-2)中搜索起点a到终点b的路径 \nj-2 j-3 j-2\n其中m0 为起点a的分层编号的第j-2个编号a0 ，m2 为终点b的\nj-3 j-2 j-1 j-1 j-2\n分层编号的第j-2个编号，b0 ，m1 为路径lj-1的m0 、m1 的交集，其中ms (s＝0，1，2)\n有多个编号，只保存其中的任何一个； \n[0023] 在初始网络j-3级商空间覆盖网络Gj-3(Xj-3，Ej-3)中搜索起点a到终点b的路径 \nj-3 j-4 j-3\n其中m0 为起点a的分层编号的第j-3个编号a0 ，m3 为终点\nb的分层编号的第j-3个编号b0j-4，m1j-3为路径lj-2中的m0j-2、m1j-2的交集，m2j-3为路径lj-2中的m1j-2、m2j-2的交集，其中msj-3(s＝0，1，2，3)有多个编号，只保存其中的一个； [0024] 在初始网络j-i(1≤i≤j-1)级商空间覆盖网络Gj-i(Xj-i，Ej-i)中搜索起点a到\nj-i\n终点b的路径 其中m0 为起点a的分层编号的第j-i个编号\nj-i-1 j-i j-i-1 j-i-1 j-i+1 j-i+1\na0 ，mi 为终点b的分层编号的第j-i个编号b0 ，mp 为路径lj-i+1中的mp-1 、mp\nj-i\n的交集，1≤p≤i-1，其中ms (s＝0，1，…，i)有多个编号，只保存其中的任何一个； \n[0025] 当i等于j-1时，在初始网络一级商空间覆盖网络G1(X1，E1)中搜索起点\na到终点b的路径 对于在初始网络，起点a到终点b的路径 \n即为所求的最短路径，其中m00等于a，mj0等于b，ms0(s＝1，2，…，\n1 1 0\nj-1)为路径l1中ms-1、ms 的交集，如果ms 存在多个编号，则起点a到终点b有多条最短路\n0\n径，在各个ms(s＝1，2，…，j-1)中取出一个编号就构成一条最短路径，其最短路径的条数\n0\n是各个ms(s＝1，2，…，j-1)含有多个编号数目的乘积数，其最短路径长度为j。 \n[0026] 至此，在上述商空间覆盖模型的基础上，快速搜索出任意两节点的最短路径，并可同时搜索出该两节点中的多条最短路径。 \n[0027] 上述求解无向无权网络中所有的极大完全子图的方法有多种，其中包括：一，在文 献《基于最大Code码的极大完全子图算法》(计算机科学，作者郭平、康艳荣、史晓晨。2006年第33卷第2期第188-190页)提到的一种寻找图的极大完全子图的算法；二，相容关系\n中求解完全覆盖的方法；三，先找出网络中所有的拓扑结构是三角形的子图，再根据是三角形的子图来就拓扑结构是四点的完全子图，用递归的思想逐步求出最多点的完全子图，再\n统计出所有的极大完全子图。 \n[0028] 上述求解无向无权不连通网络的连通分支方法有多种，其中包括在文献《一个求\n图的连通分支的并行算法》(软件学报，作者唐策善、梁维发。1993年第4期)提到的求解\n连通分支的并行算法。 \n[0029] 上述对于比较初始网络起点和终点的分层编号，找出自左到右方向其编号相等的\n第一个位置j，可以运用多种方法在分层编号中查找，包括：一，用折半查找法；二，用从左到右的逐个查找法；三，用从右到左逐个查找法；四，用计算机中并行算法来查找。 \n[0030] 本发明中所述的无向无权网络，是包括互联(Internet)网、交通网络或电力网络\n在内的复杂网络。 \n[0031] Internet网中，在路由器层面上，节点为路由器，边为路由器之间的物理连接(如光纤)。同样在自治系统的层面上，节点为域，边为连接域的物理连接。 \n[0032] 城市交通网络中，节点为公交车站台，边为城区道路。在铁路交通网络中，节点为火车站，边为铁路。同理在航空网络以飞机场为节点，边是航班。 \n[0033] 电力网络中，节点为变电站，边为输电线。 \n[0034] 可利用计算机来实现本发明基于商空间覆盖模型的最短路径快速搜索，其操作步\n骤如下： \n[0035] 用二维数组G[N][N]来存储无向无权网络G(X，E)，对于大规模的网络，可以用文\n件或者数据库中的表结构存放，访问无向无权网络G(X，E)时可以逐行读取文件或表；用二维数组covern[][]存储网络极大完全子图和极大完全子图在初始网络中的节点信息，用\n链表L存放各级商空间覆盖网络的极大完全子图信息； \n[0036] 首先判断无向无权网络G(X，E)是否为连通网络：如果是，转向第一步；如果不是，则根据求解连通分支算法求解各个连通分支再以每个连通分支为一个无向无权连通网络，\n采用求无向无权连通网络的方法来得到其商空间覆盖模型： \n[0037] 第一步，对于各连通网络先根据二维数组G[N][N]利用相容关系中的求完全覆盖\n的方法来求网络中所有极大完全子图和极大完全子图在初始网络中的节点信息，存放到二\n维数组covern[][]，并将二维数组covern[][]加入到链表L中； \n[0038] 判断二维数组covern[][]中极大完全子图在初始网络中的节点信息是否包含初\n始网络中任意两节点对都在同一个极大完全子图中，如果是，程序结束；否则，执行下面的程序： \n[0039] 根据二维数组covern[][]中各个极大完全子图的关系，每个极大完全子图为一\n节点，每两个极大完全子图之间有公共点定义其有一边，构造出下一级的商空间覆盖网络，更新二维数组G[N][N]，并转向第一步循环求二维数组G[N][N]的极大完全子图； \n[0040] 最后得到的商空间覆盖模型在计算机存储时只要链表L，即各级商空间网络的极\n大 完全子图的信息以及该极大完全子图相对应于初始网络节点的信息； \n[0041] 然后进行起点a到终点b间最短路径快速搜索： \n[0042] 根据商空间覆盖模型中的链表L，搜索出起点a和终点b在不同商空间覆盖网络\n的极大完全子图集中对应位置的分层编号，并在分层编号前面加上附加在初始网络中的标\n号，分别用一个数组A[]和数组B[]来存储，包含多个编号可用链表的形式存入数组A[]和\nB[]中； \n[0043] 再比较起点a和终点b的分层编号，用折半查找法找出数组A[]和数组B[]中编\n号相同的最小数组下标用变量j存储； \n[0044] 用数组L来存储初始网络j-1级商空间覆盖网络Gj中的路径，路径长度为1，其中\n第0个元素是数组A[]的第j-1个元素，第1个元素是数组B[]的第j-1个元素； \n[0045] 将变量i赋值为2； \n[0046] 计算初始网络j-i级商空间覆盖网络Gj-i中的路径存储到数组L’，数组L’长度为i+1，其中第0个元素是数组A[]的第j-i个元素，第i个元素是数组B[]的第j-i个元素，\n其它元素计算：第p(1≤p≤i-1)个元素为数组L中第p-1个元素和第p个元素的交集，\n且取交集中的一个元素；将数组L赋值为数组L’，i赋值为i+1，当i小于等于j-1，重复执\n行此段步骤； \n[0047] 再求在初始网络中的路径，存储在数组L’中，数组L’的长度为j，其中第0个\n元素是数组A[]的第0个元素，第j个元素是数组B[]的第0个元素，其它元素计算：第\np(1≤p≤j-1)个元素为数组L中第p-1个元素和第p个元素的交集； \n[0048] 则L’即为起点a到终点b在初始网络中的路径。 \n[0049] 由于本发明最短路径搜索方法所采用的商空间覆盖模型是由递阶商空间覆盖网\n络链中在不同粒度下商空间覆盖网络的极大完全子图集和极大完全子图相对应于初始网\n络节点的信息构成，其中不同粒度下商空间覆盖网络的极大完全子图集信息为网络中节点\n间的最短路径搜索过程提供下一级商空间覆盖网络本身的网络拓扑的信息，极大完全子图\n相对应于初始网络节点的信息提供初始网络在不同粒度世界上的拓扑结构信息。 \n[0050] 本发明基于商空间覆盖模型的最短路径搜索方法是依据商空间覆盖模型的一系\n列粒度由细到粗的商空间覆盖网络所有的极大完全子图和极大完全子图在初始网络中的\n节点信息，先找出要搜索起点和终点在同一极大完全子图的粒度商空间覆盖网络，接着从\n粒度较粗的商空间中搜索最短路径，再逐步细化商空间，直到粒度最细的商空间为止来求\n网络中任意两节点的最短路径，并且同时搜索出网络中多条最短路径，通过在建立了商空\n间覆盖模型的基础上进行最短路径搜索，解决互联(Internet)网中最短路径的搜索以达\n到网络资源的综合利用，解决交通网络中的最短路径搜索使得乘客达到最少换乘的次数等\n效果，解决电力网络中的最短路径搜索使得电力能源的有效利用和帮助快速故障路径检\n测。 \n[0051] 本发明基于商空间覆盖模型的最短路径搜索方法中根据起点和终点的分层编号\n长度 得到初始网络中任意两节点对之间的最短路径长度的最大值，比较起点和终点的分\n层编号，找出自左到右方向其编号第一个相等的位置，找到在递阶商空间覆盖网络链中的\n对应商空间覆盖网络，起点到终点的最短路径的长度即为分层编号中自左到右方向其编号\n第一个相等的位置数。在路径搜索的过程中，在较粗的商空间覆盖网络对应的起点和终点\n的分层编号中任意取一个编号，是因为在较粗的商空间覆盖中每个极大完全子图都包含了\n初始网络的结构性质。在初始网络中取编号时要全部保存信息，目的是得到多条最短路径。 具体实施方式\n[0052] 对于一个无向无权网络，其网络模型可以应用于互联(Internet)网、交通网络、\n电力网络等不同网络上。一下分别给出本发明的商空间覆盖模型在不同类型无向无权网络\n下的具体使用的举例说明 \n[0053] 实施例1：构建互联(Internet)网的商空间覆盖模型并搜索任意两个路由器之间\n的最短路径 \n[0054] 互联(Internet)网中，由在路由器层面上建立网络G(X，E)，节点为路由器，边为路由器之间的物理连接(如光纤)。同样在自治系统的层面上，节点为域，边为连接域的物\n理连接。 \n[0055] 现在选取某个区域的Internet网上的路由器层面的网络，将各个路由器按照一\n定的顺序来标号，各个路由器的连接状况用无权边来连接表示，无连接为0，有连接的为1。\n建立商空间覆盖模型，对于一个无向无权网络G(X，E)，共有5个节点记为X{1，2，3，4，5}，设其边集E：节点1和节点2、节点1和节点3、节点2和节点3、节点2和节点4、节点3和节\n点4、节点3和节点5之间有边，其他节点间无相连。 \n[0056] 其初始网络G(X，E)对应的矩阵\n[0057] 其网络构建商空间覆盖模型的过程： \n[0058] 初始网络G(X，E)，X＝{1，2，3，4，5}，对应的网络矩阵R，判断其网络是连通网络，求其所有极大完全子图，取节点1，对于矩阵R中的r12＝1，得(1，2)，因为r13＝r23＝1，故取节点3，得子图(1，2，3)，r1没有其它不为0的分量，则(1，2，3)是其中一个极大完全子图；再取节点2，因r23＝1取节点4，得(2，3)。又r34＝r24＝1，故取点3，得(2，3，4)，r2没有其它不为0的分量，则(2，3，4)是其中一个极大完全子图；再取点3，因r35＝1，取(3，\n5)。最后得极大完全子图集合：{(1，2，3)，(2，3，4)，(3，5)}，由于操作对象就是初始网络，故极大完全子图在初始网络中的节点信息和极大完全子图集合相同。 \n[0059] 可得初始网络G(X，E)的一级商空间覆盖网络G1(X1，E1)，根据极大完全子图集合：\n{(1，2，3)，(2，3，4)，(3，5)}可得X1中有三个元素 分别表\n示 所求得的三个极大完全子图，由于(1，2，3)和(2，3，4)之间有公共节点2、3，这两个极大完全子图之间在商空间覆盖网络G1(X1，E1)中有边相连，同理，(1，2，3)和(3，5)、(2，3，4)和(3，5)在商空间覆盖网络G1(X1，E1)中也有边相连，其商空间覆盖网络G1(X1，E1)对应矩阵 \n[0060] 对于商空间覆盖网络G1(X1，E1)求其极大完全子图集合，取节点a11，，对于矩阵R1中的r12＝1，得(1，2)，因为r13＝r23＝1，故取节点x31，得子图(1，2，3)，最后得极大完全子图集合：{(1，2，3)}，极大完全子图在初始网络中的节点信息为{(1，2，3，4，5)}，从极大完全子图在初始网络中的节点信息判断，其满足构建商空间覆盖模型的最粗商空间的条件，\n商空间覆盖模型构建成功，表明初始网络中最短路径长度不超过2。 \n[0061] 根据商空间覆盖模型可以快速搜索网络中任意两节点的最短路径，搜索从节点1\n到节点4的最短路径其步骤如下： \n[0062] 先求节点1和节点4在各个商空间覆盖网络中的分层编号：节点1的分层编号为\n(1，1，1)，节点4的分层编号为(4，2，1)；接着找出分层编号中自左向右一个编号相同的位置j，用折半查找法搜索节点1和节点4的分层编号，得j＝2，其节点1到节点4的最短路\n径长度为2。 \n[0063] 在初始网络的第1级商空间覆盖网络来搜索最短路径l1＝(1，2)，接着再初始网\n络中搜索，取(1，2，3)和(2，3，4)的交集为(2，3)，则最短路径l0＝(1，(2，3)，4)，故得到节点1到4的两条最短路径为(1，2，4)和(1，3，4)。 \n[0064] 下面通过计算机操作来完成这5节点网络的商空间覆盖模型构建过程以及节点1\n到4的搜索过程步骤： \n[0065] 用二维数组G[5][5]来存储无向无权网络G(X，E)的矩阵R。 \n[0066] 首先判断网络G(X，E)是连通网络； \n[0067] 先根据二维数组G[5][5]利用相容关系中的求完全覆盖的方法来求网络的极\n大完全子图和在初始网络的节点对应信息，存放到二维数组covern[][]，并将二维数组\ncovern[][]加入到链表L中，其信息包括{{(1，2，3)，(2，3，4)，(3，5)}，{(1，2，3)，(2，3，4)，(3，5)}}， \n[0068] 再根据二维数组covern[][]中各个极大完全子图的关系，每个极大完全子图为\n一节点，每两个极大完全子图之间有公共点定义其有一边，构造出初始网络的第1级的商\n空间覆盖网络，更新二维数组G[5][5]为二维数组G[3][3]为上述的R1，利用相容关系中的\n求完全覆盖的方法来求网络的极大完全子图和在初始网络的节点对应信息，存放到二维数\n组covern[][]，并将二维数组covern[][]加入到链表L中，其信息包括{{(1，2，3)}，{(1，\n2，3，4，5)}}。 \n[0069] 极大完全子图对应于初始网络的节点信息{(1，2，3，4，5)}中初始网络的任意两节点对都在同一个极大完全子图中，程序退出； \n[0070] 其中链表L 的信息为：{{{(1，2，3)，(2，3，4)，(3，5)}，{(1，2，3)，(2，3，4)，(3，\n5)}}，{{(1，2，3)}，{(1，2，3，4，5)}}}。 \n[0071] 然后进行起点1到终点4间最短路径快速搜索： \n[0072] 根据商空间覆盖模型中的链表L，搜索出起点1和终点4在不同商空间覆盖网络\n的极大完全子图集中对应位置的分层编号，并在分层编号前面加上附加在初始网络中的标\n号，分别用一个数组A[]和数组B[]来存储，包含多个编号可用链表的形式存入数组A[]和\nB[]中；A[]＝{1，1，1}，B[]＝{4，2，1}. \n[0073] 再比较起点1和终点4的分层编号，用折半查找法找出数组A[]和数组B[]中编\n号相同的最小数组下标用变量j＝2存储； \n[0074] 用数组L来存储初始网络1级商空间覆盖网络G1中的路径为(1，2)(数组A[]的\n第1个元素，数组B[]的第1个元素)； \n[0075] 计算初始网络0级商空间覆盖网络G0中的路径存储到数组L’，数组L’长度为3，\n其中第0个元素是数组A[]的第0个元素，第2个元素是数组B[]的第0个元素，第1个元\n素为(1，2，3)和(2，3，4)的交集为(2，3)，所求的路径L即为起点1到终点1的最短路径\n(1，(2，3)，4)。 \n[0076] 故得到节点1到4的两条最短路径为(1，2，4)和(1，3，4)。 \n[0077] 在路径搜索的过程中，在较粗的商空间覆盖网络对应的起点和终点的分层编号中\n任意取一个编号，是因为在较粗的商空间覆盖中每个极大完全子图都包含了初始网络的结\n构性质。在初始网络中取编号时要全部保存信息，目的是得到多条最短路径。 \n[0078] 应用商空间覆盖模型搜索出任意两节点间的最短路径，然后将最短路径的数字编\n码对应于各个网络路由器名称，即可以得到任意两路由器之间的最短路径，使得网络路径\n经过路由器最少，为网络中的路径选择提供方便，为网络资源的综合充分利用创造条件。 [0079] 实施例2：构建交通网络的商空间覆盖模型并搜索任意两个车站之间的最短路径 \n[0080] 对于城市交通网络中，节点为公交车站台，边为城区道路。在铁路交通网络中，节点为火车站，边为铁路。同理在航空网络以飞机场为节点，边是航班。 \n[0081] 现在选取某个航空网络，将各个飞机场按照一定的顺序来标号，各个飞机场的连\n接状况用无权边来连接表示，飞机场间没有航班则为无连接为0，飞机场间有航班则为有连接的为1。建立商空间覆盖模型，对于一个无向无权网络G(X，E)，共有7个节点记为X{1，\n2，3，4，5，6，7}，设其边集E：节点1和节点2、节点2和节点3、节点3和节点4、节点4和节点5、节点5和节点6、节点6和节点7、节点1和节点7之间有边，其他节点间无相连。其初\n始网络G(X，E)对应的矩阵\n[0082] 其网络构建商空间覆盖模型的过程： \n[0083] 初始网络G(X ，E)，X＝{1，2，3，4，5，6，7}，对应的网络矩阵R，判断其网络是连通网络， 求其极大完全子图集合为{(1，2)，(2，3)，(3，4)，(4，5)，(5，6)，(6，7)，(1，7)}，极大完全子图在初始网络中的节点信息为{(1，2)，(2，3)，(3，4)，(4，5)，(5，6)，(6，7)，(1，7)}。 [0084] 可得初始网络G(X，E)的一级商空间覆盖网络G1(X1，E1)，根据极大完全子\n图集 合{(1，2)，(2，3)，(3，4)，(4，5)，(5，6)，(6，7)，(7，1)}可 得X1中 有7个 元 素 分别表示所求得的7个极大完全子图，由于(1，\n2)和(2，3)之间有公共节点2，这两个极大完全子图之间在商空间覆盖网络G1(X1，E1)中有边相连，同理，(2，3)和(3，4)、(3，4)和(4，5)、(4，5)和(5，6)、(5，6)和(6，7)、(6，7)和(1，7)在商空间覆盖网络G1(X1，E1)中也有边相连，其商空间覆盖网络G1(X1，E1)对应矩阵R1＝R，得商空间覆盖网络G1(X1，E1)其形式与初始网络G(X，E)相同，只是各节点所含的原网络的节点子集不同而已。 \n[0085] 对于商空间覆盖网络G1(X1，E1)求其极大完全子图集合{(x11，x21)，(x21，x31)，(x31，\n1 1 1 1 1 1 1 1 1\nx4)，(x4，x5)，(x6，x7)，(x6，x7)，(x1，x7)}，极大完全子图在初始网络中的节点信息为{(1，2，3)，(2，3，4)，(3，4，5)，(4，5，6)，(5，6，7)，(6，7，1)，(7，1，2)}。 [0086] 可得初始网络G(X，E)的二级商空间覆盖网络G2(X2，E2)，根据初始网络一级商空\n1 1 1 1 1 1 1 1 1\n间覆盖网络G1(X1，E1)的极大完全子图集合：{(x1，x2)，(x2，x3)，(x3，x4)，(x4，x5)，(x5，\n1 1 1 1 1\nx6)，(x6，x7)，(x1，x7)}可得X2中有7个元素 \n1 1 1 1\n分别表示所求得的7个极大完全子图，由于(x1，x2)和(x2，x3)之间有公共节点2，这两\n1 1 1 1\n个极大完全子图之间在商空间覆盖网络G1(X1，E1)中有边相连，同理，(x2，x3)和(x3，x4)、\n1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1\n(x3，x4)和(x4，x5)、(x4，x5)和(x5，x6)、(x5，x6)和(x6，x7)、(x6，x7)和(x1，x7)\n在商空间覆盖网络G2(X2，E2)中也有边相连，其商空间覆盖网络G2(X2，E2)对应矩阵R2＝R，得商空间覆盖网络G2(X2，E2)其形式与初始网络G(X，E)相同，只是各节点所含的原网络的节点子集不同而已。 \n[0087] 对于商空间覆盖网络G2(X2，E2)求其极大完全子图集合{(x12，x22)，(x22，x32)，(x32，\n2 2 2 2 2 2 2 2 2\nx4)，(x4，x5)，(x5，x6)，(x6，x7)，(x1，x7)}，极大完全子图在初始网络中的节点信息为{(1，2，3，4)，(2，3，4，5)，(3，4，5，6)，(4，5，6，7)，(5，6，7，1)，(6，7，1，2)，(7，1，2，3)}。 [0088] 极大完全子图对应于初始网络的节点信息{(1，2，3，4)，(2，3，4，5)，(3，4，5，6)，(4，5，6，7)，(5，6，7，1)，(6，7，1，2)，(7，1，2，3)}中初始网络的任意两节点对都在同一个极大完全子图中，商空间覆盖模型构建成功。 \n[0089] 直接验证易得对初始网络i级商空间覆盖网络Gi(Xi，Ei)，如果初始网络中两节点在同一极大完全子图中，则这两点之间的距离≤i+1。根据此性质，可以得到初始网络任意两节点的最短距离≤3。对于这个网络拓扑结构是环的特殊网络，其各级商空间覆盖网络未必比原网络简单，但其节点的粒度越来越粗，网络中的最短程越来越短，故对求最短路径是越来越方便。 \n[0090] 对于不连通的网络，可以先求出各个连通分支，把连通分支当作一个网络，再构建 其商空间覆盖模型。 \n[0091] 下面根据商空间覆盖模型可以快速搜索网络中任意两节点的最短路径，搜索从节\n点1到节点3的一条最短路径其步骤如下： \n[0092] 先求节点1和节点3在各个商空间覆盖网络中的分层编号：为了求出节点间的\n一条最短路径，为了表述方便，分层编号中只取一个元素，分层编号中节点1的分层编号为(1，(1，7)，(1，6，7)，(1，5，6，7))，节点3的分层编号为(3，(2，3)，(1，2，3)，(1，2，3，7))；接着找出分层编号中自左向右一个编号相同的位置j，用折半查找法搜索节点1和节点3的分\n层编号，得j＝2，其节点1到节点3的最短路径长度为2。 \n[0093] 在初始网络的第l级商空间覆盖网络来搜索，在(1，7)和(2，3)中任意取一个编\n号，其最短路径l1＝(1，2)，接着再初始网络中搜索，在(1，2)和(2，3)中取交集(2)，最短路径l0＝(1，2，3)，故得到节点1到3的两条最短路径为(1，2，3)。 \n[0094] 在路径搜索的过程中，在较粗的商空间覆盖网络对应的起点和终点的分层编号中\n任意取一个编号，是因为在较粗的商空间覆盖中每个极大完全子图都包含了初始网络的结\n构性质。在初始网络中取编号时要全部保存信息，目的是得到多条最短路径。 \n[0095] 应用商空间覆盖模型方便地搜索出任意两节点间的最短路径，然后将最短路径的\n数字编码对应于飞机场的名称对应，即可以得到任意两飞机场的最短路径，为乘客选择经\n过的中转最少的路径。对于数字化交通地图中，为系统设计了快捷、易于求解最短路径的算法。 \n[0096] 实施例3：构建电力网络的商空间覆盖模型并搜索任意两个变电站之间的最短路\n径 \n[0097] 在电力网络中，节点为变电站，边为输电线，建立网络G(X，E)。 \n[0098] 现在选取某个电力网络，将各个变电站按照一定的顺序来标号，各个变电站的连\n接状况用无权边来连接表示，变电站间没有输电线则为无连接为0，变电站间有输电线则为\n3\n有连接的为1。应用本发明的方法通过计算机仿真模拟了10 节点以内的计算机网络系统\n的网络，无向无权网络是分别根据随机网络模型、小世界网络模型和无标度网络模型来生\n成的，分别用商空间粒度分类方法来构建商空间覆盖模型，并在此基础上搜索了节点对之