일반적인 문제와 실행 방법

가중치 매칭 문제

가중치 매칭 문제는 「최대 가중치 매칭 문제, 최대 가중치 최대 매칭 문제, 최대 가중치 완전 매칭 문제, 최소 가중치 최대 매칭 문제, 최소 가중치 완전 매칭 문제」 등의 총칭이다.


가중치 매칭 문제
문제 유형
일치하는 변 수


최대 가중치 매칭 문제
최대화
선택

최대 가중치 최대 매칭 문제
최대화
최대 매칭 문제와 같아야 함

최대 가중치 완전 매칭 문제
최대화
점수의 절반이어야 함

최소 가중치 최대 매칭 문제
최소화
최대 매칭 문제와 같아야 함

최소 가중치 완전 매칭 문제
최소화
점수의 절반이어야 함

가중치는 모두 0 이상으로 한다.

최소 가중치 매칭 문제는 하늘이 명백한 최적 해이므로 일반적으로 고려되지 않습니다.

「최대 가중치 매칭 문제와 최대 가중치 최대 매칭 문제와 최소 가중치 최대 매칭 문제」에 있어서 가중치가 모두 1일 때, 단순히 「최대 매칭 문제 」이라고 한다.

"최대 가중치 완전 매칭 문제와 최소 가중치 완전 매칭 문제"에서 가중치가 모두 1일 때, 단순히 "완전 매칭 문제"라고 한다.

최소 가중치 최대 매칭 문제와 최소 가중치 완전 매칭 문제는 해당 가중치를 "가중치 최대 - 해당 가중치"로 바꾸면 최대 가중치 최대 매칭 문제와 최대 가중치 완전 매칭 문제에 귀착할 수 있다.

최대 가중치 완전 매칭 문제는 최대 가중치 최대 매칭 문제의 해가 완전 매칭인 경우에만 해가 된다.

이러한 점에서 최대 가중치 매칭 문제와 최대 가중치 최대 매칭 문제의 해법이 있으면 된다.

최대 가중치 매칭 문제는 아래의 max_weight_matching (에드몬스법)으로 풀 수 있다.

최대 가중치 최대 매칭 문제를 해결하는 경우 아래의 max_weight_matching 에서 maxcardinality=True 를 지정하면 된다.

그래프가 2부 그래프인 경우, 일반 그래프보다 고성능(헝가리법 등) 알고리즘이 존재한다.

최대 가중치 매칭 문제

무향 그래프 $G=(V,E)$에 대해 각 변 $e\in E$의 가중치 $w(e)$가 주어졌을 때, $\sum_{e\in M}{w( e)}$가 가장 큰 매칭 $M$를 찾아라.

실행 방법 (최대 가중치 매칭 문제)

usage

Signature: nx.max_weight_matching(G, maxcardinality=False)
Docstring:
Compute a maximum-weighted matching of G.

A matching is a subset of edges in which no node occurs more than once.
The cardinality of a matching is the number of matched edges.
The weight of a matching is the sum of the weights of its edges.

파이썬

# CSVデータ
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe)[0]
d = nx.max_weight_matching(g)
pos = networkx_draw(g)
nx.draw_networkx_edges(g, pos, width=3, edgelist=[(i, j) for i, j in d])
plt.show()
print(d)

결과

{5: 1, 1: 5, 0: 2, 2: 0, 4: 3, 3: 4}

파이썬

# pandas.DataFrame
from ortoolpy.optimization import MaxWeightMatching
MaxWeightMatching('data/edge0.csv')

node1
node2
capacity
weight




0
0
2
2
4


1
1
5
2
5


2
3
4
2
4



파이썬

# 乱数データ
import networkx as nx, matplotlib.pyplot as plt
from ortoolpy import networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
for i, j in g.edges():
    g.adj[i][j]['weight'] = 1
d = nx.max_weight_matching(g)
pos = networkx_draw(g, nx.spring_layout(g))
nx.draw_networkx_edges(g, pos, width=3, edgelist=[(i, j) for i, j in d])
plt.show()

데이터

data/node0.csv

data/edge0.csv