秘书问题最优解（版）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“秘书关系协调全解”。
[摘要]经典秘书问题是最优停止理论中的一个著名例子, 属于一类序贯观察选择问题。其报酬函数仅与观察项的秩相关, 而与观察项的实际值无关。现在一定假设条件下, 将经典秘书问题推广, 建立一个更有实际意义的模型。采用动态规划的方法得到该类模型的选择策略, 为实际决策问题提供一种可供参考的方法。秘书问题是一类序贯观察与选择问题, 描述了一种动态的信息搜索与决策过程。
[关键词]秘书问题；简易公式；最小概率
[前言]已有解决秘书问题的方法,主要特征是以取样选项中的最大值作为标杆, 其优点是能保证赢的概率最大, 其不足是很少考虑决策者的有限理性与启发式偏见。提出了基于次大值标杆策略的设想, 通过理论求解以及仿真实验的方法研究了该策略的特征与规律。结果发现: 赢的概率随着标杆由最大值向次大值、第三大值等的变化而逐渐降低, 且最优截止阀值也不断后移。
一、假设与最优停止规则[1]：
假设下列条件成立（只要左方构成条件的事件的概率大于零）
条件B)的直观意义是：如果已知第n个到达的姑娘的相对名次, 则在此时刻以前的信息下引理：若若（1）式成立则最优停止规则是：其中Sn可以归纳地计算出来： , 对于预测她的绝对名次及拒聘与否, 不起任何作用。根据如
（1）则
这里约定，对空的指标集求和为零。所以最优停止规则是：
二、秘书问题的两个简单公式[2]：
我们知道秘书问题中有两个简易的计算公式：它是对N 为有限情形的秘书问题给出两个简易计算公式。
情形1：设经理放过前K 个申请者不予考虑, 从第K + 1 个开始选择比前面都好的那位(如果有的话), 记A k= { 放过前K 位结果选到1 号}
因此, 对于N 个申请者的情形,，使选到最差的那位概率最小。
情形2：对于N 个申请者由于经理每次招见一批人, 他可以在同一批中选择最好的, 如果最后一批的人数大于1, 经理不可能招聘到1 号申请者(最差的那位), 因此我们只考虑最后一批人数为1 的情形。
设这N 个人随机地按d 批进见经理, 各批的人数分别为n1, n2, ⋯, nd , nd =，最小.即经理应放掉第1 位, 才能1,，记。假设经理放过前K 批不予考虑, 从第K + 1 批开始选择比前面各批都好的那位(如果有的话), A k= { 放过前K 批最后结果选到1 号} , 则有
公式2 在上述条件下由此可计算的最优值。
[3]。
三、次大值标杆策略的仿真实验
解决秘书问题的关键, 并非决定去选择哪一个选项, 而是决定何时停止取样观察选项, 即何时停止搜索决策信息。但近些年研究发现, 相比较最优解策略, 人们往往停止搜索得太早或者搜索量太少[ 4]。这意味着决策者往往并没有遵循最优解策略去决策。下面我们做一个仿真实验来解决秘书问题的满意解。
实验内容是截止阀值与标杆交叉组合的截止阀法则。根据最优解策略的阀值37% 以及现实生活中的经验值, 我们测试了7个截止阀值r与2个标杆m 的策略组合。它们分别是: 截止阀值为选项集的10%、1 /
3、37%、50%、0618、2 /
3、90%;标杆为取样选项集中的最大值(m = 1)与次大值(m = 2)。这样, 本研究一共实验了14(7 x 2)个组合策略。
首先, 与已有研究[4]类似，我们用数字的大小表示选项的优劣程度, 数字越大意味着选项越优, 否则越差。其次, 采用序数集的随机排列来模拟选项被随机会见的情境。设选项集n= 100, 将1、2、……、100共一百个序数随机置乱作为测试集。在不同的截止阀值下, 分别采用最大值与次大值标杆进行选择;而截止阀值与标杆的每种组合策略重复测试100次。然后计算即赢的次数(选中最大值100的次数), 实验结果如表1所示。
从表中可以看出：(1)当采用最大值标杆(m = 1)时, 截止阀值r为37%的组合策略赢的概率最大, 即组合点(r= 37%, m = 1)赢的概率为35%。(2)当采用次大值标杆(m = 2)时, 截止阀值r为50%的组合策略赢的概率最大。即组合点(r= 50%, m = 2)赢的概率为23%。(3)在最大化赢的概率的条件下, 随着标杆由最大值(m = 1)向次大值(m = 2)的变化, 截止阀值也由r= 37%向r= 50%变动。这说明标杆不同, 截止阀值也不同;而且还有标杆降低、截止阀值后移的趋势。
另外, 从表中还可以看出：在阀值37%、最大值标杆处, 赢的概率达到最大(为35%)。该值与理论计算的赢的概率1/ e= 37% [5]只差2个百分点, 与Seale和Rapoport[4] 的仿真结果36%仅差1个百分点。
仿真实验结果中赢的概率35%与23%, 都比理论计算的37% [5] 与25% 少了2 个百分点, 与Seale 和Rapoport[4] 的仿真结果36%仅差1个百分点。Seale和Rapoport在解释其36% 与最优解策略的差距时, 认为是由于仿真实验的随机本性所致。而我们认为, 除此之外还有一种可能性, 即最优解策略的37%是在n趋于无穷时得到的;而当n= 100远小于无穷时, 赢的概率为35%是很有可能的。因此, 我们认为本研究的实验数据具有相当高的信度与效度。
三、结论及进一步的研究
已有的最优解策略, 其主要特征是以取样选项中的最大值作为标杆。而本文基于适应性决策与满意决策的理论提出了结合公式及仿真实际情况下的实验模型。研究结果发现:截止阀值一定的条件下, 随着标杆的降低, 赢的概率呈线性下降的趋势。进一步的研究可以考虑: 增加情境变量(如观察成本或时间压力)对次大值标杆策略的影响研究。
[1]金治明.可拒绝的秘书问题(国防科学技术大学)应用概率统计.第二卷.第四期 1986年11月
[2]邹植民.秘书问题中的两个简易计算公式[ 中图分类号] O211.1 [3]陈家鼎, 李向科.一类最优停止问题的解[ J].应用概率统计, 1986, 2(1): 13-20 [4]Seale, Rapoport.Optimal Stopping Behavior with R elative Ranks:The Secretary Problem with Unknown Population Size[ J].Journal of Behavioral Decision Making, 2000, 13(4): 391.[5]Gilbert, Mosteller.Recognizing the Maximum of a Sequence[ J].Journal of the American Statistical Aociation, 1966, 61: 35-73.
