计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2008年
26期
48-50
,共3页
极大独立集%界%贪婪算法%图论
極大獨立集%界%貪婪算法%圖論
겁대독립집%계%탐람산법%도론
最大独立集问题是图论中典型的组合优化问题,有着广泛的实际应用价值.分析了现有独立数的界公式后给出了新的上界公式,并通过分析贪婪算法和独立集自身的特征,给出了新的求解极大独立集的算法,并证明了其确定性.然后用实例验证了该算法的有效性.
最大獨立集問題是圖論中典型的組閤優化問題,有著廣汎的實際應用價值.分析瞭現有獨立數的界公式後給齣瞭新的上界公式,併通過分析貪婪算法和獨立集自身的特徵,給齣瞭新的求解極大獨立集的算法,併證明瞭其確定性.然後用實例驗證瞭該算法的有效性.
최대독립집문제시도론중전형적조합우화문제,유착엄범적실제응용개치.분석료현유독립수적계공식후급출료신적상계공식,병통과분석탐람산법화독립집자신적특정,급출료신적구해겁대독립집적산법,병증명료기학정성.연후용실례험증료해산법적유효성.
