Применение "бесполезных" ходов при решении задачи о покрытии

Abstract

Предложена модификация алгоритма случайного повторного локального поиска для решения задачи о покрытии с применением «бесполезных» ходов, что позволяет расширить поисковые возможности алгоритма. Эффективность разработанного алгоритма подтверждена экспериментально при решении задач большой размерности, а также сравнением полученных результатов с известными. С помощью предложенного алгоритма найдено новое рекордное решение.

Запропонована модифікація алгоритму випадкового повторного локального пошуку для розв'язання задачі про покриття із застосуванням «даремних» ходів, що дозволяє розширити пошукові можливості алгоритму. Ефективність розробленого алгоритму підтверджена експериментально при розв'язанні задач великої розмірності, а також порівнянням отриманих результатів із відомими. За допомогою запропонованого алгоритму знайдено новий рекордний розв'язок.

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.