一种求解有向图最小反馈节点集的搜索算法  

A Search Algorithm for Computing Minimum Feedback Vertex Set of a Directed Graph

作　　者：蔡烜[1] 黄竞伟[1] 简国强[1] 

机构地区：[1]武汉大学计算机学院,武汉430072

出　　处：《计算机工程》2006年第4期67-69,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60133010)

摘　　要：反馈节点集问题源于组合电路的设计,在预防计算机操作系统的死锁、VLSI芯片设计、计算机程序证明以及贝叶斯推论等方面都有极其重要的应用。最小反馈节点集问题是一个NP完全问题,很难准确求解。该文在计算流程、图的约减操作以及贪婪函数3个方面对以前求解该问题的贪婪随机适应性搜索算法作了改进。实验表明改进的算法无论在计算结果方面还是在计算稳定性方面都要优于前者,同时还在一定程度上减少了计算时间。Feedback vertex set problems originated from the area of combinatorial circuit design, and have found numerous important applications in other fields such as deadlock prevention in operating systems, VLSI design, program verification, Bayesian inference and so on. As the minimum feedback vertex set problem is NP-complete, it is hard to be solved exactly. This paper improves the previous algorithm for the problem in three aspects： computing process, contraction operations and greedy function. The experiments demonstrate that the improved algorithm is much better than the previous one no matter in the quality of solution or the stability of solution. To some degree, it reduces the running time at the same time.

关 键 词：反馈节点集 贪婪随机适应性搜索过程 局部搜索 

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