Применение "бесполезных" ходов при решении задачи о покрытии
Предложена модификация алгоритма случайного повторного локального поиска для решения задачи о покрытии с применением «бесполезных» ходов, что позволяет расширить поисковые возможности алгоритма. Эффективность разработанного алгоритма подтверждена экспериментально при решении задач большой размерност...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2014 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84820 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Применение "бесполезных" ходов при решении задачи о покрытии / П.В. Шило // Компьютерная математика. — 2014. — № 1. — С. 150-158. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862590132325974016 |
|---|---|
| author | Шило, П.В. |
| author_facet | Шило, П.В. |
| citation_txt | Применение "бесполезных" ходов при решении задачи о покрытии / П.В. Шило // Компьютерная математика. — 2014. — № 1. — С. 150-158. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Предложена модификация алгоритма случайного повторного локального поиска для решения задачи о покрытии с применением «бесполезных» ходов, что позволяет расширить поисковые возможности алгоритма. Эффективность разработанного алгоритма подтверждена экспериментально при решении задач большой размерности, а также сравнением полученных результатов с известными. С помощью предложенного алгоритма найдено новое рекордное решение.
Запропонована модифікація алгоритму випадкового повторного локального пошуку для розв'язання задачі про покриття із застосуванням «даремних» ходів, що дозволяє розширити пошукові можливості алгоритму. Ефективність розробленого алгоритму підтверджена експериментально при розв'язанні задач великої розмірності, а також порівнянням отриманих результатів із відомими. За допомогою запропонованого алгоритму знайдено новий рекордний розв'язок.
In this paper, the modification of a new algorithm based on the iterated random local search for Minimum Cardinality Set Covering Problem (MCSCP) with “useless” moves is proposed that makes it possible to increase its search capabilities. The efficiency of the algorithm is confirmed experimentally by solving problems of high dimension and comparing the results with the known ones. The proposed algorithm improves the new record solution for 1 benchmark instance widely used in the literature.
|
| first_indexed | 2025-11-27T04:09:59Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-84820 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-11-27T04:09:59Z |
| publishDate | 2014 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шило, П.В. 2015-07-15T20:11:26Z 2015-07-15T20:11:26Z 2014 Применение "бесполезных" ходов при решении задачи о покрытии / П.В. Шило // Компьютерная математика. — 2014. — № 1. — С. 150-158. — Бібліогр.: 11 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84820 519.854.33 Предложена модификация алгоритма случайного повторного локального поиска для решения задачи о покрытии с применением «бесполезных» ходов, что позволяет расширить поисковые возможности алгоритма. Эффективность разработанного алгоритма подтверждена экспериментально при решении задач большой размерности, а также сравнением полученных результатов с известными. С помощью предложенного алгоритма найдено новое рекордное решение. Запропонована модифікація алгоритму випадкового повторного локального пошуку для розв'язання задачі про покриття із застосуванням «даремних» ходів, що дозволяє розширити пошукові можливості алгоритму. Ефективність розробленого алгоритму підтверджена експериментально при розв'язанні задач великої розмірності, а також порівнянням отриманих результатів із відомими. За допомогою запропонованого алгоритму знайдено новий рекордний розв'язок. In this paper, the modification of a new algorithm based on the iterated random local search for Minimum Cardinality Set Covering Problem (MCSCP) with “useless” moves is proposed that makes it possible to increase its search capabilities. The efficiency of the algorithm is confirmed experimentally by solving problems of high dimension and comparing the results with the known ones. The proposed algorithm improves the new record solution for 1 benchmark instance widely used in the literature. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Применение "бесполезных" ходов при решении задачи о покрытии Застосування «даремних» ходів при розв'язанні задачі про покриття Application of “useless” moves to minimum cardinality set covering problem Article published earlier |
| spellingShingle | Применение "бесполезных" ходов при решении задачи о покрытии Шило, П.В. Теория и методы оптимизации |
| title | Применение "бесполезных" ходов при решении задачи о покрытии |
| title_alt | Застосування «даремних» ходів при розв'язанні задачі про покриття Application of “useless” moves to minimum cardinality set covering problem |
| title_full | Применение "бесполезных" ходов при решении задачи о покрытии |
| title_fullStr | Применение "бесполезных" ходов при решении задачи о покрытии |
| title_full_unstemmed | Применение "бесполезных" ходов при решении задачи о покрытии |
| title_short | Применение "бесполезных" ходов при решении задачи о покрытии |
| title_sort | применение "бесполезных" ходов при решении задачи о покрытии |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84820 |
| work_keys_str_mv | AT šilopv primeneniebespoleznyhhodovprirešeniizadačiopokrytii AT šilopv zastosuvannâdaremnihhodívprirozvâzannízadačípropokrittâ AT šilopv applicationofuselessmovestominimumcardinalitysetcoveringproblem |