[알고리즘] Week 2: 이분 그래프 매칭과 최대 가중치 매칭

Day 1: 이분 그래프 매칭 (Bipartite Graph Matching)

• 강의 내용:
  • 이분 그래프의 개념
    • 이분 그래프란 무엇인가?
    • 이분 그래프의 특성 및 응용 사례
  • 이분 그래프 매칭의 개념
    • 매칭이란 무엇인가?
    • 최대 매칭 (Maximum Matching) 개념
  • 헝가리안 알고리즘 (Hungarian Algorithm)
    • 알고리즘의 원리
    • 알고리즘의 단계별 설명
  • 시간 복잡도 분석
    • 헝가리안 알고리즘의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 헝가리안 알고리즘 구현 및 예제

# 이분 그래프 매칭 예제: 헝가리안 알고리즘
def bpm(bpGraph, u, matchR, seen):
    for v in range(len(bpGraph[0])):
        if bpGraph[u][v] and not seen[v]:
            seen[v] = True
            if matchR[v] == -1 or bpm(bpGraph, matchR[v], matchR, seen):
                matchR[v] = u
                return True
    return False

def maxBPM(bpGraph):
    matchR = [-1] * len(bpGraph[0])
    result = 0
    for i in range(len(bpGraph)):
        seen = [False] * len(bpGraph[0])
        if bpm(bpGraph, i, matchR, seen):
            result += 1
    return result

# 예제 실행
bpGraph = [[0, 1, 1, 0, 0, 0],
           [1, 0, 0, 1, 0, 0],
           [0, 0, 1, 0, 0, 1],
           [0, 0, 0, 1, 1, 0],
           [0, 0, 0, 0, 0, 1],
           [0, 0, 0, 0, 0, 0]]

print("최대 매칭의 크기:", maxBPM(bpGraph))  # Output: 4

 

Day 2: 이분 그래프 매칭 심화

• 강의 내용:
  • 이분 그래프 매칭의 응용
    • 작업 할당 문제
    • 네트워크 연결 문제
  • 이분 그래프 매칭의 최적화 기법
    • 시간 복잡도 최적화 방법
    • 효율적인 데이터 구조 사용
  • 이분 그래프 매칭의 다양한 알고리즘
    • Hopcroft-Karp 알고리즘
  • 시간 복잡도 분석
    • Hopcroft-Karp 알고리즘의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 Hopcroft-Karp 알고리즘 구현 및 예제

# 이분 그래프 매칭 예제: Hopcroft-Karp 알고리즘
from collections import deque

def bfs(graph, pair_u, pair_v, dist):
    queue = deque()
    for u in range(len(graph)):
        if pair_u[u] == -1:
            dist[u] = 0
            queue.append(u)
        else:
            dist[u] = float('inf')
    dist[-1] = float('inf')
    while queue:
        u = queue.popleft()
        if dist[u] < dist[-1]:
            for v in graph[u]:
                if dist[pair_v[v]] == float('inf'):
                    dist[pair_v[v]] = dist[u] + 1
                    queue.append(pair_v[v])
    return dist[-1] != float('inf')

def dfs(graph, u, pair_u, pair_v, dist):
    if u != -1:
        for v in graph[u]:
            if dist[pair_v[v]] == dist[u] + 1:
                if dfs(graph, pair_v[v], pair_u, pair_v, dist):
                    pair_v[v] = u
                    pair_u[u] = v
                    return True
        dist[u] = float('inf')
        return False
    return True

def hopcroft_karp(graph):
    pair_u = [-1] * len(graph)
    pair_v = [-1] * len(graph[0])
    dist = [0] * (len(graph) + 1)
    matching = 0
    while bfs(graph, pair_u, pair_v, dist):
        for u in range(len(graph)):
            if pair_u[u] == -1:
                if dfs(graph, u, pair_u, pair_v, dist):
                    matching += 1
    return matching

# 예제 실행
graph = [[0, 1, 1, 0, 0, 0],
         [1, 0, 0, 1, 0, 0],
         [0, 0, 1, 0, 0, 1],
         [0, 0, 0, 1, 1, 0],
         [0, 0, 0, 0, 0, 1],
         [0, 0, 0, 0, 0, 0]]

print("Hopcroft-Karp 알고리즘에 의한 최대 매칭의 크기:", hopcroft_karp(graph))  # Output: 4

 

Day 3: 최대 가중치 매칭 (Maximum Weight Matching)

• 강의 내용:
  • 최대 가중치 매칭의 개념
    • 가중치 그래프에서의 매칭
    • 최대 가중치 매칭의 응용 사례
  • 최대 가중치 매칭 알고리즘
    • 벨만-포드 알고리즘
    • 프림 알고리즘
  • 시간 복잡도 분석
    • 최대 가중치 매칭 알고리즘의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 최대 가중치 매칭 알고리즘 구현 및 예제

# 최대 가중치 매칭 예제: 벨만-포드 알고리즘
def bellman_ford(graph, src):
    dist = {node: float('inf') for node in graph}
    dist[src] = 0

    for _ in range(len(graph) - 1):
        for u in graph:
            for v, weight in graph[u].items():
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight

    for u in graph:
        for v, weight in graph[u].items():
            if dist[u] + weight < dist[v]:
                print("Graph contains negative weight cycle")
                return None

    return dist

# 예제 실행
graph = {
    'A': {'B': -1, 'C': 4},
    'B': {'C': 3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}

distances = bellman_ford(graph, 'A')
if distances:
    print("벨만-포드 알고리즘에 의한 최단 경로:", distances)

 

Day 4: 최대 가중치 매칭 심화

• 강의 내용:
  • 최대 가중치 매칭의 응용
    • 네트워크 설계 및 최적화
    • 데이터 클러스터링
  • 고급 최대 가중치 매칭 알고리즘
    • 블로섬 알고리즘 (Blossom Algorithm)
  • 시간 복잡도 분석
    • 블로섬 알고리즘의 복잡도 및 효율성
• 실습:
  • 파이썬을 사용한 블로섬 알고리즘 구현 및 예제

# 블로섬 알고리즘을 사용한 최대 가중치 매칭 예제
import networkx as nx

def maximum_weight_matching(graph):
    return nx.max_weight_matching(graph, maxcardinality=True)

# 예제 실행
G = nx.Graph()
G.add_edge('A', 'B', weight=1)
G.add_edge('A', 'C', weight=4)
G.add_edge('B', 'C', weight=3)
G.add_edge('B', 'D', weight=2)
G.add_edge('C', 'D', weight=5)

matching = maximum_weight_matching(G)
print("블로섬 알고리즘에 의한 최대 가중치 매칭:", matching)

 

Day 5: 매칭 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • 이분 그래프 매칭 및 최대 가중치 매칭 문제 해결
  • 매칭 알고리즘의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 이분 그래프에서 최대 매칭을 찾으세요.
2. 주어진 가중치 그래프에서 최대 가중치 매칭을 찾으세요.

 

Day 6: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 대규모 작업 할당 문제 해결 시스템 개발
2. 실시간 네트워크 최적화 시스템

### 프로젝트 요구사항 예시
1. 대규모 작업 할당 문제 해결 시스템:
   - 대규모 작업 데이터셋 입력 및 저장
   - 매칭 알고리즘을 통한 최적화
   - 최적화 결과 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 매칭 알고리즘 구현 (이분 그래프 매칭, 최대 가중치 매칭 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 매칭 알고리즘, 특히 이분 그래프 매칭과 최대 가중치 매칭의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!