「マッチングアルゴリズム」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
("マッチングアルゴリズム" を保護しました。 [edit=sysop:move=sysop])
 
(相違点なし)

2007年7月20日 (金) 10:56時点における最新版

【まっちんぐあるごりずむ (matching algorithm)】

マッチング問題を解くアルゴリズムのこと. 一般に, マッチングアルゴリズムは増加道を繰り返し求めることで実現される. マッチングに関する増加道とは, マッチングの枝とそうでない枝を交互に含み, かつ最初と最後の枝がマッチングに含まれるような道のことである. アルゴリズムは, 枝数 0 のマッチングからはじめ, 各反復では, ある条件を満たす増加道を求めてマッチングの枝数を増やす. このような手順により所望のマッチングを求める.