Algorithm (2) 썸네일형 리스트형 Munkres 알고리즘 배정(assignment) 문제를 해결하기 위한 알고리즘입니다. Munkres 알고리즘의 핵심은 비용 행렬에서 같은 행 또는 같은 열에 있는 요소들에 대해 같은 값을 더하거나 빼는 것으로 비용 행렬의 일부를 변형하는 것입니다. 비용 그 자체를 구하는게 아니라 최소 또는 최대의 값을 구하는 것이기 때문에 가능한 연산입니다. Munkres 알고리즘의 입력은 2차원 행렬입니다. 출력은 배정의 최소 비용 및 매칭 정보(어느 행과 어느 열이 매칭되었는지)입니다. 배정 문제 또는 본 알고리즘에 입력되는 입력에 관한 정보는 이전 글을 참고해주시기 바랍니다. 배정(Assignment) 문제 (tistory.com) 배정(Assignment) 문제 이 문제의 자료 구조는 이분 그래프(bipartite graph)입니다... 배정(Assignment) 문제 이 문제의 자료 구조는 이분 그래프(bipartite graph)입니다. https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 2색변 이분 그래프의 예 그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite graph)란 모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그 ko.wikipedia.org 두 그룹으로 나눌 수 있고, 같은 그룹 내에서 연결되는 간선이 없습니다. 그리고 작업 하나 당 모든 작업자와 연결되는 완전 연결(fully connected) 형태입니다. 가장 대표적인 예시가 작업과 작업자 .. 이전 1 다음
