寻找计算 Smith 和 Schwartz 集的伪代码

Question

我在 Smith Set, Schwartz Set, Kosaraju's Algorithm, Tarjan's Algorithm, and the path-based strongly component algorithms 上阅读过维基百科；但是，我对此类算法的经验……不足。维基百科还说您可以使用 Kosaraju 算法的版本来生成 Schwartz 集——并且这些算法可以计算 Smith 集。

维基百科也有一些 Tarjan 算法的伪代码，但其他的没有；而且它并不特定于这个相对敏感的应用程序。我也不是 100% 确定哪个是最简单的实现——哪个具有实现错误可能性最小的特点。

我想要一些更直接的伪代码来涵盖从这些算法之一计算 Smith 和 Schwartz 集，给定一组排名选票。当我有一个可以走的实际过程时，我发现更容易掌握概念。我会自己把它变成实际的代码。

考虑以下数据结构：

Type Ballot {
  Array Votes[] {
    Candidate Candidate; // We do this in C#
    int Rank;
  }
}

对于选票集合，每个单独的选票将包含一个数组 Votes，如下所示：

Ballot b.Votes[] =
  [ Vote(Alex.ID, 1),
    Vote(Chris.ID, 3),
    Vote(Sam.ID, 2) ];

这对应于选民投票 Alex>Sam>Chris，并且可能还有更多的候选人都与克里斯一样不受欢迎。

我假设第一步是计算个人选票并绘制胜利图表。例如：如果 100 个选民将 Alex 排在 Sam 之上（Alex = 1，Sam >= 2）并且 50 个选民将 Sam 排在 Alex 之上，则 Alex 将击败 Sam。因此我猜会有这样的数据结构：

Type GraphNode {
  Candidate Candidate;
  GraphNode Array Defeats[];
  GraphNode Array Ties[];
  GraphNode Array DefeatedBy[];
}

Alex 的 GraphNode 将在 Defeats[] 中有一个元素指向 Sam 的 GraphNode，反之亦然。

给定这些 GraphNode，我如何使用它来识别 Smith 和 Schwartz 集？

提前致谢。

Answer 1

我猜 python 已经足够接近伪代码了。

假设我们有 n 个候选人，编号从 0 到 n - 1。

首先，如果候选人 i 击败候选人 j，则您可以计算矩阵 beats[i][j] 等于 True，否则 False。

现在使用 Floyd-Warshall 算法计算矩阵的传递闭包：

for k in range(n):
    for i in range(n):
        for j in range(n):
            beats[i][j] = beats[i][j] or (beats[i][k] and beats[k][j])

之后矩阵的含义略有不同：beats[i][j]表示有一个"beating path" i -> c1 -> c2 -> ... -> j使得i击败c1，c1 击败 c2 依此类推直到 j.

Schwartz 组件是其中所有对 i、j 都具有击败路径运行的组件，并且没有其他候选者击败它们中的任何一个（参见维基百科关于属性的部分提到了 top cycle).

基本上每个候选人 i 尝试围绕它构建一个组件，如下所示：

schwartz_components = []

for i in range(n):
    schwartz_component = {i}
    is_schwartz = True
    for j in range(n):
        if beats[j][i]:
            if beats[i][j]:
                schwartz_component.add(j)
            else:
                is_schwartz = False
    if is_schwartz:
         schwartz_components.append(schwartz_component)

schwartz_set = set.union(*schwartz_components)
print(schwartz_set)

对于 Smith 集合，它会有点不同，您需要从 cannot_beat[i][j] = not beats[i][j] 开始，在其上使用 Floyd-Warshall，然后通过添加所有围绕每个 i 构建集合通过 cannot_beat 关系找到它的候选人。

我猜它会是这样的（在 Floyd-Warshall 步骤之后）：

smith_candidates = []

for i in range(n):
    smith_candidate = {i}
    for j in range(n):
        if cannot_beat[i][j]:
            smith_candidate.add(j)
    smith_candidates.append(smith_candidate)

# Take the smallest candidate
smith_set = min(smith_candidates, key=len)

可能某处存在错误，但大致就是这个想法。

寻找计算 Smith 和 Schwartz 集的伪代码

Seeking Pseudo-code for Calculating the Smith and Schwartz Set

algorithm

pseudocode

voting