ПРИМЕНЕНИЕ ПОЛНОГО И ЧАСТИЧНОГО ПЕРЕБОРА  ДЛЯ РЕШЕНИЯ МАЛОРАЗМЕРНЫХ КОМБИНАТОРНЫХ ЗАДАЧ

В.M. Глушань; А.В.  Зубрицкий

В.M. Глушань Южный Федеральный Университет
А.В. Зубрицкий Южный Федеральный Университет

Ключевые слова: Малоразмерная комбинаторная задача; турнирная таблица; частичный и полный перебор; оптимальное решение.

Аннотация

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

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

Литература

1. Липский В. Комбинаторика для программистов: Пер. с польск.–М.: Мир, 1988. – 213 с.
2. Новиков Ф.А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения. – СПб.: Питер. 2014. – 432 с.
3. Хаггарти Р. Дискретная математика для программистов. Издание 2-е, исправленное. Пер. с англ. Под ред. С.А. Кулешова. – М.: Техносфера, 2012. – 400 с.
4. Андерсен Дж. Дискретная математика и комбинаторика. Пер. с англ. – М.: ООО «И.Д. Вильямс», 2016. – 960 с.
5. Гладков Л.А., Курейчик В.В., Курейчик В.М. Дискретная математика // Учебник. – М.: Физматлит, 2014. – 496 с.
6. Хаггард Г., Шлипф Дж., Уайтсайдс С. Дискретная математика для программистов: учебное пособие. Пер. с англ. – М.: БИНОМ. Лаборатория знаний, 2010. – 627 с.
7. Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции // Enumerative Combinatorics. Volume 2. – М.: «Мир», 2009. — 767 c.
8. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР // М.: «Радио и связь», 1990. – 216 с.
9. Глушань В.М., Пупков М.И., Щербаков Л.И. Алгоритмы формирования упорядоченных r-выборок // Кибернетика. – 1988. –№ 1. – с.129-131.
10. Глушань В.М., Левин И.П., Щербаков Л.И. Аппаратурное формирование случайной последовательности сочетаний единичных сигналов // Известия вузов. Приборостроение. – 1987. – Т.ХХХ, № 4. – с.37-42.
11. Тимошевская Н.Е. Разработка и исследование параллельных комбинаторных алгоритмов // Прикладная дискретная математика. – 2009. – №2(4). – с. 97-103.
12. Тимошевская Н.Е. О нумерации перестановок и сочетаний для организации параллельных вычислений в задачах проектирования управляющих систем // Известия Томского политехнического университета. – 2004. – том 307. – № 6. – с. 18-20.
13. Герасимов В.А. Генерация случайных сочетаний. Генерация сочетаний по его порядковому номеру // RSDN Magasine. – 2010. – № 3.
14. Тимошевская Н.Е. Параллельная генерация сочетаний и перестановок // Вторая Сибирская школа-семинар по параллельным вычислениям / Под ред. проф. А.В. Старченко. – Томск: Изд-во Том. ун-та, 2004. – 108 c.
15. Рябко Б.Я. Быстрая нумерация комбинаторных объектов // Дискретная математика, Т. 10. –1998, с.101–119.
16. Глушань В.М.,. Зубрицкий А.В. Алгоритм разбиения множества по его номеру на совокупность равномощных подмножеств // Известия ЮФУ. Технические науки, № 4, (198). – 2018, с.59-65.
17. Зубрицкий А.В. Развитие средств информационной поддержки принятия решений в социально-технологических системах // Сборник трудов ХIV Всероссийской научной конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (ИТСАУ-2016). – Таганрог: Издательство Южного федерального университета, 2016 – Т.1. – 339 с.
18. Глушань В.М., Зубрицкий А.В. Теоретическое обоснование алгоритма формирования упорядоченных разбиений с равномощными бесповторными выборками // Труды Конгресса по интеллектуальным системам и информационным технологиям «IS&IT'17». Научное издание в 3-х томах. – Таганрог: Изд-во Ступина С.А. 2017, – Т.2. – с.104-112.
19. Глушань В.М., Кажаров А.А., Пономарев В.К., Данильченко В.И. Развитие информационного обеспечения региональных и международных спортивных соревнований // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT’14». Научное издание в 4-х томах. – М.: Физматлит, 2014. – Т. 3.
20. Glushan V., Zubritckii A., Lozovoy A. Formation of proximate two-criterion tournament tables // Advances in Computer Science Research (ACSR), volume 72. pp. 160-163.
21. Глушань В.М., Зубрицкий А.В. Сужение области поиска решений для некоторых многокритериальных комбинаторных задач // Труды конгресса по интеллектуальным системам и информационным технологиям «IS&IT’18». Научное издание в 3-х томах, –Таганрог: Изд-во Ступина А.С., 2018 – Т.1. – c. 272-279.
22. Брахман Т.Р. Многокритериальность и выбор альтернативы в технике. – М.: Радио и связь, 1984. – 288 с.