CN105978711B - 一种基于最小生成树的最佳交换边查找方法 - Google Patents

Abstract

本发明给出一种基于最小生成树的最佳交换边查找方法，该方法将最佳交换边查找问题定义成图模型，从全局角度求解失效边对应的最佳交换边，通过分布式算法等策略获取可行解空间。本发明能够形成解决全局情况下图模型中失效边对应的最佳交换边查找方案，使得图模型中的最佳交换边求解问题在解决过程中在时间和空间复杂度上得到优化，并能够避免早熟收敛。本发明要解决的最佳交换边查找问题是指给定一个通信网络，该网络中的最小生成树上的某条边失效，造成暂时的通信故障，运用分布式算法在该网络中查找一个最佳交换边，替换该失效边，使得通信尽可能保持畅通，并且能够达到诸如通信网络恢复损耗最少、最小生成树的直径尽可能小等目的。

Description

一种基于最小生成树的最佳交换边查找方法

技术领域

本发明涉及通信网络最小生成树中最佳交换边的求解方法，主要利用分布式算法从全局角度求解图模型中失效边对应的最佳交换边，属于计算机技术、信息技术、图挖掘、分布式处理交叉技术领域。

背景技术

分布式系统是指以某种方式合作的若干计算机或处理器上的所有计算机应用。分布式处理是将不同地点的，或具有不同功能的，或拥有不同数据的多台计算机通过通信网络连接起来，在控制系统的统一管理控制下，协调地完成大规模信息处理任务的计算机系统。分布式处理利用网络技术能把许多小型机或微机连接成具有高性能的计算机系统，使其具有解决复杂问题的能力。

分布式算法，就是指在完成乘加功能时通过将各输入数据每一对应位产生的运算结果预先进行相加形成相应的部分积，然后再对各部分进行累加形成最终结果。分布式算法的研究，来源于分布式系统开发活动中的基础研究，其内容构成了分布式计算的核心技术。

发明内容

技术问题：本发明要解决最小生成树中的最佳交换边查找问题，该问题是指给定一个通信网络，即图模型，并给定在该图模型中的最小生成树和一条失效边，从该图模型中选择一条最佳交换边，用来替换失效边，使得失效边造成的通信故障尽快恢复，并且使得新产生的最小生成树直径最小。

技术方案：所述最小生成树中的最佳交换边查找问题描述如下：设给定一个通信网络，再给定一条失效边，基于最小生成树的最佳交换边查找方法找到该图模型中的最佳交换边，用以替换该失效边，使得通信网络尽快恢复运作并且新产生的最小生成树直径最小。我们假定该通信网络组织在图模型G＝(V,E)中，该通信网络为一个带权无向图。每个节点可能与多个或者0个其他节点相连，节点与节点相连构成一条边，每条边看作待查询的对象。我们的目标是从图模型G＝(V,E)中找到一条最佳交换边，用来替代失效边，使得新产生的最小生成树直径最小。

本发明所述的基于最小生成树的最佳交换边查找方法将通信网络中的最佳交换边查询问题定义成图模型，以及采用分布式算法获得解空间。

本发明所述的基于最小生成树的最佳交换边查询方法包括以下步骤：

步骤1)根据用户输入的信息，构建网络中的最佳交换边查询问题的图模型G＝(V,E)，所述V是节点集，E是边集，n＝|V|，m＝|E|，n是指该图模型中的节点数，m是指该图模型G＝(V,E)中的边数。具体步骤如下：

步骤11)用户输入包含一组节点集、边集、最小生成树以及一条失效边。所述用户输入的节点集记为V＝{d₁,d₂,d₃,…,d_n}，边集记为E＝{e₁,e₂,e₃,…,e_m}，n＝|V|，m＝|E|，每条边e对应一个非负长度l(x)，路径Ρ＝<d₁,d₂,d₃,…,d_r>表示由节点d₁,d₂,d₃,…,d_r构成的一条路径，|Ρ|表示这条路径的长度，即所有边的长度之和，最小生成树记为T。所述n是指节点集中的节点数；所述m是指边集中的边数。

