求解组合拍卖问题最大值的贪婪算法 被引量：8

1

作者 罗亮 贾欣鑫 何尚录 《黑龙江科技学院学报》 CAS 2008年第5期382-384,共3页

为有效解决组合拍卖问题,从基约束条件下,下模函数最大值问题的基本结论出发,逐步过渡到求解组合拍卖问题的贪婪算法,给出一种新的近似算法,分析了该算法的性能保证。该算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法结合,从而使... 为有效解决组合拍卖问题,从基约束条件下,下模函数最大值问题的基本结论出发,逐步过渡到求解组合拍卖问题的贪婪算法,给出一种新的近似算法,分析了该算法的性能保证。该算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法结合,从而使其具有更好的性能保证,并从理论上证明了该算法的可靠性和有效性。 展开更多

关键词 贪婪算法 组合拍卖 下模函数 性能保证

下载PDF 职称材料

求解一类线性规划问题的原始贪婪算法和对偶贪婪算法及其相互关系 被引量：3

2

作者 黄辉 梁国宏 +1 位作者 张生 何尚录 《兰州交通大学学报》 CAS 2007年第1期149-152,共4页

给出了求解一类线性规划问题的一种贪婪算法和求解其对偶问题的一种贪婪算法,并讨论了这两种算法的若干性质及其相互关系.

关键词 线性规划问题 对偶问题 贪婪算法 下模函数

下载PDF 职称材料

剖分拟阵约束下求解下模函数最大值问题的一种贪婪算法 被引量：1

3

作者 罗亮 崔俊峰 +2 位作者 樊亮 贾欣鑫 何尚录 《淮阴工学院学报》 CAS 2009年第3期6-10,共5页

给出了求解剖分拟阵约束下,下模函数最大值问题的一种新的近似算法,这一算法是改进的贪婪算法,即将局部搜索法与贪婪算法相结合,使其整体具有更好的性能保证。同时从理论上证明了这一算法的可靠性。最后通过具体算例验证了算法的有效性。

关键词 组合最优化问题 剖分拟阵 下模函数 近似算法 性能保证

下载PDF 职称材料

求解预支约束下商品批发零售问题的近似算法 被引量：1

4

作者 罗亮 魏万喜 +1 位作者 贾欣鑫 何尚录 《兰州交通大学学报》 CAS 2009年第6期138-140,共3页

研究了求解预支约束下批发零售问题的一种新的近似算法,这一算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法相结合并从理论上分析了该算法的可靠性和有效性,最后得出了该算法的性能保证为1-e-1.

关键词 预支约束 下模函数 近似算法 性能保证

下载PDF 职称材料

拟阵约束下非负非减下模函数最大值问题的近似算法及其性能保证

5

作者 梁国宏 刘光荣 王武民 《德州学院学报》 2012年第4期9-10,共2页

下模函数的最值问题在组合优化问题中有着广泛的应用,给出了具有剥分拟阵约束下非负非减下模函数最大值问题的近似算法,并讨论了所给算法的性能保证.

关键词 组合优化问题 下模函数 近似算法 性能.

下载PDF 职称材料

求解具有均匀拟阵约束下下模函数的最大值问题的贪婪算法及其性能保证

6

作者 梁国宏 王武民 《青海民族大学学报（教育科学版）》 2011年第5期25-27,共3页

下模函数的最值问题在组合优化问题中有着广泛的应用,本文给出了具有均匀拟阵约束下下模函数最大值问题的贪婪近似算法,并讨论了所给算法的性能保证.

关键词 组合优化问题 下模函数 近似算法 性能保证

下载PDF 职称材料

求解双背包约束下下模集函数最大问题的近似算法及其性能保证

7

作者 赵杏利 李小平 +1 位作者 雷习军 何尚录 《洛阳理工学院学报（自然科学版）》 2009年第3期56-59,共4页

对双背包约束条件下下模函数最大值问题用近似算法求解,其性能保证为1-e-1,该算法的时间复杂性为ο(n5).

关键词 下模函数 近似算法 性能保证

下载PDF 职称材料

物资采购流行性预测问题的蚁群算法

8

作者 罗亮 罗明 +2 位作者 李小平 张馨文 周瑞 《应用数学进展》 2018年第4期328-333,共6页

