你知道稳定婚姻的问题吗？

假设有3只雄性和3只雌性。

男人a

男性b

男子c级

女p

女人q

女r

然后你可以配对3对。

但是，异性有不同的喜好，希望结果尽可能令人满意。

假设一个人排在那里。

形式

首先

第二

第三名

身体

男人a的偏爱

女p

女人q

女r

南人乙的味道

女人q

女r

女p

男人c的偏爱

女p

女人q

女r

女警的味道

男丙

人b

男人a

女人Q的味道

人b

男人a

男丙

女人r的味道。

男丙

男人a

人b

现在，假设您考虑以下匹配。

男a？女q

男b女r

男c女p

男c和女p很幸福，因为他们嫁给了对方的头号伴侣。

但是男人A和男人B呢？我更喜欢代替我的妻子。

因此，让我们更改匹配以执行以下操作：

男人a？女r

男b女q

男c女p

如果你再次更换它，情况似乎会变得更糟。

没有进一步替换的匹配结果称为“稳定匹配”。

“稳定婚姻问题”是一个根据排名寻找稳定匹配的问题。

在数学上，它被称为组合优化问题之一。

Java中的原型盖尔-沙普利算法

稳定婚姻的问题如此出名，以至于被列在维基百科上。

？稳定的婚姻-维基百科

三男三女很容易，但随着数量的增加，可能组合的数量急剧增加，变得更加困难。

如果你看看维基百科，你可以看到盖尔-沙普利算法。

稳定婚姻问题的创始人盖尔和沙普利提出的算法。

似乎需要一场稳定的比赛.

因此，我尝试使用Java快速实现它。

但是，请注意，这个源代码几乎没有用，原因如下！

目前我做的都是强调速度，完全不考虑可读性和处理速度。

输入(排名数据)是硬编码的

只有输出(匹配结果)输出到标准输出

源代码

一个

2

三

四

五

六

七

八

九

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

四十二

43

四十四

45

46

47

48

四十九

50

51

五十二

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

六十八

六十九

70

71

七十二

73

74

75

76

77

七十八

79

80

81

82

83

84

八十五

86

87

88

八十九

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

包装hoge

导入Java . util . ArrayList；

导入Java . util . collections；

导入Java . util . HashMap；

公共类randomMatching {

公共静态HashMapString，ArrayListString排名；

公共静态HashMapString，字符串匹配；

公共静态void main(String args[]){ 0

//初始号码

matching=new HashMapString，String()；

Matching.put('男a '，' ')；

Matching.put('男b '，' ')；

Matching.put('男c '，' ')；

ranking=new HashMapString，ArrayList string()；

Ranking.put('男A '，new ArrayList())；

Ranking.put('男B '，new ArrayList())；

Ranking.put('男C '，new ArrayList())；

Ranking.put('女P '，new ArrayList())；

Ranking.put('女Q '，new ArrayList())；

Ranking.put('女R '，new ArrayList())；

Collections.addAll(ranking.get('男a ')，'女p '，'女q '，'女r ')；

Collections.addAll(ranking.get('男b ')，'女q '，'女r '，'女p ')；

Collections.addAll(ranking.get('男c ')，'女p '，'女q '，'女r ')；

Collections.addAll(ranking.get('女p ')，'男c '，'男b '，'男a ')；

Collections.addAll(ranking.get('女q ')，'男b '，'男a '，'男c ')；

Collections.addAll(ranking.get('女r ')，'男c '，'男a '，'男b ')；

虽然(真)

{

//现在，“状态”表示

dump()；

//单身男性探索

字符串singleManName=

for(String manName : matching . KeySet()){ 0

if(matching.get(manName)=' ')

{

singleManName=manName

打破；

}

}

//单身男性occasion

if(singleManName==' ')

{

系统。out.println ('，))；

返回；

}

//调查单身男性喜欢的女性并求婚

string best women name=ranking . get(单一名称).get(0)；

system.out.println(单人姓名)攻击了我最喜欢的' bestWomanName ' .);

//调查这个女性是否单身

字符串名称=' ';

用于(字符串管理名称：匹配。密钥集() ) {

if(matching.get(manName )==更佳实践名称)

{

汇丰银行名称=manname

System.out.println('但是' bestWomanName '正在和' husbandName '交往。' );

布莱克；

}

}

//如果这个女性是单身的话就订婚

如果(汇丰银行名称==' ' )

{

system . out . println(best women name)现在是自由的，所以决定和'单身吗'交往。' );

matching.put(单一名称，更佳大纲名称);

继续；

}

其他

{

//调查订婚中的hasbandName和向我求婚的单身吗？你更喜欢哪一个

用于(字符串str :排名。获取(更佳名称) )

{

//husbandName更喜欢的情况

if (str==汇丰银行名称)

{

//singleMan今后不会再向这位女性求婚了

system . out . println(best women name)比起'单身吗'我更喜欢丈夫的名字.单人域名'放弃了' bestWomanName ' .);

ranking.get(单一名称) .移除（更佳名称);

布莱克；

}

//husbandName更喜欢的情况

if (str==单一名称)

{

//订婚

system . out . println(best women name)比起' husbandName '更喜欢'单一吗名'，所以决定换乘。' );

matching.put(单一名称，更佳大纲名称);

matching.put(汇丰名称，'');

布莱克；

}

}

}

}

}

