首页 > 上网技巧 > 电脑小技巧 > 我用Java编写了一个算法来解决稳定婚姻问题

我用Java编写了一个算法来解决稳定婚姻问题

时间:2021-06-03 11:46 作者:QQ地带 我要评论

你知道稳定的婚姻问题吗?
 
 
假设有3名男性和3名女性。
 
男子A
男子B
男子C
女人P
女人Q
女人R
然后您可以结对3对。
但是,异性有不同的喜好,我希望结果尽可能令人满意。
 
假设一个人在那里排名。
 
<表格>
 
第一名
第二名
第三名
 
 
<身体>
男人A的偏好
女人P
女人Q
女人R
男人B的味道
女人Q
女人R
女人P
曼C的偏好
女人P
女人Q
女人R
女人P的品味
Man C
人B
人A
女人Q的品味
人B
人A
Man C
女人R的品味
Man C
人A
人B
 
 
现在,假设您考虑以下匹配。
 
男A?女Q
男B女R
男C女P
男性C和女性P很高兴,因为他们与对方的头号伴侣结婚。
但是,男人A和男人B呢?我更愿意代替妻子。
因此,让我们更改匹配以执行以下操作:
 
男人A?女人R
男B女Q
男C女P
如果您再更换它,情况似乎会变得更糟。
不需要进一步替换的匹配结果称为"稳定匹配"。
 
"稳定婚姻问题"是根据排名来寻找稳定匹配的问题。
在数学界,它被称为组合优化问题之一。
 
Java中的原型Gale-Shapley算法
 
稳定的婚姻问题如此著名,以至于在Wikipedia上列出。
?稳定婚姻问题-维基百科
 
3个男人和3个女人很容易,但是随着人数的增加,可能组合的数量急剧增加,并且变得更加困难。
 
如果您查看维基百科,则可以看到Gale-Shapley算法。
由稳定婚姻问题的创建者Gale和Shapley提出的算法。
似乎绝对需要稳定的匹配...
 
因此,我尝试使用Java快速实现它。
 
但是,请注意,由于以下原因,此源代码几乎无济于事!
 
目前,我所做的只是强调速度,而我根本不考虑可读性或处理速度。
输入(排名数据)是硬编码的
仅输出(匹配结果)输出到标准输出
源代码
 
1
2
3
4
5
6
7
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
package hoge;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
 
public class randomMatching {
 
    public static HashMap<String, ArrayList<String>> ranking;
    public static HashMap<String, String> matching;
 
    public static void main(String args[]){
 
        // 変数初期化
        matching = new HashMap<String, String>();
        matching.put("男A", "");
        matching.put("男B", "");
        matching.put("男C", "");
        ranking = new HashMap<String, 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");
 
        while(true)
        {
            // 現在の状況を表示
            dump();
 
            // 独身男性を探す
            String singleManName = "";
            for (String manName : matching.keySet()) {
                if(matching.get(manName) == "")
                {
                    singleManName = manName;
                    break;
                }
            }
 
            // 独身男性がもういない場合
            if(singleManName == "")
            {
                System.out.println("フリーの人がいなくなったため、プログラムを終了します。");
                return;
            }
 
            // 独身男性の好みの女性を調べてプロポーズする
            String bestWomanName = ranking.get(singleManName).get(0);
            System.out.println(singleManName + "が、一番好きな" + bestWomanName + "にアタックしました。");
 
            // この女性が独身か調べる
            String husbandName = "";
            for (String manName : matching.keySet()) {
                if(matching.get(manName) == bestWomanName)
                {
                    husbandName = manName;
                    System.out.println("ところが" + bestWomanName + "は" + husbandName + "と付き合っています。");
                    break;
                }
            }
 
            // この女性が独身だった場合は婚約
            if(husbandName == "")
            {
                System.out.println(bestWomanName + "は現在フリーのため" + singleManName + "と付き合うことにしました。");
                matching.put(singleManName, bestWomanName);
                continue;
            }
            else
            {
                // 婚約中の hasbandName と、プロポーズしてきた singleManName 、どちらが好みか調べる
                for(String str : ranking.get(bestWomanName))
                {
                    // husbandName のほうが好みの場合
                    if(str == husbandName)
                    {
                        // singleManはこの女性に今後二度とプロポーズしない
                        System.out.println(bestWomanName + "は" + singleManName + "より" + husbandName + "が好きです。" + singleManName + "は" + bestWomanName + "を諦めました。");
                        ranking.get(singleManName).remove(bestWomanName);
                        break;
                    }
 
                    // husbandName のほうが好みの場合
                    if(str == singleManName)
                    {
                        // 婚約
                        System.out.println(bestWomanName + "は" + husbandName + "より" + singleManName + "が好きなので、乗り換えることにしました。");
                        matching.put(singleManName, bestWomanName);
                        matching.put(husbandName, "");
                        break;
                    }
                }
            }
        }
 
    }
 
