bsuirДоклады БГУИРDoklady BGUIR1729-76482708-0382БГУИР10.35596/1729-7648-2019-124-6-72-79bsuir-1197Research ArticleЭЛЕКТРОНИКА, РАДИОФИЗИКА, РАДИОТЕХНИКА, ИНФОРМАТИКАELECTRONICS, RADIOPHYSICS, RADIOENGINEERING, INFORMATICSОПРЕДЕЛЕНИЕ СТРУКТУРЫ ОПТИМАЛЬНОГО ПОДМНОЖЕСТВА В ЗАДАЧЕ О РАНЦЕFINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEMЧебаковС. В.ChebakovS. V.

Кандидат физико-математических наук, старший научный сотрудник

 

PhD, senior researcher

СеребрянаяЛ. В.SerebryanayaL. V.

Серебряная Лия Валентиновна, кандидат физико-математических наук, доцент кафедры программного обеспечения информационных технологий

220013, г. Минск, ул. П. Бровки, 6

Serebryanaya Liya Valentinovna, PhD, associate professor of the information technology software department

220013, Minsk, P. Brovka str., 6

l_silver@mail.ruОбъединенный институт проблем информатики НАН БеларусиUnited Institute of Informatics Problems of NAS of BelarusБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and Radioelectronics201903102019067279Copyright © Чебаков С.В., Серебряная Л.В., 20192019Чебаков С.В., Серебряная Л.В.Chebakov S.V., Serebryanaya L.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.bsuir.by/jour/article/view/1197

Рассматривается алгоритм решения задачи о ранце на основе предлагаемой многокритериальной модели. Реализация алгоритма позволяет определить структуру оптимального подмножества в виде объединения определенных элементов группы паретовских слоев, на которые разбивается множество начальных данных. Первым таким слоем является множество Парето. Определение структуры оптимального подмножества позволяет найти такое подмножество начальных данных, элементы которого не могут войти в оптимальное подмножество. Наиболее трудоемкими являются задачи о ранце с большим набором начальных данных. В статье показано, что при небольшом значении объема ранца число элементов, требуемых для нахождения оптимального подмножества, значительно меньше их общего числа в исходном множестве, что может привести к существенному уменьшению общего времени решения комбинаторной задачи.  

An algorithm for solving the knapsack problem based on the proposed multi-criteria model is considered. The implementation of this algorithm allows to define the structure of the optimal subset as a union of certain elements of a Pareto layers group into which a initial data set is divided. The first such layer is the Pareto set. The optimal subset allows to find a specific subset of the initial data. Its elements as a result of belonging to the Pareto layers with large numbers cannot enter the optimal subset. The most expensive in terms of the number of operations required are knapsack problems, in which the number of elements in the set of initial data is quite large. The article shows that with a relatively small value of the knapsack volume, the number of elements required to find the optimal subset is significantly less than their total number in the original set. It can lead to a significant decrease in the total time to solve the combinatorial problem.  

задача о ранцемногокритериальная модельмножество Паретооптимальное подмножествопаретовские слоиthe knapsack problemtwo-critarial optimizationPareto subsetoptimal subsetpareto layersReferencesАльсведе Р., Вегенер И. Задачи поиска. М.: Мир, 1982. 367 c.Al'svede R., Vegener I. Zadachi poiska. M.: Mir, 1982. 367 s. (in Russ.)Посыпкин М.А. Комбинированный параллельный алгоритм решения задачи о ранце // Труды IV Междунар. конф. «Параллельные вычисления и задачи управления». Москва, 27–29 октября 2008 г. С. 177–189.Posypkin M.A. Kombinirovannyj parallel'nyj algoritm reshenija zadachi o rance // Trudy IV Mezhdunar. konf. «Parallel'nye vychislenija i zadachi upravlenija». Moskva, 27–29 oktjabrja 2008 g. S. 177–189. (in Russ.)Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementations. N.Y.: John Wiley&Sons, 1990. 308 p.Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementations. N.Y.: John Wiley&Sons, 1990. 308 p.Чебаков С.В. Двухкритериальная модель построения оптимального подмножества альтернатив с максимальной суммарной вероятностью достижения цели // Вести НАН Беларуси. Сер. физ.-мат. наук. 2005. № 2. С. 112–118.Chebakov S.V. Dvuhkriterial'naja model' postroenija optimal'nogo podmnozhestva al'ternativ s maksimal'noj summarnoj verojatnost'ju dostizhenija celi // Vesti NAN Belarusi. Ser. fiz.-mat. nauk. 2005. № 2. S. 112–118. (in Russ.)Kung H.F., Preparata F.P. On finding the maxima of a set of vectors // Journal of the Association for Computing Machinery. 1975. Vol. 22. P. 469–476.Kung H.F., Preparata F.P. On finding the maxima of a set of vectors // Journal of the Association for Computing Machinery. 1975. Vol. 22. P. 469–476.

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