【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 投票机制可以总结为:


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


下篇继续讲实现~

目录
相关文章
|
机器学习/深度学习 数据采集 SQL
一文读懂大数据实时计算(一)
本文分为四个章节介绍实时计算,第一节介绍实时计算出现的原因及概念;第二节介绍实时计算的应用场景;第三节介绍实时计算常见的架构;第四节是实时数仓解决方案。
3211 0
一文读懂大数据实时计算(一)
|
Ubuntu Linux
憨态可掬的牛——Linux上的Cowsay命令体验
Cowsay是一个有趣的命令行工具,在Linux系统中备受欢迎。它能让一个笑脸的小牛说出你输入的文本,为你的终端带来一些趣味和幽默。本文将介绍如何在Linux上安装、运行和使用Cowsay,以及一些有趣的用法和定制技巧。
1172 0
|
Java 开发者 Python
Python中的self是什么你知道嘛?
在Python类中规定,函数的第一个参数是实例对象本身,并且约定俗成,把其名字写为self。其作用相当于java中的this,表示当前类的对象,可以调用当前类中的属性和方法。
|
2月前
|
人工智能 Linux API
零成本无限用免费大模型保姆级教程!OpenClaw极速部署(阿里云/Win11/Mac/Linux)+FreeRide Skill+FAQ
2026年,AI工具的普及让更多人感受到智能协作的便利,但“Token焦虑”始终困扰着用户——MiniMax M2.5、Kimi K2.5、智谱GLM-5等强模型API费用高昂,简单的日常对话就能快速耗尽包月额度;OpenRouter免费模型池虽香,却存在随机抽盲盒、高峰期限速卡顿等问题,严重影响使用体验。尤其是OpenClaw(昵称“小龙虾”)用户,作为开源AI代理框架的深度使用者,频繁切换模型、等待限速解除的操作,大幅降低了自动化协作效率。
5115 5
|
4月前
|
Rust 安全 Docker
使用 uv 一键创建并激活 Python 虚拟环境(附完整脚本)
本文介绍基于 `uv` 的自动化脚本 `activate_env.sh`,一键完成安装 uv、创建并激活虚拟环境、安装依赖及环境信息输出,提升 Python 项目初始化效率,适用于个人开发、团队协作与 CI/CD 场景。
|
运维 数据可视化 网络协议
Docker可视化工具Portainer的安装和使用
Docker可视化工具Portainer的安装和使用
17671 1
Docker可视化工具Portainer的安装和使用
|
10月前
|
缓存 固态存储 Windows
如何让内存发挥到最大效能?全面优化指南,提升电脑运行体验
电脑内存使用不合理会导致卡顿,本文教你如何优化内存性能。检查内存容量与主板支持上限,考虑升级或调整配置;关闭后台程序、管理浏览器标签、结束异常进程以释放内存;设置虚拟内存、调整视觉效果、定期重启提升效率;必要时增加内存条、选择高频内存、更换固态硬盘。避免盲目清理内存和依赖大内存忽视其他硬件瓶颈。只需合理设置,无需额外花钱,就能显著提升电脑速度。
|
9月前
|
Ubuntu Linux 数据安全/隐私保护
Ubuntu 安装教程(U 盘安装 Ubuntu 详细教程)
完成上述步骤后,Ubuntu将开始安装在你的电脑上。安装完成后,重启电脑,并按提示移除U盘。电脑将自动从硬盘启动进入新装的Ubuntu系统。现在你可以开始探索Ubuntu带来的全新体验了!
|
存储 人工智能 Java
一文彻底搞定C语言中的二维数组
本文详细介绍了C语言中的多维数组,包括二维和三维数组的定义、初始化方式、内存布局及遍历方法。通过具体示例讲解了多种赋值技巧,并强调了数组在内存中按行存放的特点。希望这些内容能帮助你在编程路上不断成长!君志所向,一往无前!
1419 1
一文彻底搞定C语言中的二维数组
|
算法 安全 Unix
翁恺C语言程序设计网课笔记合集
学习自翁恺C语言程序设计网课。
2233 1
翁恺C语言程序设计网课笔记合集