神奇的数学.doc

神奇的数学
神奇的数学:科学帮你找到伴侣 假设班上三男 (分别是A, B, C), 三女 (分别是x, y, z), 见下图:
图一: 班上三男三女
他们心中对异性的排名见图二.
图二: 各位男女生对异性的排名
神奇的数学
神奇的数学:科学帮你找到伴侣 假设班上三男 (分别是A, B, C), 三女 (分别是x, y, z), 见下图:
图一: 班上三男三女
他们心中对异性的排名见图二.
图二: 各位男女生对异性的排名
第一轮中, 男生们向心中的No. 1女示好, 即A, B 两男向心中最喜欢的x女示好, 而C男向y女示好.
图三: 第一轮中, 各自向心中的 No. 1 示爱
如果采用immediate acceptance, 此轮之后的结果是, x-A, y-C 两对结成情侣. 注意, y 女虽然心中首选是B男, 但是由于B男在此轮中正在追逐x女, 无奈下y女屈就于唯一来献殷勤的C男. 比及第二轮开始时, 唯一还 available 的就是z女了.
图四: 传统配对方法的结果 (拆散多少天造地设的情侣) 最后的结果是 x-A, y-C, z-B 三对恋人. 注意: y女和B男两人都更愿意离开自己的现任伴侣而彼此在一起. 这种不稳定的状态就是很多文学影视作品的来源哈. 在数学上, 这也恰恰被称为是”不稳定”(unstable)的组合. 顾名思义, 我们希望能够有种算法, 给我们的结果是所有配对都是稳定的. 4.
作为班主任的你, 这时候就会想到(如果你学****了比如 Gale 和 Shapley 这篇刊登于1962年1月美国数学月刊的经典论文的话), 你就会想到这是一个呼唤你采用 deferred acceptance algorithm 的课题. 你会让同学们这么做:
每个男生在第一轮中向自己心中的No. 1 示爱. 但是各位姑娘们不用立即决定(所以该方法名称中有”deferred”一词), 而是先hold 住了. 在第二轮中, 每个男生再向心中的 No. 2 示爱. 从第二轮开
始, 每位姑娘们只保留自己到现在为止所收获的最心仪的男生(但是不用答应他, 只hold在心理), 而拒绝其他所有人. 而被拒绝的男生(也就是现在尚没有人hold着你的男生) 则继续在下一轮中向心中排名的下一个姑娘表白. 以此类推, 一轮轮继续下去, 直到所有想示爱的男生都示完为止. 此时, 每个手中有 offer 的姑娘, 可以选择接受.
以上就是 deferred acceptance algorithm 的做法. 大家算一下, 就会发现, 在我们这个简单的例子中, 最后的结果是 x-A, y-B, z-C 三组恋人终成眷侣. 而这是一个 stable 的结果. 所有6人中, 你不可能找到一男一女符合以下条件: 他们都更愿意抛弃已有的伴侣而与彼此在一起.
图五: 运用"推迟接受"算法得到的理想结果
5.
Deferred acceptance algorithm 能够从数学上证明是一定会产生 stable 配对的算法. 这使它成为一个重要的工具, 因为这类的配对问题在现实生活中太常见了. 申请过美国大学的同学们都知