Метод таблиц допустимых решений в задаче о ранце
Автор: Бурков Владимир Николаевич, Корепанов Всеволод Олегович, Кашенков Александр Рудольфович
Рубрика: Информатика и вычислительная техника
Статья в выпуске: 2 т.18, 2018 года.
Бесплатный доступ
Предложен новый подход к получению верхних и нижних оценок для задачи о ранце, в основе которого лежат операции «склеивания» решений одного слоя (k-слоем называется множество решений, у которых определены первые k компонент, соответствующих предметам). Рассмотрены две операции склеивания. При первой операции склеивания не теряется ни одно из допустимых решений, но могут появиться недопустимые. При этом мы получаем верхнюю оценку решений задачи. Во второй операции остаются только допустимые решения, но не все. При этом мы получаем нижнюю оценку решений задачи. В статье представлены результаты численных экспериментов по оценке времени и точности предлагаемого подхода в зависимости от объёма входных данных, объёма рюкзака и величины склеивания.
Задача о ранце, верхняя и нижняя оценки решений, вычислительный эксперимент
Короткий адрес: https://sciup.org/147155263
IDR: 147155263 | УДК: 519.854.2, | DOI: 10.14529/ctcr180204
The method of tables of feasible solutions for the knapsack problem
The paper proposes a new approach to obtaining upper and lower bounds for the knapsack problem, which is based on the operations of ”gluing” together solutions of one layer (the k-layer is the set of solutions for which the first k components corresponding to items are defined). Two operations of gluing are considered. The first gluing operation does not lose any of the acceptable solutions, but it may appear inadmissible. Wherein, we obtain an upper bound for the solutions of the problem. In the second operation, only feasible solutions remain, but not all. In this case we obtain a lower bound for the solutions of the problem. The article presents the results of numerical experiments to estimate the time and accuracy of the proposed approach, depending on the input data size, the volume of the knapsack size and the volume of the gluing.
Список литературы Метод таблиц допустимых решений в задаче о ранце
- Diakaki, C. Towards a multi-objective optimization approach for improving energy efficiency in buildings/C. Diakaki, E. Grigoroudis, D. Kolokotsa//Energy and Buildings. -2008. -Vol. 40, no. 9. -P. 1747-1754 DOI: 10.1016/j.enbuild.2008.03.002
- Dynamic placement for clustered web applications/A. Karve, T. Kimbrel, G. Pacifici et al.//Proceedings of the 15th international conference on World Wide Web, WWW '06. -2006. -P. 595-604 DOI: 10.1145/1135777.1135865
- Gatzianas, M. Control of wireless networks with rechargeable batteries/M. Gatzianas, L. Georgiadis, L. Tassiulas//IEEE Transactions on Wireless Communications. -2010. -Vol. 9, no. 2. -P. 581-593 DOI: 10.1109/TWC.2010.080903
- Новый эффективный алгоритм решения задачи об инвестициях/Е.Р. Гафаров, А. Долгий, А.А. Лазарев, Ф. Вернер//Автоматика и телемеханика. -2016. -№ 9. -С. 150-166.
- Загурских, Е.А. Разработка и реализация криптографической системы с открытым ключом, основанной на обобщении задачи о ранце для кольца многочленов с коэффициентами из поля: выпускная квалификационная работа магистра/Е.А.Загурских. -Новосибирск: Новосибирский государственный университет, 2017. -24 с.
- Martello, S. New trends in exact algorithms for the 0-1 knapsack problem/S. Martello, D. Pisinger, P. Toth//European Journal of Operational Research. -2000. -Vol. 123, no. 2. -P. 325-332 DOI: 10.1016/s0377-2217(99)00260-x
- Kellerer, H. Knapsack Problems/H. Kellerer, U. Pferschy, D. Pisinger. -Springer-Verlag Berlin Heidelberg, 2004. ISBN 3-540-40286-1. MR 2161720. DOI: 10.1007/978-3-540-24777-7
- Метод допустимых решений в многомерной задаче о ранце/В.Н.Бурков, И.В. Буркова, Б.К. Уандыков, Д.С. Чу//Экономика и менеджмент систем управления. -2015. -Т.18, № 4.1. -С. 136-144.
