Место оптимальной встречи на основе ранга

Question

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

Предположим, у меня есть 10 человек и 5 возможных мест для встречи. Как найти оптимальное место встречи? Я знаю предпочтения людей, например, Person 1 будет оценивать места, идущие от лучшего к худшему, как: Местоположение D, местоположение A, местоположение C; Лицо 2 - Местонахождение B, Местонахождение A, Местоположение D, Место C; и так далее. Обратите внимание, что рейтинги могут не включать все 5 местоположений, другими словами - как я буду иметь дело с отсутствующими рейтингами?

Как мне закодировать это в Python, чтобы найти лучшее решение? Или, может быть, есть онлайн-сервис, который я могу использовать, чтобы понять это?

Спасибо!

Answer 1

Если они только ранжированы и не взвешены, это пример Condorcet vote. Псевдокод для метода Шульце выглядит here.

Сложение

Просто сделайте поиск на Google для «Python Кондорсе» - многие результаты появляются с бесплатным кодом.

Сложение 2

Первые перечисленные имена проектов на GitHub:

bradbeattie/python-vote-core

radii/condorcet

И Кодекс Обзор StackExchange: https://codereview.stackexchange.com/questions/42359/condorcet-voting-method-in-oop-python

Соответствующая цитата из вышеупомянутой Википедии ссылка:

Единственный трудный шаг в реализации метода Шульце - вычисление самых сильных прочностей. Однако это хорошо известная проблема в теории графов, которую иногда называют самой широкой проблемой пути. Таким образом, простой способ вычислить сильные стороны - это вариант алгоритма Флойда-Варшалла. Следующий псевдокод иллюстрирует алгоритм.

# Input: d[i,j], the number of voters who prefer candidate i to candidate j. 
# Output: p[i,j], the strength of the strongest path from candidate i to candidate j. 

for i from 1 to C 
    for j from 1 to C 
     if (i ≠ j) then 
     if (d[i,j] > d[j,i]) then 
      p[i,j] := d[i,j] 
     else 
      p[i,j] := 0 

for i from 1 to C 
    for j from 1 to C 
     if (i ≠ j) then 
     for k from 1 to C 
      if (i ≠ k and j ≠ k) then 
       p[j,k] := max (p[j,k], min (p[j,i], p[i,k])) 

Этот алгоритм является эффективным, и время работы, пропорциональное C3, где С представляет собой число кандидатов. (Это не учитывает время выполнения вычислений значений, которые, если они реализованы самым простым способом, занимают время, пропорциональное C2, умноженное на количество избирателей.)