Решение задачи о покрытии минимальной мощности
Работа посвящена решению имеющей многочисленные приложения NP-трудной задачи о покрытии минимальной мощности (MCSCP) - наиболее сложному подклассу задач о покрытии. Рассмотрены лучшие известные алгоритмы решения этой задачи. Предложен и исследован новый случайный алгоритм повторного локального поиск...
Збережено в:
| Дата: | 2013 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Назва видання: | Компьютерная математика |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.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| id |
irk-123456789-84759 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-847592015-07-15T03:02:12Z Решение задачи о покрытии минимальной мощности Шило, В.П. Теория и методы оптимизации Работа посвящена решению имеющей многочисленные приложения 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. 2013 Article Решение задачи о покрытии минимальной мощности / В.П. Шило // Компьютерная математика. — 2013. — № 2. — С. 152-161. — Бібліогр.: 8 назв. — рос. ХХХХ-0003 http://dspace.nbuv.gov.ua/handle/123456789/84759 519.854.33 ru Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Теория и методы оптимизации Теория и методы оптимизации |
| spellingShingle |
Теория и методы оптимизации Теория и методы оптимизации Шило, В.П. Решение задачи о покрытии минимальной мощности Компьютерная математика |
| description |
Работа посвящена решению имеющей многочисленные приложения NP-трудной задачи о покрытии минимальной мощности (MCSCP) - наиболее сложному подклассу задач о покрытии. Рассмотрены лучшие известные алгоритмы решения этой задачи. Предложен и исследован новый случайный алгоритм повторного локального поиска, использующий адаптивную настройку повторности и модифицированную целевую функцию. Приведены результаты обширных экспериментальных расчетов, которые показали преимущества предложенного алгоритма над известными лучшими алгоритмами. С помощью разработанного алгоритма найдено девятнадцать новых рекордных решений. |
| format |
Article |
| author |
Шило, В.П. |
| author_facet |
Шило, В.П. |
| author_sort |
Шило, В.П. |
| title |
Решение задачи о покрытии минимальной мощности |
| title_short |
Решение задачи о покрытии минимальной мощности |
| title_full |
Решение задачи о покрытии минимальной мощности |
| title_fullStr |
Решение задачи о покрытии минимальной мощности |
| title_full_unstemmed |
Решение задачи о покрытии минимальной мощности |
| title_sort |
решение задачи о покрытии минимальной мощности |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2013 |
| topic_facet |
Теория и методы оптимизации |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84759 |
| citation_txt |
Решение задачи о покрытии минимальной мощности / В.П. Шило // Компьютерная математика. — 2013. — № 2. — С. 152-161. — Бібліогр.: 8 назв. — рос. |
| series |
Компьютерная математика |
| work_keys_str_mv |
AT šilovp rešeniezadačiopokrytiiminimalʹnojmoŝnosti |
| first_indexed |
2023-10-18T19:29:38Z |
| last_indexed |
2023-10-18T19:29:38Z |
| _version_ |
1796147111721435136 |