步骤12)将节点集V＝{d₁,d₂,d₃,…,d_n}中所有节点看作图模型G＝(V,E)中的节点。

步骤13)将节点u和节点v之间的路径看作图模型G＝(V,E)两节点之间的弧，两节点之间的距离d(u,v)作为节点u和节点v之间弧的权值，所述d(u,v)为图模型G＝(V,E)中节点u和节点v最短路的权值。

步骤14)给定最小生成树T＝(V，E(T))，定义D＝<d₁,d₂,d₃,…,d_k>，|D|为最小生成树T＝(V，E(T))的直径，即T中的最长路径长度。定义D的中心节点d_c，定义D_L＝<d₁,d₂,d₃…d_c>，定义D_R＝<d_c,d_c+1,d_c+2…d_k>，上述节点满足：|D_L|≥|D_R|。所述D是指在最小生成树中由节点d₁,d₂,d₃,…,d_k构成的一条路径，所述D_L是指在最小生成树中由节点d₁,d₂,d₃,…,d_c构一条路径，所述D_R是指在最小生成树中由节点d_c,d_c+1,d_c+2,…,d_k构一条路径，所述|D_L|是指路径D_L的直径，所述|D_R|是指路径D_R的直径。

步骤15)令d_c作为最小生成树T＝(V，E(T))的中心，对于每个节点x∈V且x≠d_c，定义节点x的父节点p(x)，定义节点x的孩子节点集C(x)。定义T_x＝(V(T_x),E(T_x))表示以节点x为根节点的最小生成树T的一棵子树。定义V_L表示以节点d_c-1为根节点的子树，定义V_R表示以节点d_c+1为根节点的子树，定义V_c表示除V_L、V_R外其他的所有节点。

步骤16)用户输入失效边e′＝(x′,p(x′))之后，最小生成树T＝(V，E(T))分成了两棵子树T_x′和T\T_x′，所述T\T_x′不包括节点x′。所述T\T_x′是指由节点集V(T)/V(T_x′)和边集E(T)/E(T_x′)/{(x′,p(x′))}构成的图。我们的任务是针对失效边e′＝(x′,p(x′))找到一条边f，用以替代这条失效边。所述f是E\E(T)中任何一条能使两棵子树T_x′和T\T_x′重新连接在一起的边，称之为交换边。定义S(e′)表示边e′对应的交换边构成的集合。对于失效边e′＝(x′,p(x′))来说，一条最佳交换边f′∈S(e′)，是指加入该交换边后能使新产生的最小生成树的|D(T_e′/f′)|最小。所述e′＝(x′,f(x′))表示给定的失效边，f′＝(z,z′)表示一条交换边。所述z是指在T_x中的一个节点；所述z′是指在T\T_x中的一个节点。

步骤2)采用分布式算法，获得通信网络中的最佳交换边查找问题在图模型G＝(V,E)上的解空间。具体步骤如下：

步骤21)对于给定的失效边e′＝(x′,f(x′))，遍历以x′为根的子树T_x′中的每个节点z。

步骤22)等候来自父节点的可用信息，计算|L(T_x′,z)|，同时为所有孩子节点计算可用信息并发送该信息。所述|L(T_x′,z)|，是指以节点z开始的且在图T_x′中的最长路径的长度。

步骤23)对每个本地交换边f＝(z,z′)，对|L(T\T_x′,z′)|进行分布式计算。所述本地交换边，是指在边集S(e′)中且邻近节点z的一条边；所述|L(T\T_x′,z′)|，是指以节点z′开始的且在图T\T_x′中的最长路径的长度。其中，

|L(T\T_x′,z′)|＝max{d(z′,d_k),d(z′,d_c)+γ,d(z′,d_c)+λ(p(x′)),

d(z′,u′)+d(u′,ρ_R)+μ_R-d(d_k,ρ_R)}

