求极小碰集的蛛网算法  

Cobweb algorithm of computing minimum hitting sets

作　　者：何士玉[1] 刘志刚[1] 徐建芳[1] 李文帆[1] 

机构地区：[1]西南交通大学电气工程学院,成都610031

出　　处：《计算机应用研究》2013年第3期684-687,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(U1134205;51007074);国家教育部新世纪优秀人才支持计划项目(NECT-08-0825);中央高校基本科研业务费专项资金资助项目(SWJTU11CX141)

摘　　要：为降低空间复杂度和减少搜索时间,结合极小碰集的特点和生物学中蜘蛛捕食思想,提出了一种搜索极小碰集的蛛网算法。该方法考虑集合之间的相关性,并构造能在蛛网上寻路的访问蜘蛛用于寻找蛛网内集合的所有极小碰集。在该算法中,所提出的访问蜘蛛生成和搜索策略能够降低空间复杂度和减少搜索时间。将此算法与其他的极小碰集算法进行比较,实验结果表明,该算法在保证得到所有极小碰集的前提下,具有较低的空间复杂度和较高的时间效率。To reduce space complexity and reduce search time, this paper proposed a cobweb algorithm for search minimum hitting sets, which combined the characteristics of minimum hitting sets and thought on spider prey in biology. It considered this method the correlation between the sets, and structured the visiting spider which could find the path of the cobweb access to find all minimum hitting sets of sets within the cobweb. In the algorithm, the generation of visiting spiders and search strate- gy could reduce space complexity and reduce search time. Compared with the other algorithms which computing the minimum hitting sets, the results of experiments show that under the premise of guaranteeing to get all minimum hitting sets, the algo- rithm has Bower space comolexitv and higher efficiency,

关 键 词：基于模型诊断 极小碰集 蛛网 访问蜘蛛 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]