Анализ полученных данных

Применение методов искусственного интеллекта в переборных алгоритмах

Для начала проанализируем данные из таблиц для значения A=0,5. Эти таблицы выделяются среди прочих лишним столбцом, который находится сразу за столбцом с обозначениями оценок, отмечен знаком "-" и содержит информацию о чемпионатах "без правил". Значения наиболее легко вычисляемых полей в этом столбце можно найти и чисто теоретически, что мы и сделаем. Итак, если в чемпионате участвуют N_p игроков, то вероятность, что какой-то из них, а значит и лучший, окажется на первом месте, равна 1/N_p. Для 8, 16, 32 и 64 игроков это составит соответственно 0.125, 0.0625, 0.03125 и 0.015625. Оценка первых трех в свою очередь составит T(N_p)=3(N_p+1)/2-6=3(N_p-3)/2, то есть 7.5, 19.5, 43.5, 91.5.

Теперь посмотрим на соответствующие поля в таблицах и убедимся, что экспериментальные данные отличаются незначительно. Это подтверждает то, что используемый датчик случайных чисел работает удовлетворительно, по крайней мере в плане распределения вероятностей. Далее, в указанных таблицах сравним значения по строкам. В идеале все значения в одной строке должны совпадать, совпадение свидетельствовало бы о полном соответствии моделей и методов вычисления реальной ситуации. Как видим, отличия здесь есть, но небольшие. Причем наибольшие расхождения соответствуют возможному появлению совокупных мест. Так, например, в таблице 16, в строке D, содержащей полную невязку. Наибольшим отличием от столбца "-" обладают олимпийские нерекурсивные системы, а наименьшим - олимпийские рекурсивные. При этом первые предполагают весьма объемные совокупные места - до половины участников, а вторые исключают совокупные места совсем. Итак, можно говорить о том, что проверка при помощи подстановки параметра А=0,5 подтвердила непротиворечивость полученных экспериментальных данных.

Теперь обратимся к основным данным. По показателю частоты победы сильнейшего имеем следующие результаты. При N_p=8, N_p=16 лучшие оценки принадлежат олимпийским системам с матчами, затем идет круговая система, затем с небольшим отрывом швейцарская, затем олимпийские без матчей. При N_p=32, N_p=64 круговая система "обходит" соперниц и увеличивает разрыв. Разрыв между швейцарской системой и олимпийскими с матчами с ростом N_p сокращается. Олимпийские без матчей безнадежно "отстают". По показателям невязки и первой тройки имеем аналогичные результаты, причем с ростом N_p швейцарская система обходит олимпийские по всем этим показателям и уступает только круговой.

Общий вывод таков: круговая система имеет непревзойденные показатели точности, за ней идут швейцарская и олимпийские с матчами, затем олимпийские без матчей, причем с ростом числа участников швейцарская приближается к олимпийским с матчами по частоте побед сильнейшего и опережает их по остальным критериям. Однако, сопоставляя эти выводы с данными по количеству партий, можно сказать, что показатели точности круговой системы оправдывают себя только при самых малых значениях N_p, а среди приемлемых по числу партий систем лидирует швейцарская, так как требует меньшее количество партий, чем олимпийские с матчами, а свое отставание по показателям точности при малых N_p компенсирует значительно меньшим числом партий. Далее следует вспомнить о дополнительных критериях отбора систем проведения чемпионатов, а именно о гибкости оценок точности. Увеличить точность в олимпийской системе без матчей можно, лишь превратив ее в олимпийскую систему с матчами. Точность круговой системы и без того высока, а увеличивать в ней количество партий вовсе не имеет смысла.

Самые гибкие системы - это олимпийская с матчами и швейцарская. Напомним, что увеличить точность в первой можно, увеличив число партий в матче, а во второй - увеличив число туров. При этом число партий с каждым шагом в первом случае будет увеличиваться на 2N_p, а во втором - на N_p/2. Очевидно, преимущество здесь на стороне швейцарской системы. Наконец, все олимпийские системы имеют один общий недостаток - их алгоритм прост лишь при количестве игроков, равном степени двойки, в то время как для швейцарской системы это требование ограничивается лишь четностью. Заметим, что рекурсивные олимпийские системы исследованы в основном для более точной оценки невязки соответствующих олимпийских систем и сами по себе отдельного интереса не представляют.

А.В.Мосеев, underwood.narod.ru, 1999 год