マッチング
いかにも、どこかにアルゴリズムがありそうだが見つからないので作る 偶数kにつき、(1,2,...,k)をk/2ペアに分けるわけ方を列挙する 作戦としては、k個から2つを取り出す場合を列挙、ついでk-2個から2つを取り出す場合を列挙、、、繰り返す そうすると重複…
昨日のMIKUでマッチングと、その「安定な状態」という話を聞いた 安定結婚問題と言うものがあるらしい 安定結婚問題の本当の定義をしっかり確認していないのだけれど、次のような問題設定ができるようだ(その問題設定が安定結婚なのか、それとは違うのか、を…
空間に点集合が2つ()ある。一つ目の集合()から二つ目の集合()への移動であると考えて、どの点がどの点に移動したとみなすことにするかを考える 同数の点に関するマッチングの決め方であるとみなせる マッチングにはハンガリアン・アルゴリズムが使える場合…
重み付きマッチングとは→こちら参照 ついでにハンガリー法の説明にもなっている RでHungarian methodは、パッケージ clueの関数 solve_LSAP() 昨日の記事のlpSolveパッケージのlp.assign()関数も同じことだけれど、このハンガリー法はこの教科書のp271に「現…