Наближений алгоритм розв’язання задачі упаковки
Встановлено еквівалентність задачі упаковки та задачі знаход- ження незалежної множини вершин графу максимальної ваги. Для їх розв’язання розроблено наближений алгоритм. Ефективність його підтверджена експериментально при розв’язанні задач упаковки великої розмірності та порівнянні отриманих результ...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2013 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84735 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Наближений алгоритм розв’язання задачі упаковки / В.П. Шило, В.О. Рощин, І.П. Градинар // Компьютерная математика. — 2013. — № 1. — С. 110-116. — Бібліогр.: 8 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862706435141402624 |
|---|---|
| author | Шило, В.П. Рощин, В.О. Градинар, І.П. |
| author_facet | Шило, В.П. Рощин, В.О. Градинар, І.П. |
| citation_txt | Наближений алгоритм розв’язання задачі упаковки / В.П. Шило, В.О. Рощин, І.П. Градинар // Компьютерная математика. — 2013. — № 1. — С. 110-116. — Бібліогр.: 8 назв. — укр. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Встановлено еквівалентність задачі упаковки та задачі знаход- ження незалежної множини вершин графу максимальної ваги. Для їх розв’язання розроблено наближений алгоритм. Ефективність його підтверджена експериментально при розв’язанні задач упаковки великої розмірності та порівнянні отриманих результатів з відомими.
Установлена эквивалентность задачи упаковки и задачи нахождения независимого множества вершин графа максимального веса. Для их решения разработан приближенный алгоритм. Эффективность его подтверждена экспериментально при решении задач упаковки большой размерности и сравнении полученных результатов с известными.
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.
|
| first_indexed | 2025-12-07T16:59:25Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-84735 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Ukrainian |
| last_indexed | 2025-12-07T16:59:25Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шило, В.П. Рощин, В.О. Градинар, І.П. 2015-07-14T11:59:15Z 2015-07-14T11:59:15Z 2013 Наближений алгоритм розв’язання задачі упаковки / В.П. Шило, В.О. Рощин, І.П. Градинар // Компьютерная математика. — 2013. — № 1. — С. 110-116. — Бібліогр.: 8 назв. — укр. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84735 519.854.33 Встановлено еквівалентність задачі упаковки та задачі знаход- ження незалежної множини вершин графу максимальної ваги. Для їх розв’язання розроблено наближений алгоритм. Ефективність його підтверджена експериментально при розв’язанні задач упаковки великої розмірності та порівнянні отриманих результатів з відомими. Установлена эквивалентность задачи упаковки и задачи нахождения независимого множества вершин графа максимального веса. Для их решения разработан приближенный алгоритм. Эффективность его подтверждена экспериментально при решении задач упаковки большой размерности и сравнении полученных результатов с известными. 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. uk Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Наближений алгоритм розв’язання задачі упаковки Приближенный алгоритм решения задачи упаковки An approximate algorithm to solve packing problem Article published earlier |
| spellingShingle | Наближений алгоритм розв’язання задачі упаковки Шило, В.П. Рощин, В.О. Градинар, І.П. Оптимизация вычислений |
| title | Наближений алгоритм розв’язання задачі упаковки |
| title_alt | Приближенный алгоритм решения задачи упаковки An approximate algorithm to solve packing problem |
| title_full | Наближений алгоритм розв’язання задачі упаковки |
| title_fullStr | Наближений алгоритм розв’язання задачі упаковки |
| title_full_unstemmed | Наближений алгоритм розв’язання задачі упаковки |
| title_short | Наближений алгоритм розв’язання задачі упаковки |
| title_sort | наближений алгоритм розв’язання задачі упаковки |
| topic | Оптимизация вычислений |
| topic_facet | Оптимизация вычислений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84735 |
| work_keys_str_mv | AT šilovp nabliženiialgoritmrozvâzannâzadačíupakovki AT roŝinvo nabliženiialgoritmrozvâzannâzadačíupakovki AT gradinaríp nabliženiialgoritmrozvâzannâzadačíupakovki AT šilovp približennyialgoritmrešeniâzadačiupakovki AT roŝinvo približennyialgoritmrešeniâzadačiupakovki AT gradinaríp približennyialgoritmrešeniâzadačiupakovki AT šilovp anapproximatealgorithmtosolvepackingproblem AT roŝinvo anapproximatealgorithmtosolvepackingproblem AT gradinaríp anapproximatealgorithmtosolvepackingproblem |