//显示当前状态的函数

公共静态语音双工()

{

系统输出(' ' );

System.out.println('当前排名');

用于(字符串密钥：秩。密钥集() ) {

System.out.println(？关键点（关键点);

}

system . out . println()当前的匹配');

用于(字符串管理名称：匹配。密钥集() ) {

System.out.println(？域名'?'matching.get(名称) );

}

系统输出(' ' );

}

}

执行结果

从根本没有建立夫妇的状态开始，

它旨在逐步System.out.println()进度。

一

2

3

四

5

6

七

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

当前排名

？男人C [女人p，女人q，女人R]

？男[女p，女q，女R]

？女人[男人b，男人一个，男人C]

？男[女q，女r，女P]

？女人[男人c，男人一个，男人B]

？女人P [男人c，男人b，男人A]

现在的匹配

？男c？

？男a？

？男b？

男c攻击了最喜欢的女p .

女p现在因为自由决定和男c交往。

当前排名

？男人C [女人p，女人q，女人R]

？男[女p，女q，女R]

？女人[男人b，男人一个，男人C]

？男[女q，女r，女P]

？女人[男人c，男人一个，男人B]

？女人P [男人c，男人b，男人A]

现在的匹配

？男c？女p

？男a？

？男b？

男人攻击了最喜欢的女人p .

但是女p在和男c交往。

女人p比男人a更喜欢男人c .男人放弃了女p .

当前排名

？男人C [女人p，女人q，女人R]

？男人

？女人[男人b，男人一个，男人C]

？男[女q，女r，女P]

？女人[男人c，男人一个，男人B]

？女人P [男人c，男人b，男人A]

现在的匹配

？男c？女p

？男a？

？男b？

男人攻击了最喜欢的女人问.

q现在为了自由，决定和男a交往。

当前排名

？男人C [女人p，女人q，女人R]

？男人

？女人[男人b，男人一个，男人C]

？男[女q，女r，女P]

？女人[男人c，男人一个，男人B]

？女人P [男人c，男人b，男人A]

现在的匹配

？男c？女p

？男a？女q

？男b？

男人攻击了最喜欢的女人问.

但是女q在和男a交往。

q比起男a更喜欢男b，所以决定转车。

当前排名

？男人C [女人p，女人q，女人R]

？男人

？女人[男人b，男人一个，男人C]

？男[女q，女r，女P]

？女人[男人c，男人一个，男人B]

？女人P [男人c，男人b，男人A]

现在的匹配

？男c？女p

？男a？

？男b？女q

男人攻击了最喜欢的女人问.

但是女q在和男b交往。

比起男人一个，女人更喜欢男人b .男的放弃了女的问.

当前排名

？男人C [女人p，女人q，女人R]

？男人

？女人[男人b，男人一个，男人C]

？男[女q，女r，女P]

？女人[男人c，男人一个，男人B]

？女人P [男人c，男人b，男人A]

现在的匹配

？男c？女p

？男a？

？男b？女q

男人攻击了最喜欢的女人r .

她现在是自由的，所以决定和男a交往。

当前排名

？男人C [女人p，女人q，女人R]

？男人

？女人[男人b，男人一个，男人C]

？男[女q，女r，女P]

？女人[男人c，男人一个，男人B]

？女人P [男人c，男人b，男人A]

现在的匹配

？男c？女p

？男a？女r

？男b？女q

因为免费的人不见了，所以结束程序。

以上是执行结果。

获得稳定的匹配。

这个算法的优点

(1)始终需求稳定的匹配

在执行结果的中间

一

女人p比男人a更喜欢男人c .男人放弃了女p .

有一个出口

的地方。

当女人拒绝这样的男人攻击时，

男人'放弃，也就是说，将女人排除在他的排名之外。

此排除操作绝会使男性反复攻击相同的女性。

就是为什么算法总是退出而不会陷入无限循环的原因。

(2)不二婚姻而且申请

其次，我以'哪个男人和哪个女人该结婚？'为主题进行了手段，但愿是

除此之外，例如在学校，您似乎做类似'该给哪个学生参加哪个研讨会？'这样的情况。

研讨会教授将能够对其他最喜欢的学生进行排名。

将能创建学生也想参加的研讨会的排名。

该算法可以对任意主题执行，只要彼此排名即可。

我们正在寻找的是'稳定匹配。

有人可以抱怨您找到的匹配结果！

概括

尽管这是一件急事，但是我可以用爪哇实现盖尔-沙普利算法。

如果您有现实的算法或者要解决的组合优化问题，我想再次试一下。