CAJ | 학술논문

最可靠最大流是不确定图中可靠性最高的最大流,它是传统最大流问题在不确定图上的自然延伸.现有的最可靠最大流算法SDBA时间复杂性较高,无法满足实际中不同应用的需求,为此,文中提出一种具有普遍适用性的最可靠最大流解决方案.该方案包含面向不同需求的3种算法:基于负权群落消去的NWCE算法、基于时间约束优先单环消去的SPEA-t算法和基于概率阈值约束优先单环消去的SPEA-p算法.其中.NWCE算法借鉴最小费用最大流的“流平移”思想并基于文中提出的负权群落概念,在辅助剩余图中不断地消去可使可靠性增加而流量不变的负权群落,可证当消去所有负权群落时对应的最大流即为最可靠最大流.根据负权群落中由单环组成的群落占很高比例且相对于多环组成的群落更易查找和消去的性质,同时考虑到NWCE算法为了获得最优解,往往为了消去最后少数几个对概率提高贡献很小的负权群落却花费了很长时间的现象,提出SPEA-t和SPEAp两种快速近似算法,前者是以规定时间内尽可能逼近最优解为目标,后者是以最少时间达到预设的概率阈值为目标,它们都采用了优先消去概率时间效益较好的单环群落的策略,加快对最优解的逼近速度,减少或放弃时间开销较大的多环群落的消去,以满足那些对算法时间性能要求很高而结果以近似最优即可的应用需求.实验表明,相对于SDBA算法,NWCE算法结合概率剪枝策略在时间性能上有了数量级的提高,而SPEA-t算法和SPEAp算法则具有更高的性能和更好的适用性.
최가고최대류시불학정도중가고성최고적최대류,타시전통최대류문제재불학정도상적자연연신.현유적최가고최대류산법SDBA시간복잡성교고,무법만족실제중불동응용적수구,위차,문중제출일충구유보편괄용성적최가고최대류해결방안.해방안포함면향불동수구적3충산법:기우부권군락소거적NWCE산법、기우시간약속우선단배소거적SPEA-t산법화기우개솔역치약속우선단배소거적SPEA-p산법.기중.NWCE산법차감최소비용최대류적“류평이”사상병기우문중제출적부권군락개념,재보조잉여도중불단지소거가사가고성증가이류량불변적부권군락,가증당소거소유부권군락시대응적최대류즉위최가고최대류.근거부권군락중유단배조성적군락점흔고비례차상대우다배조성적군락경역사조화소거적성질,동시고필도NWCE산법위료획득최우해,왕왕위료소거최후소수궤개대개솔제고공헌흔소적부권군락각화비료흔장시간적현상,제출SPEA-t화SPEAp량충쾌속근사산법,전자시이규정시간내진가능핍근최우해위목표,후자시이최소시간체도예설적개솔역치위목표,타문도채용료우선소거개솔시간효익교호적단배군락적책략,가쾌대최우해적핍근속도,감소혹방기시간개소교대적다배군락적소거,이만족나사대산법시간성능요구흔고이결과이근사최우즉가적응용수구.실험표명,상대우SDBA산법,NWCE산법결합개솔전지책략재시간성능상유료수량급적제고,이SPEA-t산법화SPEAp산법칙구유경고적성능화경호적괄용성.