物资采购流行性预测是现代物流中的一个重要环节,是一种典型的组合优化问题。为使物流生产达到最佳效果,提出了一种基于下模函数下的蚁群算法,对物资采购中的流行性预测问题作出解答。该蚁群算法结合了贪婪算法是对一般蚁群算法的改进,... 物资采购流行性预测是现代物流中的一个重要环节,是一种典型的组合优化问题。为使物流生产达到最佳效果,提出了一种基于下模函数下的蚁群算法,对物资采购中的流行性预测问题作出解答。该蚁群算法结合了贪婪算法是对一般蚁群算法的改进,最后以实验表明该算法在解决物资采购流行性预测问题是有效的。 展开更多

关键词 组合优化 蚁群算法 下模函数 物资采购

下载PDF 职称材料

求解多维约束下下模函数最大值的改进贪婪算法

9

作者 张生 何尚录 《系统科学与数学》 CSCD 北大核心 2009年第4期512-518,共7页

提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.

关键词 组合优化 下模函数 贪婪算法 性能保证.

原文传递

求解下模函数最大值问题的近似算法及其性能保证

10

作者 梁国宏 王武民 《上海第二工业大学学报》 2011年第1期26-28,共3页

下模函数的最值问题在组合优化问题中有着广泛的应用,给出了具有拟阵交构成的独立系统约束下模函数的最大值问题的近似算法,并讨论了所给算法的性能保证。

关键词 组合优化问题 下模函数 近似算法 性能保证

下载PDF 职称材料

拟阵交构约束的下模函数最大值问题的近似算法及其分析

11

作者 张立群 《淮海工学院学报（自然科学版）》 CAS 2014年第4期6-8,共3页

下模函数的最大值问题是组合优化中的核心问题,然而求解下模函数最大值问题是一个NP-难问题,故人们降低要求,求解它的最优近似解.在拟阵约束的基础上,进一步研究拟阵交构成的独立系统下求解下模函数最大值问题,运用了近似领域算法,得到... 下模函数的最大值问题是组合优化中的核心问题,然而求解下模函数最大值问题是一个NP-难问题,故人们降低要求,求解它的最优近似解.在拟阵约束的基础上,进一步研究拟阵交构成的独立系统下求解下模函数最大值问题,运用了近似领域算法,得到下模函数的近似最优解,并讨论给出了近似算法的性能分析,得出近似解的近似度≤(αm+1). 展开更多

关键词 独立系统 下模函数 拟阵交构 邻域算法

下载PDF 职称材料

求解下模集函数最大值问题的局部搜索算法 被引量：5

12

作者 王武民 张防防 +1 位作者 柘晓莉 何尚录 《温州大学学报（自然科学版）》 2008年第3期12-17,共6页

给出了求解具有简单约束的下模集函数最大值问题的一种局部搜索算法,并讨论了所给算法的性能保证.该算法的基本思想是:算法每次迭代总是在当前近似解集的邻域内,求出使目标函数取得最大的集合,将其作为新的近似解集.分析表明,所给算法... 给出了求解具有简单约束的下模集函数最大值问题的一种局部搜索算法,并讨论了所给算法的性能保证.该算法的基本思想是:算法每次迭代总是在当前近似解集的邻域内,求出使目标函数取得最大的集合,将其作为新的近似解集.分析表明,所给算法是一种多项式时间近似算法. 展开更多

关键词 组合优化 下模集函数 近似算法 性能保证

下载PDF 职称材料

求解组合拍卖问题的一种贪婪算法 被引量：1

13

作者 贾欣鑫 罗亮 +1 位作者 郭丽峰 何尚录 《温州大学学报（自然科学版）》 2009年第3期32-36,共5页

为有效解决组合拍卖问题,从下模集函数最大值问题的基本结论出发,将部分穷举法与贪婪算法相结合,给出了一种求解组合拍卖问题的新算法——改进的贪婪算法,并从理论上证明了所给算法具有更好的性能保证.

关键词 组合拍卖 下模集函数 贪婪算法

下载PDF 职称材料

求解下模福利问题的一种随机算法及其性能保证 被引量：1

14

作者 李小平 雷习军 +1 位作者 赵杏利 何尚录 《兰州交通大学学报》 CAS 2011年第1期139-141,共3页

