【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上的Cowsay命令体验
Cowsay是一个有趣的命令行工具,在Linux系统中备受欢迎。它能让一个笑脸的小牛说出你输入的文本,为你的终端带来一些趣味和幽默。本文将介绍如何在Linux上安装、运行和使用Cowsay,以及一些有趣的用法和定制技巧。
992 0
|
5月前
|
缓存 固态存储 Windows
如何让内存发挥到最大效能?全面优化指南,提升电脑运行体验
电脑内存使用不合理会导致卡顿,本文教你如何优化内存性能。检查内存容量与主板支持上限,考虑升级或调整配置;关闭后台程序、管理浏览器标签、结束异常进程以释放内存;设置虚拟内存、调整视觉效果、定期重启提升效率;必要时增加内存条、选择高频内存、更换固态硬盘。避免盲目清理内存和依赖大内存忽视其他硬件瓶颈。只需合理设置,无需额外花钱,就能显著提升电脑速度。
|
移动开发 C语言
C语言:&&和&、||和|有什么区别
在C语言中,&&和||是逻辑运算符,分别表示逻辑与(AND)和逻辑或(OR),它们用于连接两个布尔表达式,只有当两边都为真时&&返回真,||在至少一边为真时返回真;&和|是位运算符,对应地进行位级的与、或操作,它们对操作数的二进制位进行逐位处理。&&和||具有短路特性,而&和|没有。
13839 1
|
网络协议 安全 网络安全
揭秘互联网的隐形斗篷:你的DNS数据真的安全吗?
【8月更文挑战第27天】在互联网中,每个网站通过IP地址定位,但记忆这些数字困难且存在安全风险。因此,域名系统(DNS)诞生,实现域名与IP之间的转换。然而,未加密的DNS请求易受中间人攻击,导致隐私泄露或恶意软件植入。为解决此问题,DNS-over-HTTPS(DoH)和DNS-over-TLS(DoT)协议应运而生,它们通过对DNS查询进行加密确保数据传输安全。本文将介绍这两种协议,并通过示例展示如何配置支持DoT的DNS服务器,包括安装dnscrypt-proxy、编辑配置文件及重启服务等步骤。
816 0
|
监控 搜索推荐 数据挖掘
Flink流处理与批处理大揭秘:实时与离线,一文让你彻底解锁!
【8月更文挑战第24天】Apache Flink 是一款开源框架,擅长流处理与批处理。流处理专攻实时数据流,支持无限数据流及事件驱动应用,实现数据的连续输入与实时处理。批处理则聚焦于静态数据集,进行一次性处理。两者差异体现在处理方式与应用场景:流处理适合实时性要求高的场景(例如实时监控),而批处理更适用于离线数据分析任务(如数据挖掘)。通过提供的示例代码,读者可以直观理解两种模式的不同之处及其实际应用。
1318 0
|
JSON 算法 数据可视化
Open3d-Point cloud (点云)
Open3d-Point cloud (点云)
1369 6
|
监控 程序员 开发工具
如何规范Git提交-参考阿里云开发者社区
这篇文章分享了如何规范Git提交,介绍了commit message的格式规范,并通过webhook监控机制来确保代码提交的规范性,从而提高研发效率和代码维护质量。
|
分布式计算 DataWorks NoSQL
MaxCompute产品使用合集之如何操作和管理节点
MaxCompute作为一款全面的大数据处理平台,广泛应用于各类大数据分析、数据挖掘、BI及机器学习场景。掌握其核心功能、熟练操作流程、遵循最佳实践,可以帮助用户高效、安全地管理和利用海量数据。以下是一个关于MaxCompute产品使用的合集,涵盖了其核心功能、应用场景、操作流程以及最佳实践等内容。
302 0
|
存储 算法 搜索推荐
【算法】七大经典排序(插入,选择,冒泡,希尔,堆,快速,归并)(含可视化算法动图,清晰易懂,零基础入门)
【算法】七大经典排序(插入,选择,冒泡,希尔,堆,快速,归并)(含可视化算法动图,清晰易懂,零基础入门)
458 1
【CS50x】 Tideman 题解(下)
【CS50x】 Tideman 题解(下)
1230 0
【CS50x】 Tideman 题解(下)