秘书问题的博弈论分析
一、秘书问题的提出
我们采用博弈论和概率的方法对秘书问题进行分析,首先总结秘书问题的大概脉络,我们先看秘书问题是如何问提问的,内容是什么,求解什么。
秘书问题(类似名称有相亲问题、止步问题、见好就收问题、苏丹的嫁妆问题、挑剔的求婚者问题等)内容是这样的:要聘请一名秘书,有n人来面试。每次面试一人,面试过后便要即时决定聘不聘他,如果当时决定不聘他,他便不会回来。面试时总能清楚了解求职者的适合程度,并能和之前的每个人作比较。问凭什么策略,才使选得到最适合担任秘书的人的机率最大?
二、秘书问题的解题策略
基本解决策略如下:对于某些整数r,其中1≤r<n。先面试首r人,都不聘请他们,在之后的n-r人中,如果任何一人比之前面试的人都更佳,便聘请他。r的最佳值应该是r≈n/e≈0.368n。其中e是自然对数的底。基于这个r值得到最佳选项(如例中的“秘书”)的成功率是1 / e (大约 36.8%)。
三、博弈论和概率原理
秘书问题的最优解是一个停止规则。在这个规则里,面试官会拒绝头 r - 1 个应聘者(令他们中的最佳人选为 应聘者 M),然后选出第一个比 M 好的应聘者。可见最优策略包含于这个系列的策略中。对于任意的截断值 r,最佳人选被选中的概率是:
求和符号内概率的计算是基于:如果应聘者 i 是(所有应聘者中的)最佳人选,他被选中当且仅当头 i - 1 个应聘者中的最佳人选处在头 r - 1 个被拒绝的应聘者中。令 n 趋近无穷大,把 x 表示为 r/n 的极限,令 t 为 i/n,dt 为 1/n,总和可以近似为如下积分:
令
P(x) 对 x 的导数为 0,解出 x,我们得到最优的 x 等于 1/e。从而,当 n 增大时,最优截断值趋近于 n/e 最佳人选被选中的概率为 1/e。
对于较小的 n 值, 最优的 r 也可以通过动态规划方法得到。下表给出了一些最优的 r 值:
n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
r |
1 |
1 |
2 |
2 |
3 |
3 |
3 |
4 |
4 |
P |
1.000 |
0.500 |
0.500 |
0.458 |
0.433 |
0.428 |
0.414 |
0.410 |
0.406 |
四、秘书问题的变化
此问题的变化包括:
(1)选择者可选多于一人;
(2)求职者的数目未知;
(3)求职者之间的关系可影响选择;
(4)被拒绝的求职者有一定机率能被叫回来;
(5)选择者满足于次好的人。
(本文大部分内容都整理自网络)推荐阅读
-
分析问题的框架:肯尼芬框架
-
问题解决思路的贪婪算法、回溯算法和动态编程分析 - 决策方法
-
Win11 分辨率太高字体很小的解决方法?Win11 分辨率太高字体很小的问题分析
-
正负偏差变量 即 d2+、d2- 分别表示决策值中超出和未达到目标值的部分。而 di+、di- 均大于 0 刚性约束和目标约束(柔性目标约束有偏差) 在多目标规划中,>=/<= 在刚性约束中保持不变。当需要将约束条件转换为柔性约束条件时,需要将 >=/<= 更改为 =(因为已经有 d2+、d2- 用来表示正负偏差),并附加上 (+dii-di+) 注意这里是 +di、-di+!之所以是 +di,-di+,是因为需要将目标还原为最接近的原始刚性约束条件 优先级因素和权重因素 对多个目标进行优先排序和优先排序 目标规划的目标函数 是所有偏差变量的加权和。值得注意的是,这个加权和都取最小值。而 di+ 和 dii- 并不一定要出现在每个不同的需求层次中。具体分析需要具体问题具体分析 下面是一个例子: 题目中说设备 B 既要求充分利用,又要求尽可能不加班,那么列出的时间计量表达式即为:min z = P3 (d3- + d3 +) 使用 + 而不是 -d3 + 的原因是:正负偏差不可能同时存在,必须有 di+di=0 (因为判定值不可能同时大于目标值和小于目标值),而前面是 min,所以只要取 + 并让 di+ 和 dii- 都为正值即可。因此,得出以下规则: 最后,给出示例和相应的解法: 问题:某企业生产 A 和 B 两种产品,需要使用 A、B、C 三种设备。下表显示了与工时和设备使用限制有关的产品利润率。问该企业应如何组织生产以实现下列目标? (1) 力争利润目标不低于 1 500 美元; (2) 考虑到市场需求,A、B 两种产品的生产比例应尽量保持在 1:2; (3)设备 A 是贵重设备,严禁超时使用; (4)设备 C 可以适当加班,但要控制;设备 B 要求充分利用,但尽量不加班。 从重要性来看,设备 B 的重要性是设备 C 的三倍。 建立相应的目标规划模型并求解。 解:设企业生产 A、B 两种产品的件数分别为 x1、x2,并建立相应的目标计划模型: 以下为顺序求解法,利用 LINGO 求解: 1 级目标: 模型。 设置。 variable/1..2/:x;! s_con_num/1...4/:g,dplus,dminus;!所需软约束数量(g=dplus=dminus 数量)及相关参数; s_con(s_con_num);! s_con(s_con_num,variable):c;!软约束系数; 结束集 数据。 g=1500 0 16 15. c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(1);!第一个目标函数;!对应于 min=z 的第一小部分;! 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); !使用设置完成的数据构建软约束表达式; ! !软约束表达式 @for(variable:@gin(x)); !将变量约束为整数; ! 结束 此时,第一级目标的最优值为 0,第一级偏差为 0: 第二级目标: !求 dminus(1)=0,然后求解第二级目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=dminus(2)+dplus(2);!第二个目标函数 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标结果 @for(variable:@gin(x)); ! 结束 此时,第二个目标的最优值为 0,偏差为 0: 第三目标 !求 dminus(2)=0,然后求解第三个目标。 模型。 设置。 变量/1..2/:x;!设置:变量/1..2/:x; ! s_con_num/1...4/:g,dplus,dminus;!软约束数量及相关参数; s_con(s_con_num(s_con_num));! s_con(s_con_num,variable):c;! 软约束系数; s_con(s_con_num,variable):c;! 结束集 数据。 g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; 结束数据 min=3*dminus(3)+3*dplus(3)+dminus(4);!第三个目标函数。 2*x(1)+2*x(2)<12;!硬约束 @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i)=g(i)); ! 软约束表达式;! dminus(1)=0; !第一个目标约束条件; ! dminus(2)+dplus(2)=0; !第二个目标约束条件 @for(variable:@gin(x));! 结束 最终结果为 x1=2,x2=4,dplus(1)=100,最优利润为
-
初学者的 JavaScript(揭开 javascript 的神秘面纱)》,2024 年最新网络前端面试问题分析
-
2024 五杯数学建模 一个问题的思路分析
-
Zabbix 监控项目无法获取数据?解决问题的 3 个步骤,11 种错误报告场景分析
-
纯干货分享 | 研发效能提升——敏捷需求篇-而敏捷需求是提升效能的方式中不可或缺的模块之一。 云智慧的敏捷教练——Iris Xu近期在公司做了一场分享,主题为「敏捷需求挖掘和组织方法,交付更高业务价值的产品」。Iris具有丰富的团队敏捷转型实施经验,完成了企业多个团队从传统模式到敏捷转型的落地和实施,积淀了很多的经验。 这次分享主要包含以下2个部分: 第一部分是用户影响地图 第二部分是事件驱动的业务分析Event driven business analysis(以下简称EDBA) 用户影响地图,是一种从业务目标到产品需求映射的需求挖掘和组织的方法。 在软件开发过程中可能会遇到一些问题,比如大家使用不同的业务语言、技术语言,造成角色间的沟通阻碍,还会导致一些问题,比如需求误解、需求传递错误等;这会直接导致产品的功能需求和要实现的业务目标不是映射关系。 但在交付期间,研发人员必须要将这些需求实现交付,他们实则并不清楚这些功能需求产生的原因是什么、要解决客户的哪些痛点。研发人员往往只是拿到了解决方案,需要把它实现,但没有和业务侧一起去思考解决方案是否正确,能否真正的帮助客户解决问题。而用户影响地图通常是能够连接业务目标和产品功能的一种手段。 我们在每次迭代里加入的假设,也就是功能需求。首先把它先实现,再逐步去验证我们每一个小目标是否已经实现,再看下一个目标要是什么。那影响地图就是在这个过程中帮我们不断地去梳理目标和功能之间的关系。 我们在软件开发中可能存在的一些问题 针对这些问题,我们如何避免?先简单介绍做敏捷转型的常规思路: 先做团队级的敏捷,首先把产品、开发、测试人员,还有一些更后端的人员比如交互运维的同学放在一起,组成一个特训团队做交付。这个团队要包含交付过程中所涉及的所有角色。 接着业务敏捷要打通整个业务环节和研发侧的一个交付。上图中可以看到在敏捷中需求是分层管理的,第一层是业务需求,在这个层级是以用户目标和业务目标作为输入进行规划,同时需要去考虑客户的诉求。业务人员通过获取到的业务需求,进一步的和团队一起将其分解为产品需求。所以业务需求其实是我们真正去发布和运营的单元,它可以被独立发布到我们的生产环境上。我们的产品需求其实就是产品的具体功能,它是我们集成和测试的对象,也就是我们最终去部署到系统上的一个基本单元。产品需求再到了我们的开发团队,映射到迭代计划会上要把它分解为相应的技术任务,包括我们平时所说的比如一些前端的开发、后端的开发、测试都是相应的技术任务。所以业务敏捷要达到的目标是需要去持续顺畅高质量的交付业务价值。 将这几个点串起来,形成金字塔结构。最上层我们会把业务目标放在整个金字塔的塔尖。这个业务目标是通过用户的目标以及北极星指标确立的。确认业务目标后再去梳理相应的业务流程,最后生产。另外产品需求包含了操作流程和业务规则,具需求交付时间、工程时间以及我们的一些质量标准的要求。 谈到用户影响的地图,在敏捷江湖上其实有一个传说,大家都有一个说法叫做敏捷需求的“任督二脉”。用户影响地图其实就是任脉,在黑客马拉松上用过的用户故事地图其实叫督脉。所以说用户影响地图是在用户故事地图之前,先帮我们去梳理出我们要做哪些东西。当我们真正识别出我们要实现的业务活动之后,用户故事地图才去梳理我们整个的业务工作流,以及每个工作流节点下所要包含的具体功能和用户故事。所以说用户影响地图需要解决的问题,我们包括以下这些: 首先是范围蔓延,我们在整张地图上,功能和对应的业务目标是要去有一个映射的。这就避免了一些在我们比如有很多干系人参与的会议上,那大家都有不同想法些立场,会提出很多需求(正确以及错误的需求)。这个时候我们会依据目标去看这些需求是否真的是会影响我们的目标。 这里提到的错误需求,比如是利益相关的人提出的、客户认为产品应该有的、某个产品经理需求分析师认为可以有的....但是这些功能在用户影响地图中匹配不到对应目标的话,就需要降低优先级或弃掉。另外,通常我们去制定解决方案的时候,会考虑较完美的实现,导致解决方案括很多的功能。这个时候关键目标至关重要,会帮助我们梳理筛选、确定优先级。 看一下用户影响到地图概貌 总共分为一个三层的结构: 第一层why,你的业务目标哪个是最重要的,为什么?涉及到的角色有哪些? 第二层how ,怎样产生影响?影响用户角色什么样的行为? (不需要去列出所有的影响,基于业务目标) 第三层what,最关键的是在梳理需求时不需一次把所有细节想全,这通常团队中经常遇到的问题。 我们用这个例子来看一下 这是一个客服中心的影响地图,业务目标是 3个月内不增加客服人数的前提下能支持1.5倍的用户数。此业务目标设定是符合 smart 原则的,specific非常的具体,miserable 是可以衡量的,action reoriented是面向活动的, real list 也是很实际的。 量化的目标会指引我们接下来的行动,梳理一个业务目标,尽量去量化,比如 :我们通过打造一条什么样的流水线,能够提高整个部署的效率,时间是原来的 1/2 。这样才是一个能量化的有意义的目标。 回到这幅图, how 层级识别出来的内容,客服角色:想要对它施加的影响,把客户引导到论坛上,帮助客户更容易的跟踪问题,更快速的去定位问题。初级用户:方论坛上找到问题。高级用户:在论坛上回答问题。通过我们这些用户角色,进行活动,完成在不增加客户客服人数的前提下支持更多的用户数量。 最后一个层级,才是我们日常接触比较多的真正的功能的特性和需求,比如引导到客户到论坛上,其实这个产品就需要有一个常见问题的论坛的链接。这个层次需要我们团队进一步地在交付,在每个迭代之前做进一步的梳理,细化成相应的用户故事。 这个是云智慧团队中,自己做的影响地图的范例,可以看下整个的层级结构。序号表示优先级。 那我们用户影响地图可以总结为:
-
组合数问题(组合数学 + 二维前缀和)--分析:有多组数据,肯定要考虑预处理,然后(O(1) answer\).\n,m<;=2000\)可以考虑线性递归的组合数\(C[i][j]=C[i-1][j]+C[i-1][j-1]\),因为只有k的倍数才会对答案有贡献、所以可以直接对 k 模进行递归,然后进行二维前缀和 \(f[i][j]=f[i-1][j]+f[i][j -1]-f[i-1][j-1]\) 计算时只需看是否为零即可。
-
使用核心转储分析查找程序崩溃问题的 golang