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

《一种求解有向图最小反馈节点集的搜索算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第32卷第4期计算机工程2006年2月Vol.32№4ComputerEngineeringFebruary2006·软件技术与数据库·文章编号：1000—3428(2006)04—0067—03文献标识码：A中图分类号：TP301.6一种求解有向图最小反馈节点集的搜索算法蔡烜，黄竞伟，简国强（武汉大学计算机学院，武汉430072）摘要：反馈节点集问题源于组合电路的设计，在预防计算机操作系统的死锁、VLSI芯片设计、计算机程序证明以及贝叶斯推论等方面都有极其重要的应用。最小反馈节点集问题是一个NP完全问题，很难准确求解。该文在计算流程、图的约减操作以及贪婪函数3个方面对以前求解

2、该问题的贪婪随机适应性搜索算法作了改进。实验表明改进的算法无论在计算结果方面还是在计算稳定性方面都要优于前者，同时还在一定程度上减少了计算时间。关键词：反馈节点集；贪婪随机适应性搜索过程；局部搜索ASearchAlgorithmforComputingMinimumFeedbackVertexSetofaDirectedGraphCAIXuan,HUANGJingwei,JIANGuoqiang（SchoolofComputer,WuhanUniversity,Wuhan430072）【Abstract】Feedbackvertexsetproblemsoriginatedfr

3、omtheareaofcombinatorialcircuitdesign,andhavefoundnumerousimportantapplicationsinotherfieldssuchasdeadlockpreventioninoperatingsystems,VLSIdesign,programverification,Bayesianinferenceandsoon.AstheminimumfeedbackvertexsetproblemisNP-complete,itishardtobesolvedexactly.Thispaperimprovestheprevi

4、ousalgorithmfortheprobleminthreeaspects:computingprocess，contractionoperationsandgreedyfunction.Theexperimentsdemonstratethattheimprovedalgorithmismuchbetterthanthepreviousonenomatterinthequalityofsolutionorthestabilityofsolution.Tosomedegree,itreducestherunningtimeatthesametime.【Keywords】Fe

5、edbackvertexset;Greedyrandomizedadaptivesearchprocedure;Localsearch有向图G（V，E）的一个反馈节点集（FeedbackVertexSet，搜索阶段，过程如下：FVS）F是V的一个子集，使得从图G中删除F中的所有节ProcedureGRASP（Max_Iterations）点及其与它们相关联的边后所得的余图G＇没有环。如果FSolution←φ；是G中所有反馈节点集中基数最小的一个，就称它为G的一Fori:=1toMax_IterationsdoBegin个最小反馈节点集（MinimumFeedbackVerte

6、xSet，MFVS）。(1)Solution←Greedy_Randomized_Construction（α，h）；其实，反馈节点集问题是一类特殊的集合覆盖问题，目(2)Solution←Local_Search（Solution）；的就是要找出一个基数最小的节点集合来覆盖图中的所有(3)Update_Solutio（Solution，Best_Solution）；[7]环。它已被证明是NP完全的，准确计算出有向图的最小反End；馈节点集是很困难的。迄今为止人们也只不过给出了针对某在可行解的构造阶段，首先初始化可行解和候选元素集些特殊类型图的一些多项式时间算法如文献[5]，而

7、对于一般C（C中包含所有可能被加到可行解中的元素），然后通过某图，计算其最小反馈节点集还是求助于近似算法，比如个反复迭代的过程构造出一个可行解。在其每一次迭代中，PardalosP．M．等人在文献[1]中应用了贪婪随机适应性搜索根据预先给出的贪婪函数h对候选元素集C中的各个元素进过程(GreedyRandomizedAdaptiveSearchProcedure，GRASP)行评估并通过参数α（其中α是一个用来调节算法的贪婪程度求解有向图的反馈节点集问题。与随机程度的参数，α为1表示算法是纯