Алгоритм определения рейтинга после многократного выбора между пунктами

Question

Я хотел бы написать небольшую программу, чтобы помочь мне ранжировать элементы, основываясь на результатах сравнений один на один.

Так что, если у меня есть 100 элементов, я бы позволил пользователям многократно выбирать между двумя случайными числамивыбранные элементы этого набора.Допустим, всего было 10.000 голосов.№ объекта10 набрали 1000 голосов и выиграли все прямые противостояния со всеми остальными предметами.№ объекта90 набрал 100 голосов, выиграл 40 и проиграл 60 прямых противостояний.Существует ли существующий алгоритм (например, из рекомендательных систем или аналогичный), который я могу использовать для составления ранжированного списка этих элементов?

Answer 1

Простой способ - это ранжировать на основе win percentage, то есть total wins/total confrontations

Если вы хотите иметь единый механизм подсчета очков, вы можете reward победитель и punish проигравший на фиксированную сумму, а затем ранжироваться на основе окончательного результата.

Наконец, вы можете взглянуть на Elo ranking algorithm, он рассчитал вероятность каждого предмета, выигравшего конфронтацию, и rewards and punishes относительно этих вероятностей.

Пример

# Probability
A higher chance of winning than B

# Case1: A wins
A +small reward
B -small punishment

# Case2: B wins
A -large punishment
B +large reward

Answer 2

Если вы просто хотите сделать то, что вы объяснили (вы не просили никакой оптимизации или подобного), тогда алгоритм очень прост.

1. Постройте матрицу всех возможных сравнений.
2. Ранжируйте каждый элемент по количеству побед в его столбце.

В псевдокоде это может выглядеть так:

# given a list of elements:
elements = ...

# build the comparison matrix:
matrix = Matrix(n, n)
for i in 0..n-1:
  for j in 0..n-1:
    matrix[i][j] = elements[i] < elements[n]

# rank each element by its "wins":
for i in 0..n-1:
  ranks[i] = sum(matrix[i])

После этого ranks[i] будетукажите ранг elements[i] для каждого i , чтобы вы могли отсортировать elements по ranks.