所述d(z′,d_k)是指以节点z′和节点d_k为端点的一条边；所述d(z′,d_c)是指以节点z′和节点d_c为端点的一条边；所述d(z′,u′)是指以节点z′和节点u′为端点的一条边；所述d(u′,ρ_R)是指以节点u′和节点ρ_R为端点的一条边；所述d(d_k,ρ_R)是指以节点d_k和节点ρ_R为端点的一条边；所述λ(p(x′))是指以节点d_c开始、进入到顶点集V_L中但不会经过节点p(x′)下方的最长路径的长度；所述u′是指在D(T)上以节点z′开始的最长路径上的距离z′最近的节点；所述ρ_R是指在以节点d_k开始且在节点集V_R中的最长路径上的，进入到V_R子树上的根节点；所述γ是指以节点d_c开始且仅包含节点集V_C中节点的最长路径的长度；所述V_C是指除节点d_c外所有节点构成的节点集合；所述μ_R是指以节点d_k开始且在节点集V_R中的最长路径的长度。

步骤24)对每个本地交换边f＝(z,z′)，对|D(T_e′/f)|进行分布式计算：|D(T_e′/f)|＝max{|D(T)|,|L(T_x′,z)|+l(f)+|L(T\T_x′,z′)|}。所述L(T_x′,z)是指以节点z开始的且在图T_x中的最长路径的长度；所述L(T\T_x′,z′)是指以节点z′开始的且在图T\T_x中的最长路径的长度；所述l(f)是指本地交换边f＝(z,z′)的长度。

步骤25)从上述这些本地交换边中，选择一个临时最佳交换边并存储加入该交换边后将会产生的新直径如果没有本地交换边存在，则创建一个虚设的侯选边，且将其新直径设为∞。

步骤26)对于每个孩子节点q∈C(z)，根据上述步骤求得的距离信息，对每个孩子节点选择一个最佳交换边候选并存储加入该交换边后将会产生的新直径再从这些孩子节点对应的最佳交换边中选择第二个临时最佳交换边所述

步骤27)定义目标最佳交换边f_best。比较第一个临时最佳交换边和第二个最佳交换边选择加入对应新直径更小的那条交换边。若则将作为目标最佳交换边f_best；若则将作为目标最佳交换边f_best；若则将或作为目标最佳交换边f_best均可。

步骤28)若以x′为根的子树T_x′中的每个节点z未被全部遍历，重复步骤22)～步骤27)。

步骤29)确定最终解空间S_olution，该解空间中包含失效边e′＝(x′,f(x′))对应的最佳交换边。

有益效果：本发明利用分布式算法形成高效的最佳交换边查找方法。具体体现如下有益效果：

1)本发明提供一种基于最小生成树的最佳交换边查找方法，其完整的方法过程包括将通信网络中的最佳交换边查询问题定义成图模型，以及采用分布式算法获得解空间。

2)本发明中所述建模过程中，提供一个或一套较为抽象的图模型，能够将实际问题中的相关求解方法转化为数学化的模型形式。

3)本发明中所述模型从全局的角度查找最佳交换边方法，使最佳交换边查找问题最终能够得到最优精确解。

4)本发明采用节点信息预先存储与分布式算法，从而有效降低算法时间复杂和空间复杂度。

附图说明

图1是基于最小生成树的最佳交换边查找方法对应的流程图。

图2是最小生成树模型对应的示例图。

图3是最佳交换边查找实例。

具体实施方式

下面对本发明附图的某些实施例作更加详细的描述。

根据附图1所示基于最小生成树的最佳交换边查找方法对应的流程图、图2所示最小生成树模型对应的示例图，本发明具体实施方式为：

1).将通信网络中的最佳交换边查找问题定义成图模型。

