위키 에서 완벽한 매칭의 개념 :
완벽한 일치는 그래프의 모든 정점과 일치하는 일치입니다. 즉, 그래프의 모든 정점이 일치하는 가장자리에 입사하는 경우 일치가 완벽합니다.
따라서 최소 가중치 퍼펙트 매칭은 가중치가 가장 작은 조합 중 하나입니다. 처음에 내 아이디어는 탐욕스러운 알고리즘을 따르고 있습니다 (주의 : 내 그래프가 완성되었으며 각 정점에는 나머지 정점에 대한 가장자리가 있음).
그래프에서 하나의 정점을 선택하고 각 단계에서 가장 가까운 인접 정점을 찾은 다음 드롭하고 그래프에 정점이 없을 때까지 루프를 수행합니다. 그러나 n을 계산하지 않으면 최적이 아닙니다! 타임스:
while odd_vert:
v = vertices.pop()
length = float("inf")
closest = 0
for u in odd_vert:
if graph[v][u]["weight"] < length:
length = graph[v][u]["weight"]
closest = u
graph_minimum_match.add_edge(v, closest, weight = length)
networkx에서 일부 기능을 찾았지만 그래프가 두 부분으로 나뉘어져 있는지 묻습니다.
nx.algorithms.bipartite.matching.minimum_weight_full_matching(G, top_nodes=None, weight='weight')
게다가, 일치하는 최대 무게를 찾으십시오.
nx.algorithms.matching.max_weight_matching(G, maxcardinality=True)
그런 다음 꽃 신앙 전파를 보여주는 기사를 검색했는데 달성 할 수 있을지 모르겠습니다.
-1을 곱하거나 최대 가중치에서 빼서 그래프의 모든 간선 가중치를 반전 할 수 있습니다. 그런 다음이 변환 된 그래프에서 최대 완전 일치를 찾을 수 있다면 해당 일치는 원래 그래프에서 최소화됩니다.
nx.algorithms.matching.max_weight_matching로 maxcardinality설정된 True경우 일치하는 항목이있는 경우에만 완전한 일치를 허용 함을 의미하는 매개 변수 가 있습니다. 따라서 networkx변환 된 그래프 에서 함수를 호출하고 실제로 일치가 완료되었는지 확인할 수 있습니다. 그렇다면이 일치는 원하는 결과입니다. 그렇지 않은 경우 완벽한 매칭이 불가능합니다.
꼭지점이 짝수 인 완전한 그래프에서 완전한 일치는 물론 항상 가능합니다. 또한 변환 된 그래프에 양의 가중치 만있는 경우 (예 : 빼기 기반 변환 사용) 최대 가중치 그래프는 항상 최대 카디널리티를 갖습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다