Preview

Моделирование и анализ информационных систем

Расширенный поиск

О рекурсивно-параллельном алгоритме решения задачи о рюкзаке

https://doi.org/10.18255/1818-1015-2018-2-155-164

Аннотация

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

Об авторе

Владимир Васильевич Васильчиков
Ярославский государственный университет им. П.Г. Демидова
Россия
канд. техн. наук, зав. кафедрой вычислительных и программных систем


Список литературы

1. Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., 1982.

2. Kellerer H., Pferschy U., Pisinger D., Knapsack Problems, Springer, Berlin, 2004.

3. Martello S., Toth P., Knapsack Problems Algorithms and Computer Implementation, Wiley, New York, 1990.

4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К., Алгоритмы: построение и анализ, Вильямс, М., 2006.

5. Land A. H., Doig A. G., “An Autmatic Method of Solving Discrete Programming Problems”, Econometrica, 28 (1960), 497–520.

6. Pisinger D., “An expanding-core algorithm for the exact 0-l knapsack problem”, Eur. J. Oper. Res., 87:1 (1995), 175–187.

7. Pisinger D., “A fast algorithm for strongly correlated knapsack problems”, Discrete Applied Mathematics, 89:1–3 (1998), 197–212.

8. Dantzig G. B., “Discrete Variable Extremum Problems”, Operation Ressearch, 5 (1957), 266–277.

9. Посыпкин М.А., Сигал И.Х., “Комбинированный параллельный алгоритм решения задачи о ранце”, Труды четвертой международной конференции "Параллельные вычисления и задачи управления", 2008, 177–189.

10. Васильчиков В.В., Средства параллельного программирования для вычислительных систем с динамической балансировкой загрузки, Ярославль, 2001.

11. Васильчиков В.В., Коммуникационный модуль для организации полносвязного соединения компьютеров в локальной сети с использованием .NET Framework, Свидетельство о государственной регистрации программы для ЭВМ № 2013619925, 2013.

12. Васильчиков В.В., Библиотека поддержки рекурсивно-параллельного программирования для .NET Framework, Свидетельство о государственной регистрации программы для ЭВМ № 2013619926, 2013.

13. Васильчиков В.В., “О поддержке рекурсивно-параллельного программирования в .NET Framework”, Модел. и анализ информ. систем, 21:2 (2014), 15–25.

14. Васильчиков В.В., “Об оптимизации и распараллеливании алгоритма Литтла для решения задачи коммивояжера”, Модел. и анализ информ. систем, 23:4 (2016), 401– 411.


Рецензия

Для цитирования:


Васильчиков В.В. О рекурсивно-параллельном алгоритме решения задачи о рюкзаке. Моделирование и анализ информационных систем. 2018;25(2):155-164. https://doi.org/10.18255/1818-1015-2018-2-155-164

For citation:


Vasilchikov V.V. On а Recursive-Parallel Algorithm for Solving the Knapsack Problem. Modeling and Analysis of Information Systems. 2018;25(2):155-164. (In Russ.) https://doi.org/10.18255/1818-1015-2018-2-155-164

Просмотров: 1018


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)