天津大学学报
天津大學學報
천진대학학보
JOURNAL OF TIANJIN UNIVERSITY SCIENCE AND TECHNOLOGY
2006年
7期
801-805
,共5页
被动测试%NP完全问题%近似算法
被動測試%NP完全問題%近似算法
피동측시%NP완전문제%근사산법
研究了被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况.先把该问题归结为图的顶点覆盖问题,它是一个NP完全问题;接着讨论了在网络拓扑是树的特殊情形下带权和不带权顶点覆盖问题的解,并给出了树结构上带权顶点覆盖问题的线性时间算法;然后在已有的一个近似比为2的算法基础上,结合树结构上不带权顶点覆盖问题的算法给出了图的不带权顶点覆盖问题的一个改进算法,最后用实验验证了改进算法能使观察者数目减小20%左右.
研究瞭被動測試中如何放置觀察者使得放置的數目最少併且能鑑視整箇網絡的運行情況.先把該問題歸結為圖的頂點覆蓋問題,它是一箇NP完全問題;接著討論瞭在網絡拓撲是樹的特殊情形下帶權和不帶權頂點覆蓋問題的解,併給齣瞭樹結構上帶權頂點覆蓋問題的線性時間算法;然後在已有的一箇近似比為2的算法基礎上,結閤樹結構上不帶權頂點覆蓋問題的算法給齣瞭圖的不帶權頂點覆蓋問題的一箇改進算法,最後用實驗驗證瞭改進算法能使觀察者數目減小20%左右.
연구료피동측시중여하방치관찰자사득방치적수목최소병차능감시정개망락적운행정황.선파해문제귀결위도적정점복개문제,타시일개NP완전문제;접착토론료재망락탁복시수적특수정형하대권화불대권정점복개문제적해,병급출료수결구상대권정점복개문제적선성시간산법;연후재이유적일개근사비위2적산법기출상,결합수결구상불대권정점복개문제적산법급출료도적불대권정점복개문제적일개개진산법,최후용실험험증료개진산법능사관찰자수목감소20%좌우.
