Stable Matching Problem——Gale Shapleyアルゴリズム

「すべてのアルゴリズムは実際の問題から出発し、問題の内在的な組合せ構造を深く理解し、アルゴリズム性から設計に着手する」.
Problem
学生は異なる大学を申請して、大学は異なる学生を受け入れて、1つの自己完備のアルゴリズムを見つけてこの問題を解決することができて、最終的な結果が安定したマッチングの結果になりますか?同様に、求職者や会社の求人にも使えます.
安定マッチング(Stable Matching)結果:現在のマッチングよりもお互いを好むように、申請者と受信者を見つけることができません.
Formalization:
入力:n人の男子学生とn人の女子学生、すべての人はすべての異性に対して1つの順位があって、共に2つのn*nの順位の行列があります.
出力:男子学生と女子学生のマッチング結果は、結果に不安定なマッチングは存在しません.
Key Observation:
結果は完全な安定整合であった.
Basic idea:
一部のマッチングから完全なマッチングに徐々に成長し,成長過程に不安定なマッチングが現れないことを保証した.
Inplementation:
「propose-engage」プロセスを使用します.男子:propose、女子:acceptまたはrejectです.
疑似コードは次のとおりです.

StableMatching(A, n)
	for i = 1 to n do
		boys[m] = NULL
		girls[m] = NULL
	end for
	while TRUE do
		if there is no boy b such that boys[b] = NULL then
			return;
		end if 
		select such a boy b arbitrarily
		g = the first girl on m's ranking list to whom g have no yet proposed
		if girls[g] == NULL then
			girls[g] = b;
			boys[b] = g;
		else if g is prefer b to state[g] then
			boys[girls[g]] = NULL;
			boys[b] = g;
			girls[g] = b;
		else
			continue; //reject the propose
		end if
	end whil

は初期化されてからループに入り、現在のすべての男性が一致している場合はループを終了します.そうでなければ、一致していない男子学生の中から任意に1人の男子学生bを選択し、ランキングマトリクスから男子学生bのすべての女子学生に対する順位を選択し、ランキングが最も良い女子学生を見つけ、その女子学生が一致しなければ両者を一致させる.そうでなければ、この女子学生のランキングからマッチした男子学生と現在の男子学生のランキングを見つけ、現在の男子学生がもっと好きなら、前にマッチした男子学生を拒否し、現在の男子学生とマッチしないと、直接現在の男子学生を拒否します.
Correctness
まず、次の結論を得ることができます.

男子学生は順位の下がる順番に女子学生propose

に行きます

女の子が一致したら、

に一致しないことはありません.

男性が女性にproposeをすると、前のマッチング

を破壊する可能性があります.
証明1:すべての男子学生と女子学生が最終的に一致した.
マッチングしていない男性がいるとしたら、すべての女性にproposeしたが拒否されたことを示します.同時に必ず1人の女子学生もマッチングしていないので、1人の男子学生が彼女にproposeをしたことがなくて、これは矛盾を生みました.
証明2:whileサイクルでは、実行されるたびに安定マッチングが行われ、最終的に生成された結果には不安定マッチングは含まれない.
bとg′は不安定な整合であり,それぞれgとb′がより好きであると仮定した.1つ目のケースは、bがg'proposeに向かったことがなく、bがgを好むようになった場合、bとg'は安定しており、矛盾している.第2のケースはbがg'proposeを考えたことがあり、g'がbを拒否したことを説明し、それによってg'はbではなくbをより好きになり、それによってg'とbは安定し、矛盾している.
アルゴリズムは最大O(n^2)の時間を必要とし,これは分かりやすい.