淮阴工学院学报
淮陰工學院學報
회음공학원학보
JOURNAL OF HUAIYIN INSTITUTE OF TECHNOLOGY
2010年
3期
15-18
,共4页
雷习军%赵杏利%李小平%何尚录
雷習軍%趙杏利%李小平%何尚錄
뢰습군%조행리%리소평%하상록
下模集函数%近似算法%性能保证%最优解
下模集函數%近似算法%性能保證%最優解
하모집함수%근사산법%성능보증%최우해
为有效求得背包约束条件下不同问题的解,我们往往采取不同的方式,以获得其最优解.但更多情况下,我们无法找出其精确最优解,这时我们将选取不同的变量,通过有效的算法,以获得该问题的近似解.我们利用线性规划的知识,分析最大化非减下模集函数在背包约束下近似算法,得出该算法计算复杂性为O(n5),性能保证为1-e-1.
為有效求得揹包約束條件下不同問題的解,我們往往採取不同的方式,以穫得其最優解.但更多情況下,我們無法找齣其精確最優解,這時我們將選取不同的變量,通過有效的算法,以穫得該問題的近似解.我們利用線性規劃的知識,分析最大化非減下模集函數在揹包約束下近似算法,得齣該算法計算複雜性為O(n5),性能保證為1-e-1.
위유효구득배포약속조건하불동문제적해,아문왕왕채취불동적방식,이획득기최우해.단경다정황하,아문무법조출기정학최우해,저시아문장선취불동적변량,통과유효적산법,이획득해문제적근사해.아문이용선성규화적지식,분석최대화비감하모집함수재배포약속하근사산법,득출해산법계산복잡성위O(n5),성능보증위1-e-1.
