首页 | 本学科首页   官方微博 | 高级检索  
     

一种求解有向图最小反馈节点集的搜索算法
引用本文:蔡烜,黄竞伟,简国强.一种求解有向图最小反馈节点集的搜索算法[J].计算机工程,2006,32(4):67-69.
作者姓名:蔡烜  黄竞伟  简国强
作者单位:武汉大学计算机学院,武汉,430072
摘    要:反馈节点集问题源于组合电路的设计,在预防计算机操作系统的死锁、VLSI芯片设计、计算机程序证明以及贝叶斯推论等方面部有极其重要的应用。最小反馈节点集问题是一个NP完全问题,很难准确求解。该文在计算流程、图的约减操作以及贪婪函数3个方面对以前求解该问题的贪婪随机适应性搜索算法作了改进。实验表明改进的算法无论在计算结果方面还是在计算稳定性方面都要优于前者,同时还在一定程度上减少了计算时间。

关 键 词:反馈节点集  贪婪随机适应性搜索过程  局部搜索
文章编号:1000-3428(2006)04-0067-03
收稿时间:2005-02-24
修稿时间:2005-02-24

A Search Algorithm for Computing Minimum Feedback Vertex Set of a Directed Graph
CAI Xuan,HUANG Jingwei,JIAN Guoqiang.A Search Algorithm for Computing Minimum Feedback Vertex Set of a Directed Graph[J].Computer Engineering,2006,32(4):67-69.
Authors:CAI Xuan  HUANG Jingwei  JIAN Guoqiang
Affiliation:School of Computer, Wuhan University, Wuhan 430072
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.
Keywords:Feedback vertex set  Greedy randomized adaptive search procedure  Local search
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号