11).用户输入包含一组节点集、边集、最小生成树以及一条失效边。如图3所示，节点集V＝{1,2,3,4,5,6}，节点1和节点2相连，其距离d(1,2)＝1；节点1和节点6相连，其距离d(1,6)＝3；节点2和节点3相连，其距离d(2,3)＝1；节点3和节点4相连，其距离d(3,4)＝3；节点4和节点5相连，其距离d(4,5)＝2；节点4和节点6相连，其距离d(4,6)＝3；节点5和节点6相连，其距离d(5,6)＝2，一共有7条边。以上所有节点与节点之间的边相连，构成图模型G＝(V,E)。其中，最小生成树T为图模型G＝(V,E)去除节点4与节点6之间的边、节点5与节点6之间的边后产生的新图。其中节点2与节点3之间的边为失效边，节点3表示失效边的下端节点，节点2表示节点3的父节点。

失效边记作e＝(3，2)。

12).将节点集V＝{1,2,3,4,5,6}中所有节点看作图模型G＝(V,E)中的节点。

所述属性图模型G在建立后，任意两个顶点之间的最短路都有相应的权值，表示两顶点的邻近度。

2).采用分布式算法，获得通信网络中的最佳交换边查找问题在图模型G＝(V,E)上的解空间。具体步骤如下：

21).对于给定的失效边e＝(3,2)，以节点3为根的子树T₃由节点4、节点5以及节点4与节点5之间的边构成，子树T₃共有两个节点，分别是节点4和节点5，将节点4记为z，将节点5记为q。对该子树T₃中的节点进行遍历。

22).第一遍遍历，操作对象为节点z。此时本地交换边为f(4,6)，对|L(T₃,z)|进行分布式计算，得到|L(T₃,z)|＝|L(T₃,4)|＝3。对|L(T\T₃,z′)|进行分布式计算，得到|L(T\T₃,z′)|＝|L(T\T₃,6)|＝max{0,3+1,3+7,3}＝10。对本地交换边f(4,6)，对|D(T_e/f)|进行分布式计算，得到|D(T_e/f)|＝max{10,3+3+10}＝16。记录临时最佳交换边并存储加入该交换边后将会产生的新直径

接下来遍历z的孩子节点q∈C(z)，此时节点4的孩子节点只有一个，即节点5。此时本地交换边为f(5,6)，对|L(T₃,q)|进行分布式计算，得到|L(T₃,q)|＝L(T₃,5)|＝5。对|L(T\T₃,z′)|进行分布式计算，得到|L(T\T₃,z′)|＝|L(T\T₃,6)|＝max{0,3+1,3+7,3}＝10。对本地交换边f(5,6)，对|D(T_e/f)|进行分布式计算，得到|D(T_e/f)|＝max{10,5+2+10}＝17。记录第二个临时最佳交换边并存储加入该交换边后将会产生的新直径

23).定义目标最佳交换边f_best。比较第一个临时最佳交换边和第二个最佳交换边选择加入对应新直径更小的那条边。因所以将作为目标最佳交换边f_best，即f_best＝f(z,z′)＝f(4,6)。

24).第二遍遍历，操作对象为节点q，此时本地交换边为f(5,6)，对|L(T₃,q)|进行分布式计算，得到|L(T₃,q)|＝|L(T₃,5)|＝5。对|L(T\T₃,z′)|进行分布式计算，得到|L(T\T₃,z′)|＝|L(T\T₃,6)|＝max{0,3+1,3+7,3}＝10。对本地交换边f(5,6)，对|D(T_e/f)|进行分布式计算，得到|D(T_e/f)|＝max{10,5+2+10}＝17。记录第二个临时最佳交换边并存储加入该交换边后将会产生的新直径节点q没有孩子节点，所以不需要从孩子节点中搜索可能的最佳交换边。因为本地交换边为f(5,6)对应的直径大于f(4,6)对应的直径，所以目标最佳交换边f_best不变，依然为f(4,6)。

