应急物流配送车辆路网路径实时生成方法研究
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

第三节 相对连通系数的近似定义

一 相对连通系数的近似定义

以上相对连通系数的定义比较适合于理论分析，但在实际应用时，由于问题的组合爆炸特性，在计算最大可能路径数｜Ni｜时，会遇到难以克服的组合计数问题。另外，由于不同节点的｜Ni｜值相差悬殊，在应用时并不需要｜Ni｜的精确数值，只需对其数量级做大概估计即可。因此本节引入相对连通系数的近似定义来估计｜Ni｜的数量级，以避免求｜Ni｜精确值的复杂计算。

为了便于估计任一节点对目标节点的影响，需要把网络转换成以目标节点为根的一棵树。这可以通过采用宽度优先搜索来实现。这样，网络中任一节点都对应一棵以该节点为根的子树。该子树可能产生的最大路径数就表征了对应节点对目标节点的影响大小（见图3-1）。

图3-1 表征网络节点对目标影响大小的子树

子树可能产生的最大路径数由两方面因素决定，即子树中总的边数和子树的“构型”（这里主要考虑子树的层数和每层的边数分布）。其中子树的构型起着决定性的影响，在相同的边数下，不同构型的子树可能产生的最大路径数往往有着巨大的差别。

为了量化子树构型的这种差别，需要将最优和最差的构型作为度量的基准。其中最差构型很容易找到（如图3-2所示）。

图3-2 子树的最差构型

以上两种最差构型子树可能产生的最大路径数都等于总边数 m，即在最差构型的子树中，可能产生的最大路径数是随边数 m 线性增加的。

子树的最优构型则不那么明显，为简化起见，下面分两步来寻找最优构型。

①假设子树的层数k已经确定，根据算术几何不等式，有：

其中ai为第i层的边数。

由上式可以看出，对具有m条边的子树来说，当每层边数都相等时可能产生的路径数最大，其最大值为（m/k）k。

②求最优层数k*：

假设每层边数为x＝m/k，则子树可能产生的路径数为：

作变量代换，令x＝ey, ｜Ni｜可写成：

对上式求极值，令：

求得当y＝1即x＝e时，子树可能产生的路径数最大，对应的最优层数为k*＝m/e。

综合①、②可知，对具有m条边的子树来说，当层数k＝m/e，且每层边数相等时，可能产生的路径数最大，对应的最大路径数｜ Ni｜ ＝em/e，即在最优构型的子树中，可能产生的最大路径数是随边数m指数增加的。

任一子树构型可看作以上最优构型和最差构型的线性组合，其可能产生的最大路径数由相应的线性增长项（最差构型）和指数增长项（最优构型）所占的比例决定。为了量化这一比例，本书引入子树构型的特征向量的概念，具体如下。

定义：如果T为最大层数为m的一棵树，那么T的特征向量是m维向量ST∈Rm，其中ST的各个分量分别为对应层的边数。

两棵树的特征向量之间的距离与普通向量之间的距离不同，定义如下。如果u∈Rm, v∈Rn（m＜n），是两棵树的特征向量，u和v之间的距离记作dist（u, v），普通向量u′和v之间的距离为u′-v，其中u′是通过空位填零将u扩展到Rn所得向量，即有：dist（u, v）＝‖u′-v‖。

这样，就可以通过特征向量之间的相对距离来度量一个子树的构型与最优构型之间的偏离程度：

其中，λ是归一化的任一构型到最优构型的相对距离；

ST是任一子树构型的特征向量；

Smin是最差构型的特征向量（从两种最差构型中任选一种作为标准即可）；

Smax是最优构型的特征向量。

从上式可以看出，当ST为最差构型时，到最优构型的相对距离最大，这时λ＝1，可能产生的最大路径数为总边数m；当ST为最优构型时，到最优构型的相对距离最小，这时λ＝0，可能产生的最大路径数为em/e。

下面根据以上边界条件从数学角度来推导任一子树可能产生的最大路径数的估计表达式。如前所述，子树可能产生的最大路径数由子树总边数和子树的构型（这里等价于相对距离λ）两方面因素决定，因此可设其为子树边数和到最优构型的相对距离的函数f（λ, m）。当边数m固定时，子树可能产生的最大路径数主要由最优构型对应的指数增长项所占的比例决定，因此可认为这时f是随λ按指数变化的，可设：

边界条件可写为：

解此方程组得：a＝ln m-m/e, b＝m/e, c＝1

由此得到任一子树可能产生的最大路径数的估计表达式为：

最后得到相对连通性系数的近似定义如下：

二 相对连通系数近似定义的递归计算方法

观察相对连通系数近似定义的定义方法，发现其中表征节点对应子树形状的特征向量的计算具有递归嵌套的特点（如图3-3所示）。

图3-3 相对连通性系数计算算法原理

由此想到，可用子树中下一级节点已有的特征向量来计算上一级节点对应的特征向量，这样只用统计每个节点子树当前层的边数，从而可以设计递归算法一次求得所有节点相对目标节点的相对连通系数，算法的伪代码如下（详细实现代码见附录A）。

    Vector ComputeRCC（rootVertex）
    ｛
      //叶子节点处理
      If（rootVertex- ＞childNum＝ ＝0）｛
        //对于叶子节点子树为空，因此相对连通系数为0
        rootVertex- ＞RCC＝0；
      saveRCCToFile（rootVertex- ＞RCC）；
      rootVertex- ＞edgeNum＝0；
      return 0；
    ｝
     //中间节点处理
    Else ｛
     //对于当前节点的所有下一级节点的特征向量求和，并统计下一级子树边数和
      For（i＝0; i＜rootVertex- ＞childNum; i+ +）｛
        extendVector+ ＝ComputeRCC（rootVertex- ＞childVertex ［i］）；
        rootVertex - ＞edgeNum + ＝rootVertex - ＞childVertex ［i］  - ＞
edgeNum；
    ｝

以上递归算法的算法复杂度与遍历算法的复杂度相近，对于n个节点的网络，求所有节点相对某一目标点的相对连通系数只需一次遍历即可，时间复杂度是O（n）；即使要求一次求出所有节点相对网络中所有目标点的相对连通系数，时间复杂度也只达到O（n2）。

采用以上递归算法计算相对连通系数还有以下好处。

无线传感器网络这一先进的通信和监测技术越来越多地被应用到应急物流管理中，在突发事件中受灾地区通信基础设施损毁的情况下，使用无线传感器网络可以在最短的时间内恢复通信，并实时监测配送道路的动态变化。基于相对连通系数的无线传感器网络节能路由算法的研究是这一领域今后的一个重要研究方向。在无线传感器网络路由算法中，通常需要监测网络中各节点的通信负载状况，及时进行动态均衡，以降低重要节点的能耗，提高无线传感器网络的整体寿命。相对连通系数可用来度量节点在网络中承担的通信任务的繁重程度，这时采用以上递归算法求相对连通系数就体现出其特别适合于无线传感器网络分布式计算结构的优点。

上一章目录下一章