マッチング

ペアに分ける

いかにも、どこかにアルゴリズムがありそうだが見つからないので作る 偶数kにつき、(1,2,...,k)をk/2ペアに分けるわけ方を列挙する 作戦としては、k個から2つを取り出す場合を列挙、ついでk-2個から2つを取り出す場合を列挙、、、繰り返す そうすると重複…

配偶者を取り換える

昨日のMIKUでマッチングと、その「安定な状態」という話を聞いた 安定結婚問題と言うものがあるらしい 安定結婚問題の本当の定義をしっかり確認していないのだけれど、次のような問題設定ができるようだ(その問題設定が安定結婚なのか、それとは違うのか、を…

移動とマッチングに関するメモ

空間に点集合が2つ()ある。一つ目の集合()から二つ目の集合()への移動であると考えて、どの点がどの点に移動したとみなすことにするかを考える 同数の点に関するマッチングの決め方であるとみなせる マッチングにはハンガリアン・アルゴリズムが使える場合…

重み付きマッチングで最適解

重み付きマッチングとは→こちら参照 ついでにハンガリー法の説明にもなっている RでHungarian methodは、パッケージ clueの関数 solve_LSAP() 昨日の記事のlpSolveパッケージのlp.assign()関数も同じことだけれど、このハンガリー法はこの教科書のp271に「現…