25).确定最终解空间S_olution，该解空间中包含失效边e＝(3,2)对应的最佳交换边f(4,6)。

Claims (2)

1.一种基于最小生成树的最佳交换边查找方法，其特征在于该方法包括以下步骤：

步骤1)根据用户输入的信息，构建网络中的最佳交换边查询问题的图模型G＝(V,E)，所述V是节点集，E是边集，n＝|V|，m＝|E|，n是指该图模型中的节点数，m是指该图模型G＝(V,E)中的边数；

步骤2)采用分布式算法，获得通信网络中的最佳交换边查找问题在图模型G＝(V,E)上的解空间；

其中，所述步骤1)具体步骤如下：

步骤11)用户输入包含一组节点集、边集、最小生成树以及一条失效边，所述用户输入的节点集记为V＝{d₁,d₂,d₃,…,d_n}，边集记为E＝{e₁,e₂,e₃,…,e_m}，n＝|V|，m＝|E|，每条边e对应一个非负长度l(y)，路径P＝<d₁,d₂,d₃,…,d_r>表示由节点d₁,d₂,d₃,…,d_r构成的一条路径，|P|表示这条路径的长度，即所有边的长度之和，最小生成树记为T，所述n是指节点集中的节点数；所述m是指边集中的边数；

步骤12)将节点集V＝{d₁,d₂,d₃,…,d_n}中所有节点看作图模型G＝(V,E)中的节点；

步骤13)将节点u和节点v之间的路径看作图模型G＝(V,E)两节点之间的弧，两节点之间的距离d(u,v)作为节点u和节点v之间弧的权值，所述d(u,v)为图模型G＝(V,E)中节点u和节点v最短路的权值；

步骤14)给定最小生成树T＝(V，E(T))，定义D＝<d₁,d₂,d₃,…,d_k>，|D|为最小生成树T＝(V，E(T))的直径，即T中的最长路径长度，定义D的中心节点d_c，定义D_L＝<d₁,d₂,d₃…d_c>，定义D_R＝<d_c,d_c+1,d_c+2…d_k>，上述节点满足：|D_L|≥|D_R|，所述D是指在最小生成树中由节点d₁,d₂,d₃,…,d_k构成的一条路径，所述D_L是指在最小生成树中由节点d₁,d₂,d₃,…,d_c构一条路径，所述D_R是指在最小生成树中由节点d_c,d_c+1,d_c+2,…,d_k构一条路径，所述|D_L|是指路径D_L的直径，所述|D_R|是指路径D_R的直径；

步骤15)令d_c作为最小生成树T＝(V，E(T))的中心，对于每个节点x∈V且x≠d_c，定义节点x的父节点p(x)，定义节点x的孩子节点集C(x)，定义T_x＝(V(T_x),E(T_x))表示以节点x为根节点的最小生成树T的一棵子树，定义V_L表示以节点d_c-1为根节点的子树，定义V_R表示以节点d_c+1为根节点的子树，定义V_c表示除V_L、V_R外其他的所有节点；

步骤16)用户输入失效边e′＝(x′,p(x′))之后，最小生成树T＝(V，E(T))分成了两棵子树T_x′和T\T_x′，所述T\T_x′不包括节点x′，所述T\T_x′是指由节点集V(T)/V(T_x′)和边集E(T)/E(T_x′)/{(x′,p(x′))}构成的图，任务是针对失效边e′＝(x′,p(x′))找到一条边f，用以替代这条失效边，所述f是E\E(T)中任何一条能使两棵子树T_x′和T\T_x′重新连接在一起的边，称之为交换边，定义S(e′)表示边e′对应的交换边构成的集合，对于失效边e′＝(x′,p(x′))来说，一条最佳交换边f′∈S(e′)，是指加入该交换边后能使新产生的最小生成树的|D(T_e′/f′)|最小，所述e′＝(x′,f(x′))表示给定的失效边，f′＝(z,z′)表示一条交换边，所述z是指在T_x中的一个节点；所述z′是指在T\T_x中的一个节点。

