Preview

Вестник Донского государственного технического университета

Расширенный поиск

Сравнение эффективности работы точных и приближенных алгоритмов для решения задачи о покрытии множества

https://doi.org/10.23947/1992-5980-2017-17-3-137-144

Полный текст:

Аннотация

Введение. Множество практических задач опирается на задачу покрытия множеств: построение расписаний, расположение пунктов обслуживания, построение электронных схем. Это определяет актуальность поиска способов повышения эффективности решения данной задачи. Материалы и методы. Рассматриваются методы решения задачи о покрытии множества точным и приближенным алгоритмами. В качестве приближенного метода используется генетический алгоритм, в качестве точного - метод ветвей и границ. Результаты исследования. Генетический алгоритм во всех своих модификациях по временным характеристикам показал предсказуемость и стабильность во всех сериях экспериментов. Метод ветвей и границ был применен к задаче покрытия множеств и показал точные результаты. Обсуждение и заключения. Проведенные исследования показали, что для множеств небольших размеров целесообразно использовать метод ветвей и границ, который продемонстрировал быстрое время выполнения при гарантированно точном результате. Для множеств больших размеров рекомендуется использовать генетический алгоритм, который гарантирует результат с незначительной погрешностью, причем изменение времени его работы стабильно и предсказуемо.

Об авторах

Игорь Сергеевич Коновалов
Донской государственный технический университет
Россия


Сергей Сергеевич Остапенко
Донской государственный технический университет
Россия


Валерий Григорьевич Кобак
Донской государственный технический университет
Россия


Список литературы

1. Коновалов, И. С. Сравнительный анализ работы жадного алгоритма Хватала и модифицированной модели Голдберга при решении взвешенной задачи нахождения минимального покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Труды СКФ МТУСИ. - Ростов-на-Дону: ПЦ «Университет» СКФ МТУСИ, 2015 - С. 366-371.

2. Коновалов, И. С. Стратегия элитизма модифицированной модели Голдберга генетического алгоритма при решении задачи покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Вестник компьютерных и информационных технологий. - 2016. - №4. - С. 50-56.

3. Коновалов, И. С. Применение генетического алгоритма для решения задачи покрытия множеств / И. С. Коновалов, В. А. Фатхи, В. Г. Кобак // Вестник Дон. гос. техн. ун-та. - 2016. - № 3. - С. 125-132.

4. Еремеев, А. В. Генетический алгоритм для задачи о покрытии / А. В. Еремеев // Дискретный анализ и исследование операций. - 2000. - Т. 7, № 1. - С. 47-60.

5. Еремеев, А. В. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования / А. В. Еремеев, Л. А. Заозерская, А. А. Колоколов // Дискретный анализ и исследование операций. - 2000. - Т. 7, № 2. - С. 22-47.

6. Holland, J. H. Adaptation in Natural and Artificial Systems. - The University of Michigan Press, 1975. - P. 245.

7. Goldberg, D. E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989. - P. 432.

8. Батищев, Д. И. Генетические алгоритмы решения экстремальных задач / Д. И. Батищев. - Воронеж : изд-во Воронеж. гос. техн. ун-та, 1995. - 121 с.

9. Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик. - Москва : ФИЗМАТЛИТ, 2010. - 368 с.

10. Алексеев, О. Г. Некоторые алгоритмы решения задачи о покрытии и их экспериментальное исследование на ЭВМ / О. Г. Алексеев, В. Ф. Григорьев // Журнал вычислительной математики и математической физики. - 1984. - Т. 24, №10. - С. 1565-1570.


Для цитирования:


Коновалов И.С., Остапенко С.С., Кобак В.Г. Сравнение эффективности работы точных и приближенных алгоритмов для решения задачи о покрытии множества. Вестник Донского государственного технического университета. 2017;17(3):137-144. https://doi.org/10.23947/1992-5980-2017-17-3-137-144

For citation:


Konovalov I.S., Ostapenko S.S., Kobak V.G. Efficiency comparison of exact and approximate algorithms for solving set covering problem. Vestnik of Don State Technical University. 2017;17(3):137-144. (In Russ.) https://doi.org/10.23947/1992-5980-2017-17-3-137-144

Просмотров: 75


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1992-5980 (Print)
ISSN 1992-6006 (Online)