折扣{0-1}背包问题之分段排序贪心核算法研究

作     者：代祖华 刘园园 狄世龙 樊琦 DAI Zuhua;LIU Yuanyuan;DI Shilong;FAN Qi

作者机构：西北师范大学计算机科学与工程学院兰州730070 

基　　金：国家自然科学基金(61762080) 西北师范大学研究生培养与课程改革项目(2020KGLX01009) 

出 版 物：《计算机科学与探索》 (Journal of Frontiers of Computer Science and Technology)

年 卷 期：2023年第17卷第3期

页      码：595-607页

摘      要：折扣{0-1}背包问题(D{0-1}KP)的贪心核算法是一种近似解算法,常通过估算核区间划分子问题,采用分治算法设计求解算法,算法性能与核区间估计准确性密切相关,核区间估算优化是算法改进的主要途径。在研究{0-1}KP核概念基础上,提出D{0-1}KP核区间的修正定义,构建分段排序策略以缩减核区间规模,改进了D{0-1}KP贪心核算法,设计了修复贪心核动态规划加速算法(RGCADP)、分段排序贪心核动态规划加速算法(RGCADP_PS)。两个算法在D{0-1}KP标准数据集上的实验结果表明:与基本动态规划算法(BDP)相比,RGCADP、RGCADP_PS算法平均求解时间提升率为71.3%、77.2%;RGCADP、RGCADP_PS算法平均解误差率低于粒子群贪心修复算法(PSO-GRDKP)0.5个百分点,低于贪心核加速动态规划(GCADP)算法4.7个百分点;RGCADP_PS时间性能提升率高于RGCADP算法5.9%。

主 题 词：折扣{0-1}背包问题 核区间定义修正 贪心核算法 分段排序 贪心核动态规划加速算法 

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3778/j.issn.1673-9418.2106033

馆 藏 号：203118559...