| 无限制背包问题的爬山算法 |
| |
| 引用本文： | 宋翔,聂义勇,储诚斌.无限制背包问题的爬山算法[J].小型微型计算机系统,2004,25(7):1352-1355. |
| |
| 作者姓名： | 宋翔 聂义勇 储诚斌 |
| |
| 作者单位： | 1. 中国科学院,沈阳自动化研究所,辽宁,沈阳,110016;中国科学院,研究生院,北京,100039
2. 特鲁瓦科技大学,法国,特鲁瓦,10009 |
| |
| 摘 要： | 给出了一种求解整数背包问题的爬山解法 ,并对该算法的计算复杂度及最坏情形进行了理论分析 .通过与经典的求解背包问题方法的对比研究 ,给出了该算法的适用范围并展示其优越性 .数值实验表明 ,该算法简便易行 ,在其适用范围内具有计算复杂度低 ,近优程度高等优点 .
|
| 关 键 词： | 背包问题 无限制 爬山算法 |
| 文章编号： | 1000-1220(2004)07-1352-04 |
Hill Climbing Algorithm for Unconstraint Knapsack Problem |
| |
| SONG Xiang , NIE Yi yong , CHU Cheng bin.Hill Climbing Algorithm for Unconstraint Knapsack Problem[J].Mini-micro Systems,2004,25(7):1352-1355. |
| |
| Authors: | SONG Xiang NIE Yi yong CHU Cheng bin |
| |
| Affiliation: | SONG Xiang 1,2,3 NIE Yi yong 1,2 CHU Cheng bin 3 1 |
| |
| Abstract: | A new hill climbing algorithm for the unconstraint knapsack problem was presented. The complexity and the worst case condition of this new algorithm were analyzed. By the comparison with some classical algorithms, the application scope is given and the superiority is displayed about this algorithm. It has been shown in numerical experiments that the new algorithm is easy to implement and has the virtue of low computational complexity and high approximate optimization degree within its applicable scope. |
| |
| Keywords: | knapsack problem unconstrained hill climbing method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
