苏格拉底的麦穗原理
突然想起来上次面试过一个苏格拉底麦穗问题，即苏格拉底说：我请你穿越这片稻田，去摘一株最大最金黄的麦穗回来，但是有个规则：你不能走回头路，而且你只能摘一次。
当初我给出的解决方案类似于苏格拉底第三个弟子的做法，第三个弟子把麦田分为三份，走第一个1/3时，只看不摘，分出大、中、小三类麦穗，在第二个1/3里验证是否正确，然后选择了大麦穗中的一支美丽的麦穗。
刚才吃饭的时候又突然想起来这个问题，上网搜了搜，也有了部分启发，即和算法导论的在线雇佣问题本质上是一样的（中文5.4.4节 66-68页）。为了偷懒我就直接贴英文的内容了：
As a final example, we consider a variant of the hiring problem. Suppose now that we do not wish to interview all the candidates in order to find the best one. We also do not wish to hire and fire as we find better and better applicants. Instead, we are willing to settle for a candidate who is close to the best, in exchange for hiring exactly once. We must obey one company requirement: after each interview we must either immediately offer the position to the applicant or must tell them that they will not receive the job. What is the trade-off between minimizing the amount of interviewing and maximizing the quality of the candidate hired?
We can model this problem in the following way. After meeting an applicant, we are able to give each one a score; let score(i) denote the score given to the ith applicant, and assume that no two applicants receive the same score. After we have seen j applicants, we know which of the j has the highest score, but we do not know if any of the remaining n - j applicants will have a higher score. We decide to adopt the strategy of selecting a positive integer k < n, interviewing and then rejecting the first k applicants, and hiring the first applicant thereafter who has a higher score than all preceding applicants. If it turns out that the best-qualified applicant was among the first k interviewed, then we will hire the nth applicant. This strategy is formalized in the procedure ON-LINE-MAXIMUM(k, n), which appears below. Procedure ON-LINE-MAXIMUM returns the index of the candidate we wish to hire.
ON-LINE-MAXIMUM(k, n)
1 bestscore ← -∞
2 for i ← to k
3 do if score(i) > bestscore
4 then bestscore ← score(i)
5 for i ← k + 1 to n
6 do if score(i) > bestscore
7 then return i
8 return n
书上给出了证明，比较多，这里就不列出了，感兴趣的同学可以参考http://mitpress.mit.edu/catalog/item/default.asp?tid=8570&ttype=2
这里直接给出结论：如果用k=n/e来实现这个策略，则可以以至少1/e的概率，成功地雇用到最优资格的应聘者。这是一种比较好的算法，貌似这个问题没有最优解，目前。
相关文章：
No comments:
Post a Comment