NetworkXのbipartite(2部マッチング)でドラクエウォークのアイテムをマッチングする

「問題解決力を鍛える！アルゴリズムとデータ構造」という本で「何人かの男性と女性とがいて，ペアになってもよいという２人の間には辺が張られているものとします．できるだけ多くのペアを作ろうとしたときに，最大で何組のペアを作ることができるでしょうか」という、いわゆる二部マッチング問題が紹介されていて、これは私がはまっているドラクエウォークのアイテム組み合わせに使えるんじゃないかと思った。

PythonではNetworkXというライブラリに2部マッチングが含まれているので、これで試してみようと思う。u++の備忘録を参考にした。

Google Colaboratoryでは特に追加インストールすることなく試すことができた。

import networkx
from networkx.algorithms import bipartite
import matplotlib.pyplot as plt

扱うデータと、重みづけ関数を下記のように定義しておく。ドラクエウォークは４人パーティだが簡単のため２人とし、片方に打撃系、片方に呪文の能力を高めたいという場合を想定している。メンバーが欲しいと思っている属性が武器に備わっていれば重みが加算される。

members = [
        ["ヒャド属性とくぎダメージ","物質系への耐性"],
        ["ヒャド属性じゅもんダメージ"],
]
arms = [
        {"name":"ガイアーラのよろい上","ヒャド属性とくぎダメージ":5},
        {"name":"フォースコート上","ヒャド属性とくぎダメージ":1},
        {"name":"蒼竜のよろい上","ヒャド属性とくぎダメージ":3},
        {"name":"書聖のはおり","ヒャド属性じゅもんダメージ":3,"物質系への耐性":5},
        {"name":"アリアハンの服上","ドラゴン系への耐性":1,"スライム系への耐性":3},
        {"name":"光のよろい","ドラゴン系への耐性":5},
]

def omomi(member,arm):
  val = 0
  for j in members[member]:
    if j in arms[arm-len(members)]:
      val = val + arms[arm-len(members)][j]
  return val

ノード０～１をメンバー、ノード２～７を武器ということにしてノードの追加、エッジの追加（同時に重みづけ）を行い、max_weight_matchingで最大マッチングを行う。

members_size = len(members)
arms_size = len(arms)

member_group = range(members_size)  # 0～1
arm_group = range(members_size,arms_size+members_size) # 2～7

g = networkx.Graph()
g.add_nodes_from(job_group, bipartite=1)
g.add_nodes_from(arm_group, bipartite=0)

for i in job_group:
  for j in arm_group:
    g.add_edge(i,j,weight=omomi(i,j))

d = networkx.max_weight_matching(g)

ここから先は描画。ノードの表示位置を適当に決め、最大マッチングに含まれていないエッジは削除する。

pos = {}
for i in job_group:
  pos[i] = (1,i)
for j in arm_group:
  pos[j] = (2,j-jobs_size)

for (i, j) in list(g.edges()):
    if (i, j) not in d:
        if (j, i) not in d:
            g.remove_edge(i,j)

networkx.draw_networkx(g,pos)
networkx.draw_networkx_edges(g,pos)
plt.show()

出力したグラフがこちら。１人目（ノード０）はガイアーラのよろい（ノード２）、２人目（ノード１）は書聖のはおり（ノード５）を選んでおり、想定とも合っている。

ということで、NetworkXを使ってお手軽に二部マッチングを実装できた。重み付けだけ考えれば、あとは全部やってくれるというところがいい。