Алгоритмы решения задачи покрытия множества
Приведен обзор алгоритмов решения задачи покрытия множества. Рассматриваются две альтернативные формулировки задачи покрытия множества, используемые авторами алгоритмов. Дается классификация алгоритмов решения задачи покрытия множества. Рассматриваются особенности наиболее известных алгоритмов решения задачи покрытия множества. Основное внимание уделено алгоритмам, использующим метаэвристики. Среди метаэвристик различают основанные на популяции и на единичных данных. К метаэвристикам, основанным на популяции, относятся: основанные на рое; на физике; на основе эволюции; на основе человека. Метаэвристики на основе единичных данных: имитация отжига; поиск табу; управляемый локальный поиск; жадная рандомизированная процедура адаптивного поиска.
Авторы: П. И. Васькин, А. А. Лисс
Направление: Информатика, вычислительная техника и управление
Ключевые слова: задача покрытия множества, таблица покрытия, правила преобразования таблиц покрытия, методы решения таблиц покрытия, метаэвристические методы
Открыть полный текст статьи