延期验收算法
让我们实现能够解决和大学选择问题的Deferred-Acceptance算法(Gale-Shapley算法)。
当前状态
一对一的DA算法已完成。
要求: : 执行结果: :
将来可以轻松完成的事情
创建一个函数来检查DA算法产生的匹配是否真的稳定(确保没有Blocking Pair)
确保即使更改了申请方的申请顺序,结果也不会改变。
创建一个函数来计算应用方和宿主方的效用(人数n –匹配对手k的等级)
确保DA算法使应用侧的实用程序最大化(使主机侧的实用程序最小化)
确保申请方没有动机作出虚假声明,而主办方有动机作出虚假声明。
回应不完整的偏好
多对一DA算法的实现
似乎很难的事情
创建一个输出所有稳定匹配的函数(如指数级)
考虑使男性和女性的效用总和最大化/使效用的差异最小化的匹配
对应于允许相同顺序的偏好(事先,教师不应给予得分相同的学生优劣)
文学
纸和
2022-05-18 18:13:16
21KB
Python
1