ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2021; 1: 12-17
http://dx.doi.org/10.17213/1560-3644-2021-1-12-17
СРАВНИТЕЛЬНЫЙ АНАЛИЗ МОДИФИКАЦИЙ АЛГОРИТМА ПЛОТНИКОВА–ЗВЕРЕВА ПО РАЗЛИЧНЫМ КРИТЕРИЯМ С ИСПОЛЬЗОВАНИЕМ БАРЬЕРА ПРИ РЕШЕНИИ МИНИМАКСНОЙ ЗАДАЧИ
Кобак Валерий Григорьевич – д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: valera33305@mail.ru
Жуковский Александр Георгиевич – д-р полит. наук, профессор, канд. техн. наук, доцент, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: zhykovskij@mail.ru
Шкабрий Роман Сергеевич – бакалавр, Донской государственный технический университет, г. Ростов-на-Дону. Россия. E-mail: shkabriy@mail.ru
Аннотация
Рассматривается проблема решения неоднородной минимаксной задачи – одной из многочисленных задач из области комбинаторной оптимизации. Комбинаторная оптимизация – это широкая и бурно развивающаяся область математического программирования и дискретной математики. Неоднородная минимаксная задача входит в число NP-полных и является трудно решаемой. Для ее решения используются алгоритмы (списочные, генетические, муравьиные и т.д.), получающие приближенные решения, близкие к оптимальным за полиномиальное время. Предлагается использовать модифицированный списочный алгоритм на основе алгоритма Плотникова–Зверева. Данный алгоритм рассматривается с барьером, который был исследован в предыдущих работах. При использовании барьера увеличивается точность решения благодаря использованию минимаксного критерия. В предлагаемой работе кроме минимаксного критерия применяется квадратичный критерий с барьером и без него. Так как аналитически определить, какой из модифицированных алгоритмов более эффективен, практически невозможно, был поставлен вычислительный эксперимент, состоящий в многочисленных запусках алгоритмов над одними и теми же данными. По результатам вычислительного эксперимента проводится сравнение различных критериев. Применение квадратичного критерия с барьером приводит к повышению эффективности решения неоднородной минимаксной задачи.
Ключевые слова: алгоритм Плотникова–Зверева; алгоритм Плотникова–Зверева по квадратичному критерию; алгоритм Плотникова–Зверева по квадратичному критерию с барьером; вычислительный эксперимент; NP-полные задачи.
Полный текст: [in elibrary.ru]
Ссылки на литературу
- Алексеев О.Т. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.
- Коффман Э.Г. Теория расписания и вычислительные машины. M.: Наука. 1987.
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ / под ред. Л.Н. Красножан. М.: Вильямс, 2013. 1328 с.
- Полиномиальное время // Дискретная математика: алгоритмы. URL http://rain.ifmo.ru/cat/view.php/theory/algorithm-analy sis/ np-completeness-2004 (дата обращения 11.01.2021).
- Трансвычислительная задача // Википедия – Свободная энциклопедия URL https://ru.wikipedia.org/wiki/ Трансвычис- лительная задача (дата обращения 11.01.2021).
- Кобак В.Г, Муратов М.А. Сравнительный анализ критериев эффективности при решении неоднородной минимаксной задачи списочным алгоритмом // Вестн. Донского гос. техн. ун-та. 2011. № 7. С. 1132 – 1135.
- Кобак В.Г, Поркшеян В.М., Кузин А.П. Исследование различных модификаций алгоритма Плотникова–Зверева при решении неоднородной минимаксной задачи // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2020. № 2. С. 5 – 12. DOI:10.17213/1560-3644-2020-2-5-12.
- Кобак В.Г, Золотых О. А., Жуковский А.Г., Ростов А.Н. Различные подходы к решению однородной минимаксной задачи теории расписаний эвристическими алгоритмами // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 1. С. 41 – 46. DOI:10.17213/0321-2653-2016-1-41-46.
- Кобак В.Г, Золотых О.А., Жуковский А.Г., Ростов А.Н. Решение однородной минимаксной задачи различными модификациями алгоритма Крона. Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 3. С. 3 – 8. DOI:10.17213/0321-2653-2016-3-3-8.
- Коновалов И.С., Кобак В.Г, Остапенко С.С. Сравнение эффективности работы точных и приближенных алгоритмов для решения задачи покрытия множества // Вестн. Донского гос. техн. ун-та. 2017. № 3. С. 137 – 144.