A Distributed Algorithm for 0-1 Knapsack Problem Based on Mobile Agent

摘要

The knapsack problem is a typical one of NPC problems, which is easy to be described but difficult to be solved. It is very important in theory and practice to study it. Nowadays there is a variety of research in algorithm for solving it. As the parallel processing technologies develop, the research of effective parallel algorithms for this problem attracts much attention. To run those algorithms needs high level hardware and high performance parallel computers. Using mobile agent technologies, a more effective model to solve the complex distributed problems can be established. Combines mobile agent with the traditional parallel algorithm, the process in a parallel computer can be evolved into the one performed by some ordinary computers. This can avoid the limitation of experiment conditions and provides convenience in practice. In this paper, a distributed algorithm is proposed for the 0-1 knapsack problem based on the mobile agent, and it is feasible and effective in theoretical analysis.