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

Question

我在 Smith Set 上阅读过维基百科, Schwartz Set , Kosaraju's Algorithm , Tarjan's Algorithm , 和 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;
  }
}

对于 Ballots 的集合，每个单独的 Ballot 将包含一个数组 Votes，如下所示:

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

这对应于投票者选择 Alex>Sam>Chris，并且可能还有更多的候选人都与 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 .

首先你可以计算一个矩阵beats[i][j]等于True如果候选人i击败候选人j和 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]意味着有一条“跳动路径”i -> c1 -> c2 -> ... -> j这样 i节拍 c1 , c1节拍 c2等等直到j .

Schwartz 组件是其中所有对 i , j有双向运行的击败路径，并且没有其他候选人击败他们中的任何一个(请参阅维基百科关于属性的部分提到顶循环)。

基本上每个候选人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)

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