スイスドローのマッチングを、Python+NetworkXでおこなう話

近況

ブログの執筆をしようと思っていたのですが、早1か月が経ってしまいました。
その間、知人に頼まれてポケモンカードゲームの大会運営プラットフォームを作っていました。
UI・UXの知識があんまりないので、利用者に快適に用いてもらえるものを作るのが結構難しいです。勉強しなければ...

Pythonでのスイスドローのマッチングの実装

さて、今回はその中で利用した、スイスドロー形式の大会の対戦マッチングの方法について解説したいと思います。

用いるもの

Python 3.7, NetworkX 2.2
スイスドローのマッチングは、グラフ理論の「最小重み最大マッチング問題」と呼ばれる問題に当てはめて解くことができます。
参考リンク：
この問題も、PythonのライブラリNetworkXを使うと簡単に解くことができます。

実装の手順

①プレイヤーをノードとしてグラフ上に配置
②すべての未対戦の組み合わせの2ノード間に、【勝ち点の差の絶対値等】を-1倍した数値を重みとしたエッジを作成する。
(【】の中身は、大会ごとに異なると思いますので各自変えてください。なお、勝ち点→オポネントのようにタイブレイカーを導入したい場合は、後のものを十分小さい値にして重みに足し合わせればうまく行くはずです。)
③NetworkXの、「networkx.algorithms.matching.max_weight_matching(maxcardinality=True)」を用いて、重みの合計が最大になる組み合わせを求める。
（NetworkXには最大重み(最大)マッチング問題を解く関数しか用意されていないので、②では重みを-1倍しています。）
④おわり

特に難しい点はないので、サンプルコードは用意していません。 





なお、重みをそのまま用いると上位層と下位層での重みの差の扱いが同じになってしまいます。



上位層でできるだけ階段マッチングを発生させないよう、重みを2乗(した後で-1倍)してから用いると良いかもしれないです。









間違っている部分があれば、ご指摘いただけると幸いです。

ご拝読ありがとうございました。 


































コメント











コメントを投稿























このブログの人気の投稿









NetworkXでTTCサイクルを実装する（アルゴリズム編）




















イメージ







 大学のマーケットデザインの授業で習った「TTCアルゴリズム」をPythonのライブラリNetworkXを使って実装してみたので、残しておこうと思います。   今回の記事ではアルゴリズムの中身の部分について、次回はそれをWebサイト(Django)上でGUIで動かして、誰でもプレゼント交換に使えるようにした記事を書く予定です。   TTCアルゴリズムのコード  さて、まずTTCアルゴリズムのマッチングを行うコードは以下の通りです。    import networkx as nx import random import matplotlib.pyplot as plt   def ttc_algorithm(preference_dict: dict):     result_cycles_list = []      while preference_dict != {}:          # create directed graph         g = nx.DiGraph()          # add nodes         nodes_list = []         for key in preference_dict:             nodes_list.append(key)          nodes_list.sort()          for elem in nodes_list:             g.add_node(elem)          for key in preference_dict:             g.add_edge(key, preference_dict[key][0])          # search for cycles         cycles = nx.simple_cycles(g)         cycles_list = list(cycles)          # Graph drawing part starts here         color_map_dict_pre = {key: "deepskyblue" for key in preference_dict.keys()}          for cy...








続きを読む










食洗機の分岐水栓の小さな円筒形の部品で困った話




















イメージ







       この小さな円筒形の部品は、おそらく逆流防止用の弁です。   分岐水栓の根元の部分に取り付けて使うものと思います。(なくても動きますが、不安ですよね...)   塞がっている方を押すと動いて開くようになっているので、向きに気をつけて使用してください。     不安になって検索した方の助けになれば幸いです。   (素人が推測で書いた記事です。間違ってたらご指摘ください)       以下、それに関する日記     引っ越しに伴って食洗機を取り付ける作業をしていたら、いつのまにかどこかから外れてたらしく、円筒形の小さな部品が1つ余ってしまいました。     食洗機の機種: NP-TA2-W   分岐水栓の型番: CB-SKH6   いずれもPanasonicの製品です。     これがなくても試運転は普通に動きましたが、不安でした。     ググってもこの円筒に関する情報がなかったので、形状からフィルター的なものかと思い、適当に分岐水栓に差し込んでみたら水が流れなくなってしまいました。   さらに悪いことに、円筒は分岐水栓から抜けなくなってしまいました。     ドライバーで引っ掛けて取り出そうとしたら、小さな円筒はさらに4つの部品に分解してしまいました。   外殻の円筒の側面が全然抜けなくて、泣きそうになりました。     苦戦の末、なんとか取り出すことに成功しました。   円筒の中にはバネが入っていたので、ここでようやくこの部品が弁であることを確信し、また底面を押すと1方向にのみ動くことに気がつきました。     この気づきは、私にかなりの感動をもたらしました。   めっちゃ気持ちよかったです。     この時私の感じた感動を伝えたくて日記を書きましたが、おそらく誰も読んでないですよね。まあ人生そんなものだと思います。     というわけで、今回は食洗機の分岐水栓の小さな円筒形の逆流防止弁についての日記でした。     ブログを書くと言ったのに書かない仕様、なんとかならないですかね...  








続きを読む