安定結婚問題ソルバー — 2つのグループ間の安定マッチングを求める
この安定結婚問題ソルバーは、Gale-Shapley遅延受諾アルゴリズムを使用して、提案者と評価者という同サイズの2つのグループ間で、どのペアも割り当てられたパートナーよりお互いを好むことがないマッチングを求めます。各参加者の他グループに対する順位付き選好リストが与えられます。
クイック回答
同サイズの2つのグループの順位付き選好リストを入力すると、Gale-Shapleyアルゴリズムで安定マッチングを即座に求められます。
提案者1人につき1行：名前: 選好1, 選好2, ...（すべての評価者を順位付け、例：A1: B2, B1, B3）。
評価者1人につき1行：名前: 選好1, 選好2, ...（すべての提案者を順位付け、例：B1: A3, A1, A2）。
安定結婚問題ソルバー — Gale-Shapleyアルゴリズムをオンラインでの使い方
- 1
各提案者の選好を1行として入力します：名前: 選好1, 選好2, 選好3, ...（最も好むものから最も好まないものへ順位付け）。
- 2
各評価者の選好も同様に、すべての提案者を順位付けして入力します。
- 3
「計算」をクリックしてGale-Shapleyアルゴリズムで安定マッチングを求めます。
なぜ安定結婚問題ソルバー — Gale-Shapleyアルゴリズムをオンラインでを使うのか？
2つのグループ間のマッチングは、お互いを現在割り当てられたパートナーよりも好むペアが存在しない場合に「安定」と言えます — そのようなペアが存在すると、既存のマッチングを破棄する動機を持つことになり、マッチングが不安定になります。Gale-Shapleyアルゴリズムは常に安定マッチングを見つけます（2012年のノーベル経済学賞を受賞した基礎的な結果です）：マッチングされていない各提案者は残っている中で最も好む選択に提案し、各評価者はこれまでの最良のオファーを暫定的に受け入れ、残りを拒否します（より良いオファーが来た場合は以前のマッチングを取り消すことさえあります）。これが全員がマッチングされるまで繰り返されます。結果は安定であるだけでなく提案者最適です — 各提案者は、いかなる安定マッチングにおいても得られる最良のパートナーを得ます。
よくある質問
関連ツール
ネットワークフロー電卓 — Edmonds-Karpによる最大フローをオンラインで
Edmonds-Karpアルゴリズムを使用して、容量制約付き有向グラフのソースからシンクへの最大フローを求めます。シンプルな辺リスト入力の無料電卓。
グラフ彩色計算機 — オンラインでウェルシュ・パウエルアルゴリズム
貪欲なウェルシュ・パウエルアルゴリズムを使用して、接続された2つのノードが色を共有しないようにグラフの頂点を彩色します。シンプルな辺リスト入力を備えた無料計算機。
順列計算機 — P(n,r)をオンラインで計算
順列P(n,r) — 順序が重要な、n個の要素からr個を並べる方法の数を計算します。段階的な解法と公式の内訳付きの無料計算機。