【CS50x】 Tideman 题解（上）

前言

CS50x 是哈佛大学推出的一门知名公开课，本课程是一门计算机科学的导论课程，适合于对计算机科学感兴趣的任何人学习，不需要任何基础。通过学习本课程有助于对计算机科学的体系建立一个基本的概念，其学习内容如下：

Tideman

相比 Runoff 投票机制，Tideman 投票机制就完全解决了它仍然会产生平局的缺点。它的运行机制是这样的：

依然是这张图，谁将赢得这次选举？在 Plurality 中，第一选择得票，Charlie 将会以四票赢得这次选举，Bob 三票和 Alice 两票，但是 Alice 有理由争辩说，她才是选举的获胜者，因为9个人中有5个人比起 Charlie 更喜欢 Alice。

在这次选举中，Alice 就是所谓的 “Condorcet winner”，在候选人只有 Alice 和 Bob， 或者 Alice 和 Charlie 时，都是 Alice 获胜。Tideman 投票机制能够确保只有一位赢家。

一般来说，Tideman 方法通过构造一种有向图来工作，其中候选人 a->b 说明候选人a在对抗中胜出，上图的投票结果可以构造出这样一张图：

从图中我们可以轻松的看出选举的获胜者 —— Alice，因为没有任何箭头指向她，不过在一些其他情况中，可能不会有赢家产生，比如下图：

三个人互相胜出形成了一个死循环，为了处理这个问题，我们必须避免在添加边时创建循环，算法首先要基于胜利的强度（喜欢候选人多于对手的人越多）确定最重要的边，然后只要添加边时不会创建循环即可添加。

在上述投票中，我们首先确定 Alice->Bob 7:2，然后是 Charlie->Alice 6:3，最后一条边 Bob->Charlie 会创建一个循环所以我们跳过这个边，该图完成：

可以看到赢家为 Charlie，所以 Tideman 投票机制可以总结为：

• 创建偏好数组
• 基于胜利强度排序候选人对
• 从最强的对开始，按顺序检查并确定图中的边到有向图中（不能创建循环）

下篇继续讲实现~