헝가리안 알고리즘

헝가리안 알고리즘은 일반적으로 이분 그래프에서 최대 가중 매칭을 찾는 문제로 표현되며, 이를 해결하기 위한 몇 가지 알고리즘이 있습니다. 그 중에서 대표적인 것은 Kuhn-Munkres 알고리즘이며, 이를 사용하여 헝가리안 알고리즘을 직접 구현할 수 있습니다.

아래는 Kuhn-Munkres 알고리즘을 사용하여 헝가리안 알고리즘을 직접 구현한 코드입니다. 이 코드에서는 최소 비용 매칭을 찾기 위해 최대 가중 매칭을 찾는 방식으로 구현되어 있습니다.

import numpy as np

def hungarian_algorithm(cost_matrix):
    cost_matrix = np.array(cost_matrix)
    num_rows, num_cols = cost_matrix.shape

    # Step 1: Subtract the smallest entry in each row from all the other entries in that row.
    cost_matrix -= cost_matrix.min(axis=1)[:, np.newaxis]

    # Step 2: Subtract the smallest entry in each column from all the other entries in that column.
    cost_matrix -= cost_matrix.min(axis=0)

    # Step 3: Cover each column with the fewest possible lines.
    covered_cols = set()
    covered_rows = set()
    while len(covered_rows) + len(covered_cols) < num_rows + num_cols:
        # Find the minimum uncovered entry.
        min_val = np.inf
        for i in range(num_rows):
            if i not in covered_rows:
                for j in range(num_cols):
                    if j not in covered_cols:
                        min_val = min(min_val, cost_matrix[i, j])

        # Subtract the minimum uncovered entry from all the uncovered entries.
        for i in range(num_rows):
            if i not in covered_rows:
                for j in range(num_cols):
                    if j not in covered_cols:
                        cost_matrix[i, j] -= min_val

        # Cover the rows and columns with the fewest uncovered entries.
        min_uncovered_row = min(range(num_rows), key=lambda x: sum(1 if cost_matrix[x, j] == 0 else 0 for j in range(num_cols)))
        min_uncovered_col = min(range(num_cols), key=lambda x: sum(1 if cost_matrix[i, x] == 0 else 0 for i in range(num_rows)))

        if sum(1 if cost_matrix[min_uncovered_row, j] == 0 else 0 for j in range(num_cols)) <= sum(1 if cost_matrix[i, min_uncovered_col] == 0 else 0 for i in range(num_rows)):
            covered_rows.add(min_uncovered_row)
        else:
            covered_cols.add(min_uncovered_col)

    # Step 4: Find a zero in the cost matrix. If there is no starred zero in its row or column,
    # star the zero. Repeat for each zero.
    starred_zeros = set()
    for i in range(num_rows):
        for j in range(num_cols):
            if cost_matrix[i, j] == 0 and i not in starred_zeros and j not in starred_zeros:
                starred_zeros.add(i)
                break

    # Step 5: Cover each column containing a starred zero. If K columns are covered, the starred
    # zeros describe a complete set of unique assignments.
    covered_cols = set()
    for i in starred_zeros:
        for j in range(num_cols):
            if cost_matrix[i, j] == 0 and j not in covered_cols:
                covered_cols.add(j)

    # Step 6: Use the smallest uncovered entry to modify the cost matrix.
    min_val = min(cost_matrix[i, j] for i in range(num_rows) for j in range(num_cols) if i not in covered_rows and j not in covered_cols)
    for i in range(num_rows):
        for j in range(num_cols):
            if i not in covered_rows and j in covered_cols:
                cost_matrix[i, j] += min_val
            elif i in covered_rows and j not in covered_cols:
                cost_matrix[i, j] -= min_val

    # Step 7: Erase all covered rows and columns. Repeat until all entries are covered.
    while len(starred_zeros) < num_rows:
        # Find a non-covered zero and prime it.
        for i in range(num_rows):
            if i not in covered_rows:
                for j in range(num_cols):
                    if j not in covered_cols and cost_matrix[i, j] == 0:
                        cost_matrix[i, j] = -1
                        covered_rows.add(i)
                        covered_cols.add(j)

                        # Find the starred zero in the same column.
                        star_in_col = next((x for x in starred_zeros if x != i and cost_matrix[x, j] == 0), None)
                        if star_in_col is not None:
                            starred_zeros.remove(star_in_col)
                            covered_rows.remove(star_in_col)
                            covered_cols.remove(j)
                            break

    # Return the assignment pairs.
    assignment_pairs = [(i, j) for i in range(num_rows) for j in range(num_cols) if cost_matrix[i, j] == 0]
    return assignment_pairs

# 예시 사용
cost_matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

assignment_pairs = hungarian_algorithm(cost_matrix)
print("Assignment Pairs:", assignment_pairs)

이 코드는 Kuhn-Munkres 알고리즘을 사용하여 헝가리안 알고리즘을 직접 구현한 예시입니다. 이 구현에서는 최소 비용 매칭을 찾기 위해 최대 가중 매칭을 찾는 방식으로 작성되어 있습니다. 비용 행렬 cost_matrix를 입력으로 받아 최적의 할당 쌍을 찾아 반환합니다.