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

1

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

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

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

下载PDF 职称材料

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

2

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

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

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

下载PDF 职称材料

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

3

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

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

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

下载PDF 职称材料

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

4

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

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

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

下载PDF 职称材料

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

5

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

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

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

下载PDF 职称材料

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

6

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

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

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

下载PDF 职称材料

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

7

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

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

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

下载PDF 职称材料

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

8

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

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

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

下载PDF 职称材料

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

9

作者 李小平 赵杏利 +1 位作者 雷习军 何尚录 《温州大学学报（自然科学版）》 2010年第1期6-10,共5页

将部分穷举法与贪婪算法相结合,给出求解多背包约束下非减下模集函数最大值的近似算法.证明了该算法的性能保证是1–e–1,算法的时间复杂性为O(3n4).

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

下载PDF 职称材料

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

10

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

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

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

下载PDF 职称材料

多背包约束下下模集函数最大值问题的近似算法

11

作者 赵杏利 雷习军 +1 位作者 李小平 何尚录 《周口师范学院学报》 CAS 2010年第5期45-47,共3页

给出了在实数范围内求解多背包约束条件下下模集函数最大值问题的一种改进的近似算法,是MaximSviridenko所给出的整数范围内求解单背包约束下下模集函数最大值的扩展.该算法的时间复杂性为:O(kn4),其性能保证为1-e-1/D.

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

下载PDF 职称材料