Gale-Shapleyアルゴリズムの実装 - LIVESENSE Data Analytics Blog

こんにちは、リブセンスでデータサイエンティストをしている北原です。今回は、マッチングアルゴリズムとして有名なGale-Shapleyアルゴリズムを扱います。今回の記事ではアルゴリズムをそのまま実装したものを紹介し、次回の記事で計算速度を考慮した実装を紹介します。なお、弊社サービスknewが始まった頃にユーザーの急増に備えて書いたコードが元ネタですが、残念ながら今回および次回紹介するコードはknewでは使われていません。コードはJuliaとRです。下記の次回記事とセットでお読みください。 analytics.livesense.co.jp Gale-Shapleyアルゴリズム 実装 まとめ Gale-Shapleyアルゴリズム Gale-Shapleyアルゴリズムは、選好順序に基づき安定マッチングとなるペアを見つけることで、安定結婚問題を解くアルゴリズムです。アルゴリズムの特徴からDA(De