热门标签 | HotTags
当前位置:  开发笔记 > 人工智能 > 正文

分蛋糕是极其复杂的

分蛋糕是极其复杂的--Linux发行版技术-Debian信息,下面是详情阅读。
味美的蛋糕会令你馋涎欲滴,但分蛋糕却会令你绞尽脑汁。数学上有一个著名的分蛋糕问题:一块蛋糕有N个人分,每一个人对自己分到的那块都持有不同的观点,怎么分才能让每一个人都满意(或叫Envy-free)?1980 年费城附近Swarthmore学院的Walter Stromquist证明存在一个Envy-free解。换句话说,一块蛋糕切N-1次分给N个人,让每个人都满意是可能的。N=2和N=3的情况比较简单(其实N=3已经相当繁琐了),1992年Steven Brams和Alan Taylor证明了N>3的情况,但算法过于复杂,他们为此特地写了一本书来剖析如何公平的分蛋糕。现在香港城市大学的Xiaotie Deng和同事提出了一种更高效分蛋糕算法(预印本),算法的计算可在多项式时间内完成。但唯一令人遗憾的问题是算法适用范围是N=3,另外的一些特例只能得到近似的Envy-free解。以下引用流?日?: 1. N=2:两个人分蛋糕时,一般都认为直接分一半不就得了?确实如此,但是如果两人,譬如是两位小朋友,都在意有没有公平分到水果,那这样的话谁都会想要先选,并且尽量得到越多水果越好。假如切的和先选的都是同一位,则另一位一定觉得不公平。所以最好的解决方法是“一个人切蛋糕,另一人先选”,这样第一个人就尽量不会太小心眼,而第二个人的选择也不会占到什么便宜。

2. N=3:当甲乙丙三个人要分一块蛋糕时,先将状况简化一下,蛋糕是圆形,而且每个人在意的只有蛋糕大小,对装饰不考虑。那么可能的分法有两种。 a.第一种分法,假定让甲执刀,从一条起点的半径绕着蛋糕转,剩下的乙和丙观察,如果其中有一个人(例如丙)觉得已经到1/3时喊停,让甲切下蛋糕当作丙分得的那份。剩下来的状况就和两人分一样了。这种分法也引出一另个情境,就是假定三人分蛋糕,乙和丙没有订定契约或者暗中勾结,让刀子超过1/3还没停。情况是假定乙和丙勾心斗角,有各自的理性抉择,同时每个人都会嫉妒别人分到比自己多.....
推荐阅读
  • 深入解析JVM垃圾收集器
    本文基于《深入理解Java虚拟机:JVM高级特性与最佳实践》第二版,详细探讨了JVM中不同类型的垃圾收集器及其工作原理。通过介绍各种垃圾收集器的特性和应用场景,帮助读者更好地理解和优化JVM内存管理。 ... [详细]
  • 使用Numpy实现无外部库依赖的双线性插值图像缩放
    本文介绍如何仅使用Numpy库,通过双线性插值方法实现图像的高效缩放,避免了对OpenCV等图像处理库的依赖。文中详细解释了算法原理,并提供了完整的代码示例。 ... [详细]
  • 本文将介绍如何使用 Go 语言编写和运行一个简单的“Hello, World!”程序。内容涵盖开发环境配置、代码结构解析及执行步骤。 ... [详细]
  • 线性Kalman滤波器在多自由度车辆悬架主动控制中的应用研究
    本文探讨了线性Kalman滤波器(LKF)在不同自由度(2、4、7)的车辆悬架系统中进行主动控制的应用。通过详细的仿真分析,展示了LKF在提升悬架性能方面的潜力,并总结了调参过程中的关键要点。 ... [详细]
  • 本文探讨了Hive中内部表和外部表的区别及其在HDFS上的路径映射,详细解释了两者的创建、加载及删除操作,并提供了查看表详细信息的方法。通过对比这两种表类型,帮助读者理解如何更好地管理和保护数据。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现,详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]
  • 本文详细探讨了Java中的24种设计模式及其应用,并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类,帮助开发者更好地理解和应用这些模式,提升代码质量和可维护性。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 探讨一个显示数字的故障计算器,它支持两种操作:将当前数字乘以2或减去1。本文将详细介绍如何用最少的操作次数将初始值X转换为目标值Y。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 本文探讨如何设计一个安全的加密和验证算法,确保生成的密码具有高随机性和低重复率,并提供相应的验证机制。 ... [详细]
author-avatar
一大书虫
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有