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

Question

Я хотел бы ранжировать или сортировать коллекцию предметов (с размером потенциально более 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]. В этом случае допустимо либо упорядочение.

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

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

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

Answer 1

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

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

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

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

Answer 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

Answer 3

Я гугл на это, обратите внимание на главу 12.3 Топологической сортировку и Depth- первой Поиск

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

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