Создание полного или частичного порядка из противоречивого отношения
Представьте, что я хочу построить общий порядок из набора элементов, $E$, но функция сравнения дает недетерминированные результаты. Я создаю список пар элементов (e, e) путем многократного применения функции сравнения, так что каждый элемент в наборе представлен хотя бы один раз.
Как я могу использовать эти данные для создания общего заказа? Какой класс алгоритмов здесь можно применить?
Для большей наглядности приведу конкретный пример.
Какие самые лучшие начинки для пиццы?
Мой набор элементов $E$ включает некоторые популярные начинки для пиццы: пепперони, сыр, грибы, ананас, болгарский перец, оливки.
Затем для каждого из моих друзей я выбираю подмножества начинок произвольного размера и прошу друга расставить их в порядке от лучшего к худшему. Мои друзья покорно отвечают и создают входные данные для моего алгоритма:
- сыр, пепперони, оливки
- сыр, ананас, грибы, оливки
- болгарский перец, грибы, оливки
- пепперони, сыр, оливки
- сыр, болгарский перец
Здесь действительно есть нечеткий порядок (все согласны, что оливки худшие), но мои друзья не пришли к единому мнению о том, какая начинка для пиццы лучше: сыр или пепперони. Учитывая, где элементы встречаются во входных данных и как часто они встречаются, я, вероятно, создал бы такой заказ.
- сыр> пепперони> сладкий перец> ананас> грибы> оливковое
Я просто не уверен, как это формализовать и заставить работать с гораздо большими входами.
Я думаю, что решение, вероятно, включает в себя графы и взвешенные ребра, но я недостаточно знаком с алгоритмами графов, чтобы понять, является ли это именованной областью исследования. Я уже сталкивался с «топологической сортировкой», но она работает только для ориентированных ациклических графов, и меня особенно интересуют входные данные, которые не могут создавать DAG.
Я также заметил, что эта проблема похожа на голосование за избранных представителей. Действительно ли это тот же класс проблем?
Ответы
Трудно сказать без большего контекста и большего моделирования. Это потребует некоторых предположений о том, как результаты функции сравнения соотносятся с (скрытым) желаемым общим порядком.
Возможно, вам понадобится модель Брэдли-Терри-Люса . Если так, то существует множество стандартных алгоритмов. Смотрите такжеhttps://cs.stackexchange.com/a/85204/755.
Возможно, вам понадобится какая-то система ранжирования, например Эло и т. Д.
Возможно, вам понадобится система рейтингового голосования , такая как IRV, метод Кондорсе, подсчет Борда или любая другая. Все они имеют различные недостатки и компромиссы. Существует доказательство того, что ни одна система не будет обладать всеми необходимыми нам свойствами - см., Например, теорему Эрроу и проблему нетранзитивности (что даже если каждое из индивидуальных предпочтений вашего друга является транзитивным, т. Е. Полным порядком, то нет гарантии, что существует глобальный общий порядок, который согласуется со всеми из них).