maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2018-2-155-164mais-676Research ArticleОригинальные статьиArticlesО рекурсивно-параллельном алгоритме решения задачи о рюкзакеOn а Recursive-Parallel Algorithm for Solving the Knapsack Problemhttps://orcid.org/0000-0001-7882-8906ВасильчиковВладимир ВасильевичVasilchikovVladimir V.

канд. техн. наук, зав. кафедрой вычислительных и программных систем

PhD

vvv193@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201820042018252155164Copyright © Васильчиков В.В., 20182018Васильчиков В.В.Vasilchikov V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/676

Предлагается эффективный параллельный алгоритм решения NP-полной задачи о рюкзаке в ее исходном, так называемом 0-1 варианте. Для нахождения ее точного решения издавна применяются алгоритмы, относящиеся к категории "методов ветвей и границ". Для ускорения получения результата с разной степенью эффективности применяются также различные варианты организации параллельных вычислений. Мы предлагаем здесь алгоритм решения задачи, основанный на парадигме рекурсивно-параллельных вычислений. Он представляется нам хорошо пригодным для задач такого рода, когда трудно сразу разбить вычисления на достаточное количество сравнимых по трудоемкости подзадач, поскольку она проявляется динамически во время вычислений. В качестве основного инструмента для программной реализации алгоритма использовалась разработанная автором библиотека RPM_ParLib, позволяющая создавать эффективные приложения для вычислений на локальной сети в среде .NET Framework. Такие приложения обладают способностью порождать параллельные ветви вычислений непосредственно во время выполнения программы и динамически перераспределять работу между вычислительными модулями. При этом в качестве языка программирования может использоваться любой язык с поддержкой .NET Framework. Для проведения экспериментов было написано несколько программ на языке C# с использованием упомянутой библиотеки. Основной целью этих экспериментов было исследование ускорения, достигаемого за счет рекурсивно-параллельной организации вычислений. Подробное описание алгоритма и эксперимента, а также полученные результаты приводятся в работе.          

In this paper, we offer an efficient parallel algorithm for solving the NP-complete Knapsack Problem in its basic, so-called 0-1 variant. To find its exact solution, algorithms belonging to the category ”branch and bound methods” have long been used. To speed up the solving with varying degrees of efficiency, various options for parallelizing computations are also used. We propose here an algorithm for solving the problem, based on the paradigm of recursive-parallel computations. We consider it suited well for problems of this kind, when it is difficult to immediately break up the computations into a sufficient number of subtasks that are comparable in complexity, since they appear dynamically at run time. We used the RPM ParLib library, developed by the author, as the main tool to program the algorithm. This library allows us to develop effective applications for parallel computing on a local network in the .NET Framework. Such applications have the ability to generate parallel branches of computation directly during program execution and dynamically redistribute work between computing modules. Any language with support for the .NET Framework can be used as a programming language in conjunction with this library. For our experiments, we developed some C# applications using this library. The main purpose of these experiments was to study the acceleration achieved by recursive-parallel computing. A detailed description of the algorithm and its testing, as well as the results obtained, are also given in the paper.

задача о рюкзакепараллельный алгоритмрекурсия.NETKnapsack Problemparallel algorithmrecursion.NETReferencesГэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., 1982.Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co, San Francisco, 1979.Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer, Berlin, 2004.Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer, Berlin, 2004.Martello S., Toth P., Knapsack Problems Algorithms and Computer Implementation, Wiley, New York, 1990.Martello S., Toth P., Knapsack Problems Algorithms and Computer Implementation, Wiley, New York, 1990.Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., Алгоритмы: построение и анализ, Вильямс, М., 2006.Cormen T., Leiserson Ch., Rivest R., Stein C., Introduction to Algorithms, The MIT Press, 2001.Land A. H., Doig A. G., “An Autmatic Method of Solving Discrete Programming Problems”, Econometrica, 28 (1960), 497–520.Land A. H., Doig A. G., “An Autmatic Method of Solving Discrete Programming Problems”, Econometrica, 28 (1960), 497–520.Pisinger D., “An expanding-core algorithm for the exact 0-l knapsack problem”, Eur. J. Oper. Res., 87:1 (1995), 175–187.Pisinger D., “An expanding-core algorithm for the exact 0-l knapsack problem”, Eur. J. Oper. Res., 87:1 (1995), 175–187.Pisinger D., “A fast algorithm for strongly correlated knapsack problems”, Discrete Applied Mathematics, 89:1–3 (1998), 197–212.Pisinger D., “A fast algorithm for strongly correlated knapsack problems”, Discrete Applied Mathematics, 89:1–3 (1998), 197–212.Dantzig G. B., “Discrete Variable Extremum Problems”, Operation Ressearch, 5 (1957), 266–277.Dantzig G. B., “Discrete Variable Extremum Problems”, Operation Ressearch, 5 (1957), 266–277.Посыпкин М.А., Сигал И.Х., “Комбинированный параллельный алгоритм решения задачи о ранце”, Труды четвертой международной конференции "Параллельные вычисления и задачи управления", 2008, 177–189.Posypkin M.A., Sigal I.Kh., “Kombinirovannyj parallelnyj algoritm reshenija zadachi o rance”, Proceedings of the Fourth International Conference "Parallel Computations and Control Problems", 2008, 177–189,(in Russian).Васильчиков В.В., Средства параллельного программирования для вычислительных систем с динамической балансировкой загрузки, Ярославль, 2001.Vasilchikov V.V., Sredstva parallelnogo programmirovaniya dlya vychislitelnykh sistem s dinamicheskoy balansirovkoy zagruzki, Yaroslavl, 2001, (in Russian)Васильчиков В.В., Коммуникационный модуль для организации полносвязного соединения компьютеров в локальной сети с использованием .NET Framework, Свидетельство о государственной регистрации программы для ЭВМ № 2013619925, 2013.Vasilchikov V.V., Kommunikatsionnyy modul dlya organizatsii polnosvyaznogo soedineniya kompyuterov v lokalnoy seti s ispolzovaniem .NET Framework, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619925, 2013, (in Russian).Васильчиков В.В., Библиотека поддержки рекурсивно-параллельного программирования для .NET Framework, Свидетельство о государственной регистрации программы для ЭВМ № 2013619926, 2013.Vasilchikov V.V., Biblioteka podderzhki rekursivnoparallelnogo programmirovaniya dlya .NET Framework, Svidetelstvo o gosudarstvennoy registratsii programmy dlya EVM № 2013619926, 2013, (in Russian).Васильчиков В.В., “О поддержке рекурсивно-параллельного программирования в .NET Framework”, Модел. и анализ информ. систем, 21:2 (2014), 15–25.Vasilchikov V.V., “On the Recursive-Parallel Programming for the .NET Framework”, Modeling and Analysis of Information Systems, 21:2 (2014), 15–25, (in Russian).Васильчиков В.В., “Об оптимизации и распараллеливании алгоритма Литтла для решения задачи коммивояжера”, Модел. и анализ информ. систем, 23:4 (2016), 401– 411.Vasilchikov V.V., “On Optimization and Parallelization of the Little Algorithm for Solving the Travelling Salesman Problem”, Modeling and Analysis of Information Systems, 23:4 (2016), 401–411, (in Russian).

The authors declare that there are no conflicts of interest present.