Как объединить коллекцию упорядоченных предпочтений

Question

У меня есть набор из r рецензентов, которые оценивают набор из n объектов.Каждый рецензент самостоятельно составляет упорядоченный список объектов, которые он или она выбирает для ранжирования.Цель состоит в том, чтобы создать один список, который является объединением различных упорядоченных списков.Мы можем предположить, что точка зрения каждого рецензента одинаково взвешена.

Это отличается от большинства вопросов с объединением и упорядоченным списком тем, что не существует глобального упорядочения.Один рецензент может оценить A> B, а другой может оценить B> A. Как уже упоминалось, каждый объект не обязательно оценивается каждым рецензентом.

Моя текущая мысль состоит в том, чтобы разложить список каждого рецензента на набор упорядоченных кортежей для каждой из m * (m-1) * .5 уникальных пар записей в списке, где m - количество объектов.рейтинг.Теперь возьмите все кортежи от всех рецензентов.Для данной комбинации (a, b) найдите все такие кортежи и возьмите большинство голосов (из числа участвующих в голосовании), чтобы определить, является ли a Теперь у меня есть набор упорядоченных кортежей, которые представляют мудрость всех.Но как мне превратить их в один упорядоченный список?Я могу начать со случайно выбранной пары объектов и упорядочить их, затем добавить еще один в правильном порядке, но результат будет зависеть от того, с какого я выберу начинать.Также могут быть петли.

Буду признателен за любые идеи.

Answer 1

Пространство, по которому вы перемещаетесь, по сути (изоморфно) подмножество теории голосования, та часть, в которой бюллетени и итоги представляют собой упорядоченные списки кандидатов.

Вам может быть полезно прочитать следующее:

• Метод Кондорсе - дает полезный критерий "правильности".
• Метод Шульце - дает O (n ³ ) алгоритм для достижения этого.
• Система голосования - дает вам другие желательные критерии и сравнивает различные подходы.
• Подсчет Борды - по сути то же самое, что и принятый в настоящее время ответ .
• Теорема невозможности стрелки - показывает, почему вы не можете одновременно взять свой пирог и съесть его.

Основываясь на моих знаниях теории голосования, я дам вам рекомендацию: если вы разумно полагаете, что алгоритм O (n ³ ) работает для вашего конкретного набора данных,опробуйте метод Шульце .В противном случае Borda Count - единственный перечисленный метод, который выполняется за O (n) время и принимает ранжирование в качестве входных данных для голосования, поэтому придерживайтесь этого.

Answer 2

Решение, которое кажется элегантным и все еще делает то, что ему нужно, состоит в преобразовании каждого заказа в баллы от 1 до 0, где 1 - это первый (верхний) элемент в списке данного рецензента, а 0 - их последний.(нижний элемент) и все промежуточные элементы получают линейно масштабированный счет.Таким образом, если рецензент 1 оценивает только 3 элемента, он получит оценки для этого списка 1, 0,5 и 0. Затем вы просто берете среднюю оценку для каждого элемента, чтобы создать сопоставленный список.Связи могут быть разбиты по количеству «обзоров» для элемента (так, чтобы элемент, единодушно отмеченный как лучший из 3 рецензентов, оказался в окончательном списке выше, чем элемент, единодушно отмеченный как лучший из 2 рецензентов и т.

Ваше требование: «Цель состоит в том, чтобы составить один список, который является объединением различных упорядоченных списков. Мы можем предположить, что точка зрения каждого рецензента одинаково взвешена».этот простой алгоритм определенно удовлетворяется, но часто такие проблемы предъявляют более сложные требования, когда вы их изучаете.

Answer 3

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

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

Answer 4

Предметы: Герцог навсегда Quake UT3 Duke3d Halo

REV1:
- Duke nukem forever
- Duke3d

REV2:
- Duke3d
- UT3
- Quake

REV3:
- Duke3d
- Duke nukem forever

Логический вывод:

• REV1: Герцог навсегда> duke3d #
• REV1: Duke3d
• REV2: Duke3d> UT3%
• REV2: UT3
• REV2: Duke3d> Quake %%
• REV2: Quake
• REV2: UT3> Quake %%%
• REV2: Quake
• REV3: Duke3d> Герцог навсегда #
• REV3: Герцог навсегда

Большинство проголосовавших:

• Duke3d 3
• Герцог навсегда 2
• UT3, Quake 1

Удалите #, которые противоречат, создавая противоречивые пары и преобразуйте в = Accept%, которые совпадают в парах.Группа с подсчитать все.Если есть <и = противоречия, то истина - та, с большим количеством. </p>

Отфильтровано, затем отсортировано по логике:

• Duke3d, Duke forever
• UT3
• Quake

Но на сортировку должен влиять подсчет голосов (байесовский тип).Таким образом, Duke3d выиграл бы.

Halo нельзя нигде разместить, потому что за него не проголосовали ...