Вычисление очков от неполных сравнительных таблиц
Когда я был в средней школе и приобретении знаний о матрицах, нам показали технику, которая поможет в такой ситуации:
В лиге существует много шахматистов, и они должны определить рейтинг для всех них, но не имеют достаточного количества времени для каждого плеера для проигрывания любого человека. Если это заканчивается, что Плеер, Игрок ударов B и Игрок B побеждают Игрока C, можно сказать с некоторым уровнем уверенности, что Игрок A лучше, чем Игрок C, и поэтому присудите некоторые очки плееру вместо них на самом деле проигрывание друг друга.
Как я сказал, это было только что, и я не могу помнить, как на самом деле выполнить алгоритм, но я думаю, что это назвали чем-то как "матрица доминирования". Поиск сети для этого был бесплоден и время от времени страшен, таким образом, я не думаю правильно.
Кто-либо может дать мне некоторую справку? Идеально алгоритм, который я могу использовать для этой программы, я продолжаю работать, но даже просто указатель еще на некоторую информацию о процедуре.
4 ответа
Звучит так, как будто вы описываете турнир по швейцарской системе или очень похожую вариацию - все это описано в связанной с Википедией статье. Хотя вместо того, чтобы дать неполный турнир для подсчета рейтингов, это способ организовать турнир для составления пары лучших и худших шахматистов с лучшими и худшими шахматистами для определения рейтинга без необходимости того, чтобы все играли с остальными.
.Может быть, вам подойдет какой-нибудь тип алгоритма PageRank.
Представьте, что у каждого человека есть веб-страница, на которой он гиперссылка на каждого, кто его победил.
Запуск алгоритма ранжирования страницы по этим данным даст вам устойчивое состояние матрицы ссылок, которое может указывать вам на относительную важность каждого человека (я полагаю).
Например, человек, который играл только в одну игру, но в этой игре победил того, кто победил много людей, может иметь более высокий ранг страницы, чем тот, кто победил 10 человек, которые, в свою очередь, не выиграли ни одной игры.
.Похоже, что Вы помните презентацию теоремы Перрона-Фробениуса - которая, по крайней мере, является более безопасным поисковым термином :-). Один из них - на http://www.math.utah.edu/~keener/lectures/rankings.pdf Шахматисты используют систему Эло, описанную по адресу http://en.wikipedia.org/wiki/Elo_rating_system и http://www.chesselo.com/, которую было бы проще реализовать. Возможно, что хорошего рейтинга не существует, даже если вы все знаете - смотрите http://en.wikipedia.org/wiki/Nontransitive_dice. Люди, моделирующие футбол, обычно отдельно следят за оборонительными и наступательными силами.