摘要
在被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况是一个很有实际应用价值的问题·先证明了该问题是一个NP完全问题;接着讨论了在网络拓扑是树的特殊情形下该问题的解,并给出了针对树结构的一个线性时间算法;然后在一个已有的近似比为2的算法基础上给出了一个改进算法并证明了其近似比为2-O(1),最后用实验来验证了改进算法的有效性,指明了进一步的研究方向·
The problem of how to place the observers in passive testing while assuring they can monitor all the behavior of a network and the number of them is the smallest is an interesting and useful problem. First, this problem is proved to be an NP-complete problem. Then a special case in which the topology of network is a tree is discussed and a linear time algorithm for it is presented. Based on the thought of tree topology an improved approximate algorithm is proposed and the approximate proportion of the improved algotithm is 2-O( 1 ) . Finally, a simulating experiment is conducted to illustrate the effectiveness of the improved algorithm and future extensions are discussed.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2005年第10期1815-1819,共5页
Journal of Computer Research and Development
基金
国家自然科学基金重大研究计划项目(90104010)
国家自然科学基金项目(60241004)
国家"九七三"重点基础研究发展规划基金项目(2003CB314801)
关键词
被动测试
NP完全问题
通信有限状态机
passive testing
NP-complete problem
communicating finite state machine