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