给出了求解下模福利问题最大值的一种随机算法,并证明了所给算法的性能保证为1-e-1.

关键词 下模福利问题 下模集函数 近似算法 性能保证

下载PDF 职称材料

求解背包约束下下模集函数近似算法及性能保证 被引量：1

15

作者 雷习军 赵杏利 +1 位作者 李小平 何尚录 《淮阴工学院学报》 CAS 2010年第3期15-18,共4页

为有效求得背包约束条件下不同问题的解,我们往往采取不同的方式,以获得其最优解。但更多情况下,我们无法找出其精确最优解,这时我们将选取不同的变量,通过有效的算法,以获得该问题的近似解。我们利用线性规划的知识,分析最大化非减下... 为有效求得背包约束条件下不同问题的解,我们往往采取不同的方式,以获得其最优解。但更多情况下,我们无法找出其精确最优解,这时我们将选取不同的变量,通过有效的算法,以获得该问题的近似解。我们利用线性规划的知识,分析最大化非减下模集函数在背包约束下近似算法,得出该算法计算复杂性为O(n5),性能保证为1-e-1。 展开更多

关键词 下模集函数 近似算法 性能保证 最优解

下载PDF 职称材料

多维背包约束下单调非减下模函数最大值的贪婪算法 被引量：1

16

作者 宫兴荣 何尚录 杨留猛 《四川兵工学报》 CAS 2012年第12期126-128,共3页

给出了求解多维背包约束下单调非减下模集函数最大值的近似算法,证明了该算法的性能保证是1-e-1。该算法结合了部分穷举法与贪婪算法,是对贪婪算法的一种改进,该算法的时间复杂性为O(n4)。

关键词 组合最优化 背包约束 下模集函数 贪婪算法

下载PDF 职称材料

预算型最大覆盖问题的近似算法

17

作者 张生 何尚录 《河北大学学报（自然科学版）》 CAS 北大核心 2008年第1期7-9,13,共4页

研究了给定预算常数的最大覆盖问题,给出了求解此问题的改进贪婪算法,得到了性能保证为1-e-1的近似算法.

关键词 覆盖问题 贪婪算法 下模集函数 性能保证

下载PDF 职称材料

一种求解下模集函数最大值问题的近似算法

18

作者 李小平 王利红 何尚录 《黑龙江科技学院学报》 CAS 2010年第5期391-394,共4页

下模集函数最大值问题属于NP-难问题,难以得到有效的求解方法。针对这一情况,运用概率分布方法,给出了求解该问题的一种近似算法,并证明算法的性能保证为1/3。组合优化问题实例证明了该算法的有效性。该研究可为求解下模集函数最大值问... 下模集函数最大值问题属于NP-难问题,难以得到有效的求解方法。针对这一情况,运用概率分布方法,给出了求解该问题的一种近似算法,并证明算法的性能保证为1/3。组合优化问题实例证明了该算法的有效性。该研究可为求解下模集函数最大值问题提供新的思路。 展开更多

关键词 下模集函数 最大值问题 近似算法 性能保证 组合优化问题

下载PDF 职称材料

双背包约束下下模函数最大值的贪婪算法

19

作者 李小平 赵杏利 +1 位作者 雷习军 何尚录 《苏州科技学院学报（自然科学版）》 CAS 2010年第3期24-28,39,共6页

给出求解双背包约束下非减下模集函数最大值的近似算法,证明了该算法的性能保证是1-e-1。该算法结合了部分穷举法与贪婪算法,是对贪婪算法的一种改进。算法的时间复杂性为O(n4)。

关键词 组合最优化 背包约束 下模集函数 贪婪算法 性能保证

下载PDF 职称材料

求解最大P-中心问题的一种近似算法

20

作者 黄辉 王忠思 梁国宏 《四川兵工学报》 CAS 2009年第6期85-88,共4页

求解最大P-中心问题属于计算下模集函数最大值问题,该类问题在组合优化问题中具有非常重要的应用.为此,给出了求解具有简单约束的最大P-中心问题的一种局部搜索算法,并讨论了所给算法的性能保证.

关键词 组合优化问题 下模集函数 近似算法 性能保证

下载PDF 职称材料