C++ 稳定婚配问题

在组合数学和计算机科学中，稳定婚姻问题是一个著名的难题。它需要在两组元素（例如男性和女性）之间建立稳定的匹配，其中每个人对另一组的个体都有不同的偏好。如果没有任何元素宁愿与彼此匹配而不是与当前伴侣匹配，那么这种匹配被称为稳定匹配。像盖尔-沙普利算法这样的算法经常用于解决这个问题。

算法

解决稳定婚姻问题的一个流行方法是盖尔-沙普利算法，它由大卫·盖尔和劳埃德·沙普利开发。

该算法的步骤如下：

1. 每个单身男子向他尚未求婚的最喜欢的女子求婚。
2. 每个女子仔细权衡她收到的求婚，然后暂时接受她最喜欢的男子的求婚。
3. 当一个女子拒绝一个男子时，该男子会转向他次喜欢的女子并求婚。
4. 只要没有男子被拒绝或用尽他所有的选择，这个过程就会重复。

性质

盖尔-沙普利算法总能找到一个稳定的匹配，并且它的终止是确定的。

在每个阶段，问题都有一个稳定的答案，因为如果一个男子向一个女子求婚，而她拒绝了他，这表明她更喜欢他而不是她当前的伴侣（如果她有伴侣）。

程序

让我们举一个例子来演示 C++ 中的稳定婚姻问题

输出

Enter the number of men and women: 3
Enter men's preferences (0-based indexing):
Preferences for Man 0: 1 0 2
Preferences for Man 1: 2 1 0
Preferences for Man 2: 0 2 1
Enter women's preferences (0-based indexing):
Preferences for Woman 0: 1 0 2
Preferences for Woman 1: 2 1 0
Preferences for Woman 2: 0 2 1
Stable Matches:
Man 0 matches with Woman 1
Man 1 matches with Woman 2
Man 2 matches with Woman 0

1. 首先，将男性和女性的数量输入程序。
2. 之后，每个男性和女性的偏好都被纳入系统。偏好以索引列表的形式输入，其值表示应给予的优先级。
3. 使用盖尔-沙普利算法在男性和女性之间找到稳定的匹配，该算法由stableMarriage函数实现。
4. 算法迭代，直到每个男性都匹配。
   
   • 它会识别每个单身男子名单上尚未收到求婚的第一个女子。
   • 如果该女子是单身，他们之间就会建立匹配。
   • 即使该女子已经匹配，如果她发现她当前的伴侣不如前一个有吸引力，她就会更换伴侣。
   • 直到每个男子都匹配，算法会一直运行。
   • 程序最终会打印出男性和女性之间的稳定匹配。