8.概率组合数学.pdfVIP

概率组合数学 七月算法 邹博 2015年11月8日 花开堪折直须折  婚介所登记了N位男孩和N位女孩，每个男 孩都对N 个女孩的喜欢程度做了排序，每个 女孩都对N 个男孩的喜欢程度做了排序。 作为月老，能否给出稳定的牵手方案？  分析：每个男孩都对N 个女孩做了排序，N 个男 孩的钟情度形成N ×N 的矩阵A ；同时，N 个女 孩的钟情度形成N ×N 的矩阵B ；  如果男孩i和女孩a 牵手，但男孩i对女孩b 更喜 欢，而女孩b 的男友j 拼不过男孩i ，则没有力量 阻碍男孩i和女孩b 的私奔，这即是不稳定的。 10月算法在线班 2/61 题目解析  采取贪心的思路：  所有男孩同时对各自最喜欢的女孩表白：  若女孩a 只有1个男孩i 表白，接受男孩i ；  若女孩a有多位男孩表白，选择她最喜欢的男孩x  若女孩a 没有男孩表白，静静等待下一轮。  第k轮，所有单身男孩对各自第k喜欢的女孩表白：  无论该女孩是否有男友；  若女孩a 收到了男孩i 的表白：  若女孩a 没有男友，则接受男孩i ；  若相对于现任男友j ，女孩a 更喜欢男孩i ，则接受男孩i ； 10月算法在线班 3/61 正确性分析：匹配性和稳定性  在某个时刻，任何一个女孩要么已经有了男友，要么还会有男 孩对其表白(她此刻没有男友，说明还有单身男孩，所以，该女 孩不用着急，只需等待) ，她总可以在表白的男孩中选择一个自 己最喜欢的，因此，任何一个女孩必然都能找到男友。  因为“N-N” 的比例关系，这也导致了每个男孩都能有女友。  不稳定情况：如果男孩i和女孩a 牵手，但男孩i对女孩b 更喜欢， 而女孩b 的男友j 拼不过男孩i ，则男孩i和女孩b 的私奔。  1、男孩i和女孩a 牵手  2 、男孩i对女孩b 更喜欢  3 、相对于男友j ，女孩b 的更喜欢男孩i  打破上述三个前提中的一个：1和2说明男孩i 曾经向女孩b 表白 却遭拒，这说明相对于男孩i ，女孩b 的更喜欢现任男友j 。 10月算法在线班 4/61 Code 10月算法在线班 5/61 改进相互表 的策略？ 相互表  首轮a ：所有男孩同时对各自最喜欢的女孩表白：  若女孩a 只有1个男孩i 表白，接受男孩i ；  若女孩a有多位男孩表白，选择她最喜欢的男孩x  若女孩a 没有男孩表白，静静等待下一轮。  首轮b ：所有女孩同时对各自最喜欢的男孩表白：  策略同a  第k轮a ：所有单身男孩对各自第k喜欢的女孩表白：  无论该女孩是否有男友；  若女孩a 收到了男孩i 的表白：  若女孩a 没有男友，则接受男孩i ；  若相对于现任男友j ，女孩a 更喜欢男孩i ，则接受男孩i ；  第k轮b ：所有单身女孩对各自第k喜欢的男孩表白：  策略同a 10月算法在线班 6/61 一个反例  男女孩各3位： 0 1 2  每个男孩的钟情度矩阵为： 0 0 1 1