基于排名的最佳会议地点

Question

这听起来像是一个很常见的问题。也许甚至有一个网站可以为我解决这个问题？如果没有，我确定一定有一些 python 库和几行代码可以提供帮助。

假设我有 10 个人和 5 个可能的会议地点。我如何找到最佳的会议地点？我知道人们的偏好，例如，第 1 个人会将位置从最好到最差排列为：位置 D、位置 A、位置 C；人 2 - 位置 B、位置 A、位置 D、位置 C；等等。请注意，排名可能不包括所有 5 个位置，换句话说 - 我将如何处理缺失的排名？

我如何在 Python 中对此进行编码以找到最佳解决方案？或者我可以使用在线服务来解决这个问题？

谢谢！

Answer 1

如果只排名不加权，这是一个Condorcet vote. Pseudocode for the Schulze method looks to be here的例子。

添加

只需在 Google 上搜索 "Python Condorcet" - 许多结果都带有免费代码。

附加 2

首先在 github 上列出的项目名称：

bradbeattie/python-vote-core

radii/condorcet

以及 StackExchange 代码审查： https://codereview.stackexchange.com/questions/42359/condorcet-voting-method-in-oop-python

上述维基百科的相关引文link:

The only difficult step in implementing the Schulze method is computing the strongest path strengths. However, this is a well-known problem in graph theory sometimes called the widest path problem. One simple way to compute the strengths therefore is a variant of the Floyd–Warshall algorithm. The following pseudocode illustrates the algorithm.

# 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] ) )

This algorithm is efficient, and has running time proportional to C3 where C is the number of candidates. (This does not account for the running time of computing the d[,] values, which if implemented in the most straightforward way, takes time proportional to C2 times the number of voters.)

基于排名的最佳会议地点

Optimal meeting location based on rank

python

algorithm