Development of the Software for Solving the Knapsack Problem by Solving the Traveling Salesman Problem

摘要

The work addressees the topical problem of reducing some NP-complete problems to others. The authors focus on the development of an algorithm for reducing the knapsack problem to the traveling salesman problem to find its solution and transfer the results of solving one NP-complete problem to another.Authors investigate the developed reduction algorithm for accuracy of obtaining the result of the original NP-complete problem and computational complexity. The paper shows a mathematical model of the reduction algorithm, provides a mathematical proof of its accuracy, as well as a proof of the polynomial computational complexity of the developed reduction algorithm.For a programmatic demonstration of the correctness of the work, authors implemented the developed reduction algorithm in Java programming language, as well as the exact algorithms for solving the knapsack problem, and the traveling salesman problem. Using this program, we carried out the experiments to find solutions to the original NP-complete problem with different amounts of input data, and we confirmed the correctness of the reduction algorithm.The paper describes further prospects for the study of this direction.