Наближений алгоритм розв’язання задачі упаковки

• Published in: Компьютерная математика
• Date: 2013
• Main Authors: Шило, В.П., Рощин, В.О., Градинар, І.П.
• Format: Article
• Language: Ukrainian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2013
• Subjects: Оптимизация вычислений
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/84735
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Наближений алгоритм розв’язання задачі упаковки / В.П. Шило, В.О. Рощин, І.П. Градинар // Компьютерная математика. — 2013. — № 1. — С. 110-116. — Бібліогр.: 8 назв. — укр.

Встановлено еквівалентність задачі упаковки та задачі знаход- ження незалежної множини вершин графу максимальної ваги. Для їх розв’язання розроблено наближений алгоритм. Ефективність його підтверджена експериментально при розв’язанні задач упаковки великої розмірності та порівнянні отриманих результатів з відомими. Установлена эквивалентность задачи упаковки и задачи нахождения независимого множества вершин графа максимального веса. Для их решения разработан приближенный алгоритм. Эффективность его подтверждена экспериментально при решении задач упаковки большой размерности и сравнении полученных результатов с известными. In the paper, the equivalence of packing problem and the problem of finding an independent set of graph nodes of maximum weight is established. The approximation algorithm is proposed for this problem. Its efficiency is confirmed experimentally by solving packing problems of high dimensionality and comparing the results obtained with known ones.