Алгоритм ранжирования на основе сравнения

Я хотел бы ранжировать или сортировать коллекцию элементов (с размером потенциально более 100 000), когда элементы в коллекции не имеют собственного (сопоставимого) значения, вместо этого все, что у меня есть, это сравнение между любыми двумя элементами, которые были предоставлены пользователями субъективным образом.

Пример. Рассмотрим коллекцию с элементами [a, b, c, d] и сравнениями пользователями b > a, a > d, d > c. Правильный порядок этой коллекции будет [b, a, d, c].

Этот пример прост, однако могут быть более сложные случаи:

  • Поскольку сравнения являются субъективными, пользователь также может сказать, что c > b. В этом случае это приведет к конфликту с указанным выше порядком.
  • Также у вас могут не быть сравнения, которые "соединяют" все элементы, т.е. b > a, d > c. В этом случае упорядочение неоднозначно. Это может быть [b, a, d, c] или [d, c, b, a]. В этом случае допустимо либо упорядочение.

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

Аналогичное применение этого алгоритма использовалось приложением Zuckerberg FaceMash, где он оценивал людей на основе сравнений (если я правильно понял), но я не смог найти, что это за алгоритм.

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

Ответы

Ответ 1

Это проблема, которая уже произошла на другой арене: конкурентные игры! Здесь также цель - присвоить каждому игроку глобальный "ранг" на основе серии 1 против 1 сравнения. Трудность, конечно, в том, что сравнения не являются транзитивными (я беру "субъективный", чтобы означать "предоставленный человеком" в вашем вопросе). Каспаров бьет Фишера (не знаю другого шахматиста!) Боб побеждает Каспарова, возможно.

Это приводит к бесполезным алгоритмам, которые полагаются на транзитивность (т.е. a > b and b > c => a > c), поскольку вы в конечном итоге получаете (очень) циклический график.

Для решения этой проблемы были разработаны несколько рейтинговых систем.

Самой известной системой является, вероятно, алгоритм Elo/score для конкурентоспособных шахматистов. Его потомки (например, система оценки Glicko) более сложны и учитывают статистические свойства записи о выигрыше/проигрыше --- в других слова, насколько достоверен рейтинг? Это похоже на вашу идею взвешивания более тяжелых записей с более "играми". Glicko также создает основу для системы TrueSkill, используемой в Xbox Live для многопользовательских видеоигр.

Ответ 2

Вас может заинтересовать проблема минимальной обратной связи. По сути, проблема заключается в том, чтобы найти минимальное количество сравнений, которые "идут не так", если элементы линейно упорядочены в некотором порядке. Это то же самое, что и поиск минимального количества ребер, которые нужно удалить, чтобы сделать график ацикличным. К сожалению, решение проблемы точно NP-сложно.

Несколько ссылок, которые обсуждают проблему:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8157&rep=rep1&type=pdf

http://en.wikipedia.org/wiki/Feedback_arc_set

Ответ 3

Я искал это, ищите главу 12.3, Топологическую сортировку и Глубокий поиск

http://www.cs.cmu.edu/~avrim/451f09/lectures/lect1006.pdf

В вашем наборе отношений описывается ориентированный ациклический граф (надеюсь, ациклический), и поэтому топографическая сортировка графа - это именно то, что вам нужно.