APPLICATION OF EXHAUSTIVE AND PARTIAL SEARCH FOR SOLUTION LOW-SIZED COMBINATOR PROBLEMS
Abstract
Currently, there are many combinatorial problems for which the optimal solution theoretically can be found using the brute force method. However, the number of solutions for such problems increases exponentially with the size of problems. This excludes the possibility of a quick search for optimal solutions using brute force, even for medium-sized problems. Among combinatorial problems there are also small-sized problems. These are problems with set of elements equal several dozen. These problems include assignment and backpack problems, as well as the problem of creating tournament tables. The rapid improvement of computer technology allows us to solve some small combinatorial problems in real time. The article presents several approaches to the optimal formation of tournament tables, which are the result of the draw. This is important for those sports that involve a relatively large number of players from different regions. In these cases, the purpose of the draw is to separate players into different groups so that groups have approximately the same total rating and regional factor. Under this condition, the problem becomes two-criteria. If the number of participants is within two dozen, then the problem can still be solved by exhaustive search in a reasonable time. With the number of participants in tournament beyond two dozen brute force is almost not applicable.
Two combined algorithms for the formation of tournament tables are proposed. The first is based on the heuristic “snake” method and the brute force method. The second algorithm is based on the preliminary formation of several groups by partial enumeration, and the remaining groups by a sequential method. The developed combined algorithms can significantly increase the number of players in the standings with the permissible time of their work. Since the proposed algorithms are approximate, a method for assessing the quality of the results of their work with respect to the optimal solution has been developed. Testing of the presented algorithms was carried out using both randomly generated tests and tests based on real ratings, the algorithms were compared and recommendations on their use were given.
References
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 с.
