标签: stable-marriage

我正在编写一个算法来匹配不同群体的学生.每个群体的斑点数量有限.每个学生提供他们的前5个小组选择.然后将学生按预定顺序分组(年龄较大的学生和完全出勤的学生优先考虑).不需要完全填充组,但是不能填充通过的容量.

我已经研究过类似的婚姻问题,例如Gale-Shapely稳定的婚姻算法,但我遇到的问题是群体远远少于学生,每个群体都可以接受多个学生.

实现这样一种算法的最佳方法是找到一个完全优化的解决方案,这样学生就没有更好的安排？在算法复杂性方面,我将大约600名学生分成10-20组.

我知道使用 Gale-Shapley 可以保证找到稳定的匹配，但是对于给定的匹配，我们如何验证它是否是稳定的匹配？换句话说，我应该考虑什么条件来验证它是稳定匹配？

以下问题来自 Jon Kleinberg 和 \xc3\x89va Tardos 的“算法设计”，第 1 章，练习 3。我尽可能缩短了描述（我的注释在括号中或引用块之外）

\n

假设我们有两个电视网络，我们将其称为A和B。有n黄金时段的节目时段，每个网络都有n电视节目。每个电视网都希望制定一个时间表——将每个节目分配到一个不同的时段——以便吸引尽可能多的市场份额。\n [...] 每个节目都有固定的收视率[...]；我们假设没有两个节目具有完全相同的评级。如果一个网络在给定的时间段安排的节目比其他网络在该时间段安排的节目具有更高的收视率，则该网络赢得该时间段。目标是赢得尽可能多的时间段。

\n

我们从每个网络获得一个赛季的时间表，因此第一个网络给我们一个时间表s，第二个网络给我们一个时间表T。

\n

[...]如果两个网络都不能单方面改变自己的时间表并赢得更多的时隙，我们就说这对时间表（S，T）是稳定的。

\n

也就是说，不存在S\'给予第一网络更多时隙的调度，并且也不存在用于T\'第二网络的类似调度。

\n

【问题是】：每一套电视剧和收视率，是否总有一对稳定的档期？

\n

我的直觉告诉我不，因为我可以想象稳定时间表的问题的唯一实例是当第一个网络的最佳节目仍然比第二个网络的最差节目差时，即当一个网络可以赢得所有时间表时。否则，我认为一个网络可以交换两个条目以赢得更多插槽，而另一个网络可以更改其时间表，以便始终赢回这些插槽。

我目前正在阅读算法的书,并遇到了稳定的匹配问题.一个问题浮现在脑海里,我很好奇,但这本书没有回答.在每个SMP中,总是可以有一对,每个最喜欢另一个？就像在经典的婚姻例子中一样.是否总有一对有一个女人和一个男人在哪里都排在彼此的首选？