Решение задачи о покрытии минимальной мощности
Работа посвящена решению имеющей многочисленные приложения NP-трудной задачи о покрытии минимальной мощности (MCSCP) - наиболее сложному подклассу задач о покрытии. Рассмотрены лучшие известные алгоритмы решения этой задачи. Предложен и исследован новый случайный алгоритм повторного локального поиск...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84759 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Решение задачи о покрытии минимальной мощности / В.П. Шило // Компьютерная математика. — 2013. — № 2. — С. 152-161. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862739387093090304 |
|---|---|
| author | Шило, В.П. |
| author_facet | Шило, В.П. |
| citation_txt | Решение задачи о покрытии минимальной мощности / В.П. Шило // Компьютерная математика. — 2013. — № 2. — С. 152-161. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Работа посвящена решению имеющей многочисленные приложения NP-трудной задачи о покрытии минимальной мощности (MCSCP) - наиболее сложному подклассу задач о покрытии. Рассмотрены лучшие известные алгоритмы решения этой задачи. Предложен и исследован новый случайный алгоритм повторного локального поиска, использующий адаптивную настройку повторности и модифицированную целевую функцию. Приведены результаты обширных экспериментальных расчетов, которые показали преимущества предложенного алгоритма над известными лучшими алгоритмами. С помощью разработанного алгоритма найдено девятнадцать новых рекордных решений.
Робота присвячена розв'язанню NP-важкої задачі про покриття мінімальної потужності (MCSCP), що має численні застосування, – найбільш складному підкласу задач про покриття. Розглянуто кращі відомі алгоритми розв'язання цієї задачі. Запропоновано та досліджено новий випадковий алгоритм повторного локального пошуку, що використовує адаптивне настроювання повторності та модифіковану цільову функцію. Наведено результати експериментальних розрахунків, які показали переваги запропонованого алгоритму над відомими кращими алгоритмами. За допомогою розробленого алгоритму знайдено дев'ятнадцять нових рекордних розв'язків.
In this paper the Minimum Cardinality Set Covering Problem (MCSCP) is considered. The MCSCP is a NP-hard problem with a wide range of practical applications. MCSCP is the most complex subclass of the Set Covering Problem. We propose and investigate a new random algorithm with an adaptive iterative tuning based on the iterated local search. Our approach introduces a modifying objective function, which significantly improves the characteristics of the algorithm. The results of extensive computational experiments reveal a superior performance when compared with the stateof-the-art algorithms. The proposed approach improves the best existing solutions for 19 benchmark instances widely used in the literature.
|
| first_indexed | 2025-12-07T20:08:38Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-84759 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T20:08:38Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шило, В.П. 2015-07-14T16:06:11Z 2015-07-14T16:06:11Z 2013 Решение задачи о покрытии минимальной мощности / В.П. Шило // Компьютерная математика. — 2013. — № 2. — С. 152-161. — Бібліогр.: 8 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84759 519.854.33 Работа посвящена решению имеющей многочисленные приложения NP-трудной задачи о покрытии минимальной мощности (MCSCP) - наиболее сложному подклассу задач о покрытии. Рассмотрены лучшие известные алгоритмы решения этой задачи. Предложен и исследован новый случайный алгоритм повторного локального поиска, использующий адаптивную настройку повторности и модифицированную целевую функцию. Приведены результаты обширных экспериментальных расчетов, которые показали преимущества предложенного алгоритма над известными лучшими алгоритмами. С помощью разработанного алгоритма найдено девятнадцать новых рекордных решений. Робота присвячена розв'язанню NP-важкої задачі про покриття мінімальної потужності (MCSCP), що має численні застосування, – найбільш складному підкласу задач про покриття. Розглянуто кращі відомі алгоритми розв'язання цієї задачі. Запропоновано та досліджено новий випадковий алгоритм повторного локального пошуку, що використовує адаптивне настроювання повторності та модифіковану цільову функцію. Наведено результати експериментальних розрахунків, які показали переваги запропонованого алгоритму над відомими кращими алгоритмами. За допомогою розробленого алгоритму знайдено дев'ятнадцять нових рекордних розв'язків. In this paper the Minimum Cardinality Set Covering Problem (MCSCP) is considered. The MCSCP is a NP-hard problem with a wide range of practical applications. MCSCP is the most complex subclass of the Set Covering Problem. We propose and investigate a new random algorithm with an adaptive iterative tuning based on the iterated local search. Our approach introduces a modifying objective function, which significantly improves the characteristics of the algorithm. The results of extensive computational experiments reveal a superior performance when compared with the stateof-the-art algorithms. The proposed approach improves the best existing solutions for 19 benchmark instances widely used in the literature. Работа выполнена при частичной финансовой поддержке Украинского научно-технологического центра (грант № 5710). ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Решение задачи о покрытии минимальной мощности Розв'язання задачі про покриття мінімальної потужності Random iterated local search algorithm for minimum cardinality set covering problem using modified objective function Article published earlier |
| spellingShingle | Решение задачи о покрытии минимальной мощности Шило, В.П. Теория и методы оптимизации |
| title | Решение задачи о покрытии минимальной мощности |
| title_alt | Розв'язання задачі про покриття мінімальної потужності Random iterated local search algorithm for minimum cardinality set covering problem using modified objective function |
| title_full | Решение задачи о покрытии минимальной мощности |
| title_fullStr | Решение задачи о покрытии минимальной мощности |
| title_full_unstemmed | Решение задачи о покрытии минимальной мощности |
| title_short | Решение задачи о покрытии минимальной мощности |
| title_sort | решение задачи о покрытии минимальной мощности |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84759 |
| work_keys_str_mv | AT šilovp rešeniezadačiopokrytiiminimalʹnoimoŝnosti AT šilovp rozvâzannâzadačípropokrittâmínímalʹnoípotužností AT šilovp randomiteratedlocalsearchalgorithmforminimumcardinalitysetcoveringproblemusingmodifiedobjectivefunction |