系统工程与电子技术
繫統工程與電子技術
계통공정여전자기술
SYSTEMS ENGINEERING AND ELECTRONICS
2012年
5期
1030-1035
,共6页
李振%孙新利%雷俊牛%姬国勋%刘志勇
李振%孫新利%雷俊牛%姬國勛%劉誌勇
리진%손신리%뢰준우%희국훈%류지용
多状态网络%随机流量网络%d-最小割集%边合并%状态继承
多狀態網絡%隨機流量網絡%d-最小割集%邊閤併%狀態繼承
다상태망락%수궤류량망락%d-최소할집%변합병%상태계승
为更有效的获取多状态网络系统d-最小割集(d-mincuts,d-MCs),提出一种边合并算法.算法用容量未取最大容量的边及对应取值组成的集合对表示网络状态,基于网络分割的思想,不以最小割集为基础,通过边合并、状态继承求取可行解,通过集合对的比较得到d-MCs.同时提出一个引理,更高效的求取容量下界,缩小状态空间.算法复杂度对比分析证明算法有效,且通过定义带权值的广义联络矩阵实现算法,便于编程计算.最后,通过实例分析验证了算法的有效性.
為更有效的穫取多狀態網絡繫統d-最小割集(d-mincuts,d-MCs),提齣一種邊閤併算法.算法用容量未取最大容量的邊及對應取值組成的集閤對錶示網絡狀態,基于網絡分割的思想,不以最小割集為基礎,通過邊閤併、狀態繼承求取可行解,通過集閤對的比較得到d-MCs.同時提齣一箇引理,更高效的求取容量下界,縮小狀態空間.算法複雜度對比分析證明算法有效,且通過定義帶權值的廣義聯絡矩陣實現算法,便于編程計算.最後,通過實例分析驗證瞭算法的有效性.
위경유효적획취다상태망락계통d-최소할집(d-mincuts,d-MCs),제출일충변합병산법.산법용용량미취최대용량적변급대응취치조성적집합대표시망락상태,기우망락분할적사상,불이최소할집위기출,통과변합병、상태계승구취가행해,통과집합대적비교득도d-MCs.동시제출일개인리,경고효적구취용량하계,축소상태공간.산법복잡도대비분석증명산법유효,차통과정의대권치적엄의련락구진실현산법,편우편정계산.최후,통과실례분석험증료산법적유효성.
