一种新的启发式边排序策略及其性能分析

作     者：潘竹生 莫毓昌 钟发荣 刘轩 伍欢 PAN Zhu-sheng;MO Yu-chang;ZHONG Fa-rong;LIU Xuan;WU Huan

作者机构：浙江师范大学数理与信息工程学院浙江金华321004 

基　　金：国家自然科学基金资助项目(61272130) 浙江省自然科学基金资助项目(Y1100689) 浙江省重中之重学科开放课题资助项目(ZSDZZZZXK24) 浙江省教育厅项目(Y201328072) 

出 版 物：《计算机工程与科学》 (Computer Engineering & Science)

年 卷 期：2014年第36卷第11期

页      码：2119-2127页

摘      要：网络可靠度BDD分析方法的计算复杂度与BDD尺度线性相关,而BDD尺度严重依赖边排序质量。由于求解最优边排序是一个NP问题,在实际应用中,通常采用启发式边排序策略如BFS(Breadth-First-Search)和DFS(Depth-First-Search)。针对边排序问题,从分析基于边界集(Boundary Set)的BDD构建方法 BDD-BS出发,将边界集思想应用于边排序过程,提出了一种新的启发式边排序策略。性能分析和大量实验表明,新设计的边排序策略性能优于经典的DFS和BFS策略,该结果为网络可靠度BDD分析方法在大规模网络中的应用拓展了新的空间。

主 题 词：网络可靠度 二叉决策图 边界集 边排序 

学科分类：07[理学] 070104[070104] 0701[理学-数学类] 

核心收录：

D　O　I：10.3969/j.issn.1007-130X.2014.11.011

馆 藏 号：203128913...