论文部分内容阅读
在实际应用中，不确定性是许多系统的固有特性，如电力传输网中的元器件、数据通信网中的节点都存在着发生故障的概率，交通运输网中也有着发生拥塞的概率等。可将这类应用中的系统建模成不确定图，从而将问题转化成不确定图中的问题来解决。不确定图最可靠最大流问题是指在不确定图中可以传递最大流的多个流分布中选择可靠性最高的一个。该问题能够很好的解决诸如构建可靠性网络、可靠传输路径的选择以及系统薄弱环节的分析等一系列问题。 针对现有的最可靠最大流算法时间复杂度较高，难以应用于大规模网络的不足，本文给出负权群落的概念，并借鉴最小费用流中平移思想提出了基于负权群落消去的算法(NCEA)。NCEA算法首先求得一个最大流分布，然后在该最大流分布对应的剩余图中查找负权群落，通过负权群落的消去得到可靠性更高的最大流分布，接着继续在更新后的剩余图中查找负权群落并消去，直到剩余图中不存在负权群落，此时求得的最大流分布经论证即为最可靠最大流。然而在NCEA算法中涉及到组合运算，容易产生组合爆炸，为此提出了基于剪枝策略的改进算法(PBA)，PBA算法利用若一个组合满足条件，则包含该组合的其余组合均不满足条件的性质很好的解决了组合爆炸的问题，并显著的提高了算法的性能。 为了进一步提高算法性能，满足对算法速度要求很高而精度要求不高的应用需求，本文根据负权群落的特点给出了基于单环消去的近似算法(OCEA)，该算法具有很好的性能，能够很快的求出一个近似解，但算法精度波动性较大，为此，本文又提出的另一个基于双环消去的近似算法(TCEA)，该算法具有较高的精度，并且效率只比OCEA算法稍低。 最后本文设计了一系列实验来验证算法的正确性和性能。实验表明NCEA算法及PBA算法均能够得到正确的解，在性能上优于已有的SDBA算法，其中PBA算法优势达到一到两个数量级。而近似算法OCEA比PBA算法又快到一个数量级，但是在最差情况下OCEA算法的精度不足50％，而TCEA算法可使算法精度在最差情况下提高到80％以上。