    // 現在の状態を表示する関数
    public static void dump()
    {
        System.out.println("");
 
        System.out.println("現在のランキング");
        for (String key : ranking.keySet()) {
            System.out.println("?" + key + " " + ranking.get(key));
        }
 
        System.out.println("◆現在のマッチング");
        for (String manName : matching.keySet()) {
            System.out.println("?" + manName + " ? " + matching.get(manName));
        }
 
        System.out.println("");
    }
}
执行结果
 
从根本没有建立夫妻的状态开始,
它旨在逐步System.out.println()进度。
 
1
2
3
4
5
6
7
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]
?男A [女P, 女Q, 女R]
?女Q [男B, 男A, 男C]
?男B [女Q, 女R, 女P]
?女R [男C, 男A, 男B]
?女P [男C, 男B, 男A]
◆現在のマッチング
?男C ?
?男A ?
?男B ?
 
男Cが、一番好きな女Pにアタックしました。
女Pは現在フリーのため男Cと付き合うことにしました。
 
現在のランキング
?男C [女P, 女Q, 女R]
?男A [女P, 女Q, 女R]
?女Q [男B, 男A, 男C]
?男B [女Q, 女R, 女P]
?女R [男C, 男A, 男B]
?女P [男C, 男B, 男A]
◆現在のマッチング
?男C ? 女P
?男A ?
?男B ?
 
男Aが、一番好きな女Pにアタックしました。
ところが女Pは男Cと付き合っています。
女Pは男Aより男Cが好きです。男Aは女Pを諦めました。
 
現在のランキング
?男C [女P, 女Q, 女R]
?男A [女Q, 女R]
?女Q [男B, 男A, 男C]
?男B [女Q, 女R, 女P]
?女R [男C, 男A, 男B]
?女P [男C, 男B, 男A]
◆現在のマッチング
?男C ? 女P
?男A ?
?男B ?
 
男Aが、一番好きな女Qにアタックしました。
女Qは現在フリーのため男Aと付き合うことにしました。
 
現在のランキング
?男C [女P, 女Q, 女R]
?男A [女Q, 女R]
?女Q [男B, 男A, 男C]
?男B [女Q, 女R, 女P]
?女R [男C, 男A, 男B]
?女P [男C, 男B, 男A]
◆現在のマッチング
?男C ? 女P
?男A ? 女Q
?男B ?
 
男Bが、一番好きな女Qにアタックしました。
ところが女Qは男Aと付き合っています。
女Qは男Aより男Bが好きなので、乗り換えることにしました。
 
現在のランキング
?男C [女P, 女Q, 女R]
?男A [女Q, 女R]
?女Q [男B, 男A, 男C]
?男B [女Q, 女R, 女P]
?女R [男C, 男A, 男B]
?女P [男C, 男B, 男A]
◆現在のマッチング
?男C ? 女P
?男A ?
?男B ? 女Q
 
男Aが、一番好きな女Qにアタックしました。
ところが女Qは男Bと付き合っています。
女Qは男Aより男Bが好きです。男Aは女Qを諦めました。
 
現在のランキング
?男C [女P, 女Q, 女R]
?男A [女R]
?女Q [男B, 男A, 男C]
?男B [女Q, 女R, 女P]
?女R [男C, 男A, 男B]
?女P [男C, 男B, 男A]
◆現在のマッチング
?男C ? 女P
?男A ?
?男B ? 女Q
 
男Aが、一番好きな女Rにアタックしました。
女Rは現在フリーのため男Aと付き合うことにしました。
 
現在のランキング
?男C [女P, 女Q, 女R]
?男A [女R]
?女Q [男B, 男A, 男C]
?男B [女Q, 女R, 女P]
?女R [男C, 男A, 男B]
?女P [男C, 男B, 男A]
◆現在のマッチング
?男C ? 女P
?男A ? 女R
?男B ? 女Q
 
フリーの人がいなくなったため、プログラムを終了します。
以上是执行结果。
成功获得稳定的匹配。
 
这个算法的优点
 
(1)始终需要稳定的匹配
在执行结果的中间
 
1
女Pは男Aより男Cが好きです。男Aは女Pを諦めました。
有一个输出
 
的地方。
当女人拒绝这样的男人攻击时,
男人"放弃",也就是说,将女人排除在他的排名之外。
此排除操作绝不会使男人反复攻击相同的女人。
这就是为什么算法始终退出而不会陷入无限循环的原因。
 
(2)不仅婚姻而且申请
这次,我以"哪个男人和哪个女人应该结婚?"为主题进行了尝试,但是
除此之外,例如在学校,您似乎可以做类似"您应该给哪个学生参加哪个研讨会?"这样的事情。
研讨会教授将能够对他最喜欢的学生进行排名。
您将能够创建学生也想参加的研讨会的排名。
 
该算法可以对任何主题执行,只要彼此排名即可。
我们正在寻找的是"稳定匹配"。
没有人可以抱怨您找到的匹配结果!
 
概括
 
尽管这是一件急事,但我能够用Java实现Gale-Shapley算法。
如果您有要实现的算法或要解决的组合优化问题,我想再次尝试一下。

标签: java
顶一下
(0)
0%
踩一下
(0)
0%

Google提供的广告