Dissertation > Excellent graduate degree dissertation topics show

The Comparison and Improvement of Algorithms for Solving the 0-1 Knapsack Problem

Author: ZhuYueAn
Tutor: MengXiaoHua
School: Jinan University
Course: Computer Software and Theory
Keywords: 0-1 knapsack problem Dynamic programming algorithm Hybrid Algorithm Parallel algorithms
CLC: TP301.6
Type: Master's thesis
Year: 2011
Downloads: 299
Quote: 0
Read: Download Dissertation

Abstract


From the computational complexity point of view, the knapsack problem is an NP-hard problem. For half a century, the problem has been one of the hot spots of the algorithm complexity. Knapsack problem in information encryption, budget control, project selection, material cutting, loading of goods, the important value applications such as network and information security. Therefore, the method for solving the knapsack problem, both in theory and in practice has a certain significance. The major work done in the paper are as follows: (1) using classical algorithm for the 0-1 knapsack problem, and design a hybrid algorithm based on two table thinking. (2) space complexity the hybrid algorithm RKP improved algorithm for solving 0-1 knapsack problem. The RKP algorithm combined with dynamic programming algorithm and the divide-and-conquer strategy, only O (C) space complexity in case time complexity of O (nC) 0-1 knapsack problem. And in the premise without backtracking step obtained items into the backpack. (3) dynamic programming to solve the 0-1 knapsack problem serial algorithm is extended to a parallel algorithm. The analysis showed that: vertically partitioned table area parallel dynamic programming algorithm affected by the weight of the article to cause the processor to access data difficult, heavy burden on system bandwidth and code complexity; contrast, horizontal partitioning table area parallel dynamic programming algorithm has more The big advantage. For each processor, each treatment the columns of the data block size is b '= (?) (Where C is the capacity backpack, p is the number of processors, n is the number of optional items, γ, β, χ constant), the parallel algorithm with optimal performance. Subsequently, with the dominant technology dynamic programming the serial algorithm extended parallel algorithm. In the case of load balancing, the time complexity of the algorithm is O (min (?)). (4) Finally, the experiments show different characteristics of various algorithms for solving different classes of 0-1 knapsack problem, the conclusions are as follows: general dynamic programming algorithm proposed in this paper RKP algorithm is insensitive knapsack problem category, and also in solving strong correlation, not very different from the time-consuming when weakly correlated and uncorrelated knapsack problem; poor performance hybrid algorithm based on two table thinking in solving strong 0-1 knapsack problem; surprising in Dantzig performance is bounding function value bound as branch-and-bound algorithm for solving strongly correlated knapsack problem performance performance than backtracking; the recursion method only adapt to the problem of the small-scale, and they are strengthened in solving 0-1 knapsack problem poor.

Related Dissertations

  1. Designs and Applications of Fuzzy Synthetic Evaluation Models Based on Parallel Algorithms,TP18
  2. Public Transport Optimal Dispatching Based on the Genetic-Newton Algorithm,TP18
  3. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  4. The Research on A Scheduling Algorithm for Real-time Tasks in Multi-core Systems,TP332
  5. Design and Realization of Parallel Signal Processing System with ADSP TS201S,TN957.51
  6. The Improvements and Applications of the Glowworm Swarm Algortihm,TP301.6
  7. Multi-objective artificial fireflies swarm optimization algorithm and its application,TP301.6
  8. The Improvement of Genetic Algorithm and It’s Application on Knapsack Problem and Function Optimization,TP18
  9. Research on the Combinational Optimization in Shuffled Frog Leaping Algorithm,TP301.6
  10. Research on Modified Particle Swarm Optimization and Its Application,TP301.6
  11. The Research of Artificial Fish Swarm Algorithm and Its Application,TP301.6
  12. The Research of a Multi-objective Evolutionary Algorithm Based on Steady-state,O221.6
  13. Research on Lock Capacity on the Minjiang River Downstream,U641.7
  14. Research on Parallel Algorithms of Image Matching,TP301.6
  15. Using Layer Patterns in Solving the Two-dimensional Cutting Stock Problem,TP301.6
  16. The Numerical Algorithm for the Linear Congruential Equations with Single Modulus / Multi-modulus and Its Application in Cryptography,TN918.1
  17. MPI-based parallel genetic algorithm for 0-1 knapsack problem Applied Research,TP18
  18. Approximation to Fuzzy Minimum-Risk Problems and Its Applications,O224
  19. A Migration Parallel Genetic Algorithm for Solving SVM Inverse Problem,TP18
  20. Application Research of Particle Swarm Optimization in Conbinatiorial Optimization Problems,TP301.6
  21. Genetic Algorithms Research and Application mode - based alternative,TP18

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile