小型微型计算机系统
小型微型計算機繫統
소형미형계산궤계통
MINI-MICRO SYSTEMS
2013年
5期
1137-1140
,共4页
最大团问题%算法%上界%下界
最大糰問題%算法%上界%下界
최대단문제%산법%상계%하계
最大团问题是找出给定图中的一个最大结点子集合,使得子集合中的任意两点之间都有边相连,最大团问题是一个著名的NP-难题,在很多领域中都有着广泛的应用.本文在研究最大团问题数学性质的基础上给出该问题的一个初步降阶方法;在初步降阶的基础上给出一个求解最大团问题的上、下界方法;最后将降阶方法和上下界方法结合起来形成一个全新的降阶算法,该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.在文中还介绍了本算法和其它各类算法的优缺点,最后通过多个示例来进一步说明算法的原理及应用情况.
最大糰問題是找齣給定圖中的一箇最大結點子集閤,使得子集閤中的任意兩點之間都有邊相連,最大糰問題是一箇著名的NP-難題,在很多領域中都有著廣汎的應用.本文在研究最大糰問題數學性質的基礎上給齣該問題的一箇初步降階方法;在初步降階的基礎上給齣一箇求解最大糰問題的上、下界方法;最後將降階方法和上下界方法結閤起來形成一箇全新的降階算法,該算法不僅可以單獨使用,還可以與其它算法結閤起來使用達到更好的效果.在文中還介紹瞭本算法和其它各類算法的優缺點,最後通過多箇示例來進一步說明算法的原理及應用情況.
최대단문제시조출급정도중적일개최대결점자집합,사득자집합중적임의량점지간도유변상련,최대단문제시일개저명적NP-난제,재흔다영역중도유착엄범적응용.본문재연구최대단문제수학성질적기출상급출해문제적일개초보강계방법;재초보강계적기출상급출일개구해최대단문제적상、하계방법;최후장강계방법화상하계방법결합기래형성일개전신적강계산법,해산법불부가이단독사용,환가이여기타산법결합기래사용체도경호적효과.재문중환개소료본산법화기타각류산법적우결점,최후통과다개시례래진일보설명산법적원리급응용정황.