【CS50x】 Tideman 题解(上)

简介: 【CS50x】 Tideman 题解(上)

前言


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


image.png


Tideman


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


image.png


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


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


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


image.png



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


image.png


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


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


image.png


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


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


下篇继续讲实现~

目录
相关文章
|
Ubuntu Linux
Linux Ubuntu 20.04 LTS 解决无法输入中文 输入法问题
Linux Ubuntu 20.04 LTS 解决无法输入中文 输入法问题
4783 0
|
存储 人工智能 算法
详细设计工具之盒图(N-S图)
详细设计工具之盒图(N-S图)
2259 0
详细设计工具之盒图(N-S图)
|
2月前
|
缓存 固态存储 Windows
如何让内存发挥到最大效能?全面优化指南,提升电脑运行体验
电脑内存使用不合理会导致卡顿,本文教你如何优化内存性能。检查内存容量与主板支持上限,考虑升级或调整配置;关闭后台程序、管理浏览器标签、结束异常进程以释放内存;设置虚拟内存、调整视觉效果、定期重启提升效率;必要时增加内存条、选择高频内存、更换固态硬盘。避免盲目清理内存和依赖大内存忽视其他硬件瓶颈。只需合理设置,无需额外花钱,就能显著提升电脑速度。
|
Ubuntu Linux
憨态可掬的牛——Linux上的Cowsay命令体验
Cowsay是一个有趣的命令行工具,在Linux系统中备受欢迎。它能让一个笑脸的小牛说出你输入的文本,为你的终端带来一些趣味和幽默。本文将介绍如何在Linux上安装、运行和使用Cowsay,以及一些有趣的用法和定制技巧。
919 0
|
Dart 测试技术 UED
Dart 和 Flutter 错误处理指南 | 最佳实践全解析
深入探索 Dart 和 Flutter 中的错误处理技术,从编译时错误到运行时异常,带你学习如何优雅地处理应用程序中的各种意外情况。了解最佳实践,让你的应用程序稳如磐石,用户体验持续优化!
294 5
Dart 和 Flutter 错误处理指南 | 最佳实践全解析
|
Java 容器
JavaFX之Stage
JavaFX之Stage
153 0
|
存储 算法 搜索推荐
【算法】七大经典排序(插入,选择,冒泡,希尔,堆,快速,归并)(含可视化算法动图,清晰易懂,零基础入门)
【算法】七大经典排序(插入,选择,冒泡,希尔,堆,快速,归并)(含可视化算法动图,清晰易懂,零基础入门)
411 1
【CS50x】 Tideman 题解(下)
【CS50x】 Tideman 题解(下)
1131 0
【CS50x】 Tideman 题解(下)
|
程序员 编译器 C语言
【C++ 基本类型 bool 】深入探索C++中的布尔类型Boolean(一)
【C++ 基本类型 bool 】深入探索C++中的布尔类型Boolean
1313 0
|
机器学习/深度学习 PyTorch 区块链
深度学习原理篇 第十章:Pix2Seq
简要介绍pix2seq的原理和代码实现。
660 1