2.根据权利要求1所述的一种基于最小生成树的最佳交换边查找方法，其特征在于所述步骤2)采用分布式算法，获得通信网络中的最佳交换边查找问题在图模型G＝(V,E)上的解空间，具体步骤如下：

步骤21)对于给定的失效边e′＝(x′,f(x′))，遍历以x′为根的子树T_x′中的每个节点z；

步骤22)等候来自父节点的可用信息，计算|L(T_x′,z)|，同时为所有孩子节点计算可用信息并发送该信息，所述|L(T_x′,z)|，是指以节点z开始的且在图T_x′中的最长路径的长度；

步骤23)对每个本地交换边f＝(z,z′)，对|L(T\T_x′,z′)|进行分布式计算，所述本地交换边，是指在边集S(e′)中且邻近节点z的一条边；所述|L(T\T_x′,z′)|，是指以节点z′开始的且在图T\T_x′中的最长路径的长度，其中，

|L(T\T_x′,z′)|＝max{d(z′,d_k),d(z′,d_c)+γ,d(z′,d_c)+λ(p(x′)),

d(z′,u′)+d(u′,ρ_R)+μ_R-d(d_k,ρ_R)}

所述d(z′,d_k)是指以节点z′和节点d_k为端点的一条边；所述d(z′,d_c)是指以节点z′和节点d_c为端点的一条边；所述d(z′,u′)是指以节点z′和节点u′为端点的一条边；所述d(u′,ρ_R)是指以节点u′和节点ρ_R为端点的一条边；所述d(d_k,ρ_R)是指以节点d_k和节点ρ_R为端点的一条边；所述λ(p(x′))是指以节点d_c开始、进入到顶点集V_L中但不会经过节点p(x′)下方的最长路径的长度；所述u′是指在D(T)上以节点z′开始的最长路径上的距离z′最近的节点；所述ρ_R是指在以节点d_k开始且在节点集V_R中的最长路径上的，进入到V_R子树上的根节点；所述γ是指以节点d_c开始且仅包含节点集V_C中节点的最长路径的长度；所述V_C是指除节点d_c外所有节点构成的节点集合；所述μ_R是指以节点d_k开始且在节点集V_R中的最长路径的长度；

步骤24)对每个本地交换边f＝(z,z′)，对|D(T_e′/f)|进行分布式计算：|D(T_e′/f)|＝max{|D(T)|,|L(T_x′,z)|+l(f)+|L(T\T_x′,z′)|}，所述L(T_x′,z)是指以节点z开始的且在图T_x中的最长路径的长度；所述L(T\T_x′,z′)是指以节点z′开始的且在图T\T_x中的最长路径的长度；所述l(f)是指本地交换边f＝(z,z′)的长度；

步骤25)从上述这些本地交换边中，选择一个临时最佳交换边并存储加入该交换边后将会产生的新直径如果没有本地交换边存在，则创建一个虚设的侯选边，且将其新直径设为∞；

步骤26)对于每个孩子节点q∈C(z)，根据上述步骤求得的距离信息，对每个孩子节点选择一个最佳交换边候选并存储加入该交换边后将会产生的新直径再从这些孩子节点对应的最佳交换边中选择第二个临时最佳交换边所述

步骤27)定义目标最佳交换边f_best，比较第一个临时最佳交换边和第二个最佳交换边选择加入对应新直径更小的那条交换边，若则将作为目标最佳交换边f_best；若则将作为目标最佳交换边f_best；若则将或作为目标最佳交换边f_best均可；

步骤28)若以x′为根的子树T_x′中的每个节点z未被全部遍历，重复步骤22)～步骤27)；

步骤29)确定最终解空间S_olution，该解空间中包含失效边e′＝(x′,f(x′))对应的最佳交换边。