CAJ | 학술논문

文中首先基于可能世界模型提出了不确定图的最可靠最大流问题和可靠性计算模型,这对于构建可靠性网络、可靠传输路径选择以及系统薄弱环节分析等一系列实际问题具有重要意义；然后基于简单路径组合思想提出了一种求解最可靠最大流的算法SPCA,通过简单路径流量的组合,在无需求得所有最大流分布的情况下获得最可靠最大流,并在组合过程中引入概率剪枝与约束剪枝策略,对无效组合进行过滤,从而显著地提高了算法效率；接着文中针对SPCA算法易受路径数量及瓶颈容量影响的问题,又提出一种基于状态空间划分的最可靠最大流算法SDBA,该算法的主要思想是将不确定图所蕴含的子图空间划分为互不相交且满足最大流值的闭合区间集合,进而寻找所有闭合区间中概率最大的下界状态,经证明这个下界状态对应子图中的最大流分布为最可靠最大流；最后通过实验,比较了两种算法的性能.实验结果表明SDBA算法相对于SPCA算法其空间复杂度有一定的增加,但时间复杂度方面具有较大的优势,能够很好地解决SPCA算法性能受制于容量的问题,具有更好的性能与适用性.
문중수선기우가능세계모형제출료불학정도적최가고최대류문제화가고성계산모형,저대우구건가고성망락、가고전수로경선택이급계통박약배절분석등일계렬실제문제구유중요의의；연후기우간단로경조합사상제출료일충구해최가고최대류적산법SPCA,통과간단로경류량적조합,재무수구득소유최대류분포적정황하획득최가고최대류,병재조합과정중인입개솔전지여약속전지책략,대무효조합진행과려,종이현저지제고료산법효솔；접착문중침대SPCA산법역수로경수량급병경용량영향적문제,우제출일충기우상태공간화분적최가고최대류산법SDBA,해산법적주요사상시장불학정도소온함적자도공간화분위호불상교차만족최대류치적폐합구간집합,진이심조소유폐합구간중개솔최대적하계상태,경증명저개하계상태대응자도중적최대류분포위최가고최대류；최후통과실험,비교료량충산법적성능.실험결과표명SDBA산법상대우SPCA산법기공간복잡도유일정적증가,단시간복잡도방면구유교대적우세,능구흔호지해결SPCA산법성능수제우용량적문제,구유경호적성능여괄용성.