Ранжирование - минимизация парного сравнения

Question

У меня есть список из 100 предметов, и я хочу сгенерировать ранжированный список, пользователю предлагается оценить пары предметов, предлагая: «Вы предпочитаете предмет A или пункт B вместо этого?». Поскольку было бы очень утомительно просить каждую возможную комбинацию этих предметов. Например. если элемент 1 предпочтительнее элемента 2, а элемент 2 предпочтительнее элемента 3, нет необходимости сравнивать элемент 1 и пункт 3.

Я ищу алгоритм, который сокращает такие сравнения и даст полный список рейтинга.

Если число сравнений будет улучшено за счет использования трех пар элементов, это будет предпочтительным способом. В этом случае пользователь будет оценивать лучшие и худшие из 3 пар, таким образом оценивая 3 элемента за «ход».

Answer 1

Есть 100! возможных заказов. 2^524 < 100! < 2^525 так что лучшее, что вы можете сделать, это 525 бинарные вопросы.

Версия с 3 вопросами работает лучше. Он может дать 6 возможных ответов, поэтому лучшее, что вы можете сделать с помощью одного и того же анализа, - это 204 вопросов.

Маловероятно, что вы легко сможете достичь этих границ. Но вы можете приблизиться.

Для бинарных сравнений будет трудно добиться большего успеха, чем сортировка с вставкой слиянием Ford-Johnson 1012 *.

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

Точный расчет будет слишком сложным. Но жадный подход заключается в следующем. Для каждого элемента подсчитайте, сколько других известно, что они лучше, а сколько - хуже. Сортируйте их в список приоритетов по: «наименьшее из известных сравнений», а затем «наименьшая разница между лучше / хуже», а затем «наименьшее из известных хуже», а затем «исходный порядок».

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

Пример может помочь. Давайте попробуем отсортировать 2, 4, 1, 3, 5 с 3 путями сравнения. Без информации мы сначала просто принимаем заказ, который нам дали. Мы начнем со сравнения 2, 4, 1 и выясним, что это 1, 2, 4. На данный момент мы знаем:

1: better: 2, 4; worse:
2: better: 4; worse: 1
3: better: ; worse:
4: better: ; worse: 1, 2
5: better: ; worse:

Теперь мы сортируем по наименьшему количеству сравнений, затем наименьшей разнице между числом лучших и худших, затем наименьшим худшим, а затем исходным порядком. Это дает 3, 5, 2, 1, 4. Ни один из 3, 5, 2 не был сравнен, поэтому мы делаем это затем, чтобы получить 2, 3, 5. Теперь мы знаем:

1: better: 2, 3, 4, 5; worse:
2: better: 3, 4, 5; worse: 1
3: better: 5; worse: 1, 2
4: better: ; worse: 1, 2
5: better: ; worse: 1, 2, 3

И теперь наш приоритет сортировки дает нам 4, 3, 5, 2, 1. Мы берем 4, 5. Все сравнивали с одним из них, поэтому мы go до 3, потому что это еще не было по сравнению с 4. Эти три сравнивают 3, 4, 5. Теперь мы знаем:

1: better: 2, 3, 4, 5; worse:
2: better: 3, 4, 5; worse: 1
3: better: 4, 5; worse: 1, 2
4: better: 5; worse: 1, 2, 3
5: better: ; worse: 1, 2, 3, 4

И мы отсортировали 5 вещей с помощью 3 3-сторонних сравнений. Что теоретически лучшее, что мы могли сделать. (Поскольку вы увеличиваете число, я сомневаюсь, что вы будете часто делать то же самое. Но это должно превзойти бинарную стратегию.)

Answer 2

Вы могли бы представить 100, затем спросить о лучшем, затем о следующем лучшем, и так далее, для 99 вопросов, в результате чего ваш окончательный рейтинг.