摘要： 反馈节点集问题源于组合电路的设计，在预防计算机操作系统的死锁、VLSI 芯片设计、计算机程序证明以及贝叶斯推论等方面都有极其重要的应用。最小反馈节点集问题是一个NP 完全问题，很难准确求解。该文在计算流程、图的约减操作以及贪婪函数3 个方面对以前求解该问题的贪婪随机适应性搜索算法作了改进。实验表明改进的算法无论在计算结果方面还是在计算稳定性方面都要优于前者，同时还在一定程度上减少了计算时间

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

Abstract: 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

Key words: Feedback vertex set; Greedy randomized adaptive search procedure; Local search