「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。

MENU

アルゴリズムの学習(002/XXX)

 コンピュータ科学を学ぶべくアルゴリズムを学んでいく。参考として定番書であり古典的名著でもある

を用いる。実装には勉強もかねてC#を使う。

3. 安定的結婚問題

 女性N人、男性N人がそれぞれ異性N人を好みの順に列挙した2N\times Nの表を入力すると、安定な結婚の解を1つ出力する*1

   (1) i=1とする。
   (2) 男性iは女性iに求婚し、差し当たり女性iはこれをOKとし(男性i,女性i)をペアとする。
   (3) i=i+1とする。
   (4) 男性iは女性iに求婚する。女性iは既に求婚された男性j(\lt i)が存在する場合、男性iよりも好ましいならば男性jをそのまま、そうでなければ新たに男性iをペアの相手とし、いなければそのまま男性iを受け入れる。
   (5) i\lt Nならば(3)に戻る。そうでなければアルゴリズムを終了する。

 入力としてN=3として以下の好みを与えることとする。

     1番目 2番目 3番目
   女1 2 3 1
   女2 2 1 3
   女3 3 2 1
   男1 1 3 2
   男2 2 3 1
   男3 3 1 2
using System;

static class Constants
{
    public const int N = 3;
}

namespace _03_StableMarriageProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            var boy = new int[Constants.N + 1];
            var girl = new int[Constants.N + 1, Constants.N + 1];
            var position = new int[Constants.N + 1];
            var rank = new int[Constants.N + 1, Constants.N + 1];

            int b, g, r, s, t;

            // 女性の好み
            for(g = 1; g <= Constants.N; g++)
            {
                for(r = 1; r <= Constants.N; r++)
                {
                    Console.WriteLine("女性{0}の{1}番目の好みは:",g,r);
                    b = int.Parse(Console.ReadLine());
                    rank[g,b] = r;
                }
                boy[g] = 0;
                rank[g, 0] = Constants.N + 1;
            }

            // 男性の好み
            for(b=1; b <= Constants.N; b++)
            {
                for(r = 1; r <= Constants.N; r++)
                {
                    Console.WriteLine("男性{0}の{1}番目の好みは:", b, r);
                    girl[b,r] = int.Parse(Console.ReadLine());
                    position[b] = 0;
                }
            }

            /* 
             * (1) 男性1は女性1に求婚し、差し当たりOKとする
             * (2) 男性i(>1)が女性iに求婚し、既に男性j(<i)から求婚されていれば女性iは自身の好みに応じて、
             *     求婚されている人物か男性iかを選択する
             * (3) i<Nならばi=i+1として(2)に戻る。そうでなければ終了する
            */
            for(b = 1; b <= Constants.N; b++)
            {
                s = b;
                while(s != 0)
                {
                    g = girl[s, ++position[s]];
                    if (rank[g,s] < rank[g, boy[g]])
                    {
                        t = boy[g];
                        boy[g] = s;
                        s = t;
                    }
                }
            }

            // 出力
            for (g = 1; g <= Constants.N; g++) Console.WriteLine("女:{0}と男:{1}がペア", g, boy[g]);
        }
    }
}

 結果は以下のとおり:
f:id:suguru_125:20220403230510p:plain

*1:一応補足すると、結婚は一種の比喩でマッチングの問題である。

プライバシーポリシー お問い合わせ