基于综合背包问题的混合贪婪算法的研究

发布时间：2018-06-20 09:54

本文选题：综合背包 + 贪婪算法　；参考：《吉林大学》2017年硕士论文

【摘要】：背包问题是一种组合优化的NP完全问题。问题可以描述为,给定了一个背包和一组物品,每个物品都有其自己的重量和价值,在背包限定的总重量内,通过选择部分物品,使得背包的总价值最高。背包问题经常会出现在商业、组合数学、密码学等领域中。0-1背包问题、依赖问题和多背包问题就是在背包问题的概念基础上扩展应用的NP完全问题,但随着待解决问题复杂性的提高,传统的0-1背包问题、依赖问题和多背包问题都已不能表述错综复杂的实际问题。本文提出一种在0-1背包问题、依赖问题和多背包问题的理论基础上附加其它约束条件的复杂的综合背包问题。综合背包问题可描述为,给定了一组物品,每个物品都有其自身的重量和度数,度数由入度和出度相加获得。物品相互之间存在某种联系,例如物品item0依赖item1和item2,则item0的出度数是2,假设item1也对item0存在依赖关系,在只考虑item1一个依赖关系的条件下,item0的入度数是1,由此也可以看出度数是单向计算的。除了给出一组物品外,综合背包问题并不像传统的背包问题那样只给出一个背包,而是存在未知个数的背包。每个背包的重量容纳值都是相同的,此外每个背包的入度和出度数都是被限制数量的。背包的入度和出度数依赖装进背包的所有物品的入度和出度数累加。综合背包问题的解可描述为,在满足不超过每个背包的总容量和不违反入度和出度数的限制的情况下,使用最少的背包个数,将所有的物品装入一组背包中。本文研究了依赖不同贪婪策略选择的混合贪婪算法计算出综合背包问题的最终解。混合贪婪算法通过使用不同的贪婪策略计算出输入值的贪婪因子序列,在满足局部最优解的情形下,以迭代的方式做出相继的贪心选择,得到问题的最终解。最后对根据不同贪婪策略的运用计算出的最终解进行分析,找出依赖贪婪策略的综合背包问题的最优解。
[Abstract]:Knapsack problem is a combinatorial optimization NP complete problem. The problem can be described as that given a knapsack and a group of items, each item has its own weight and value. Within the total weight of the knapsack, by selecting some items, the total value of the knapsack is the highest. Knapsack problem often appears in the fields of business, combinatorial mathematics, cryptography and so on. The dependency problem and multi-knapsack problem are NP-complete problems that extend the application of knapsack problem based on the concept of knapsack problem. However, with the improvement of the complexity of the unsolved problem, the traditional 0-1 knapsack problem, dependency problem and multi-knapsack problem can no longer express complicated practical problems. In this paper, we propose a complex synthetic knapsack problem with other constraints on the basis of the theory of 0-1 knapsack problem, dependency problem and multi-knapsack problem. The comprehensive knapsack problem can be described as: given a set of items, each item has its own weight and degree, and the degree is obtained by the sum of entry and output. There is some connection between items, for example, if the item item0 depends on item1 and item2, then the item0 has a degree of 2, assuming that item1 also has a dependency on item0. Under the condition that only one item1 dependency is considered, the input degree of item0 is 1, and it can be seen that the degree is calculated in one direction. Besides giving a set of items, the synthetic knapsack problem does not give only one knapsack as the traditional knapsack problem, but has an unknown number of knapsack. The weight of each knapsack is the same, in addition to each knapsack's entry and output are limited in number. The entry and output of the knapsack depends on the cumulative entry and output of all items loaded into the backpack. The solution of the synthetic knapsack problem can be described as that, under the condition that the total capacity of each knapsack and the limit of entry and output are not exceeded, all items are packed into a group of knapsack with the least number of knapsack. In this paper, a hybrid greedy algorithm based on the choice of different greedy strategies is studied to calculate the final solution of the synthetic knapsack problem. The hybrid greedy algorithm calculates the greedy factor sequence of the input value by using different greedy strategies. When the local optimal solution is satisfied, successive greedy selection is made iteratively and the final solution of the problem is obtained. Finally, the final solution calculated by different greedy strategies is analyzed to find the optimal solution of the comprehensive knapsack problem which depends on the greedy strategy.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】