[포럼] mcbm 개빡치네

글 보러 와줘서 고마워 gnr이랑 관련없는 알고리즘 설명이지만 그냥 심심해서 써봄

mcbm 이란 뭐냐 -> maximum cardinality bipartite matching -> 토나오지? 한국어론 -> 최대 이분 매칭? 정도로 번역이 되

자 여기서 이분? 이분이 뭘까?

이분이란 이분저분 할때 쓰는게 아니라 二分, 이분할 할때의 이분이야.즉, 도형을 그려봤을때 서로 다른 두개의 집합으로 나뉜다는 뜻이지.

요로코롬 말이야

여기서 중요한 점은, 서로 같은 색으로 칠해진 애들끼리는 연결되어선 안된다는 거야. "서로 안이어짐" 을 기준으로 니편 내편을 나누는 거라 그래.

자 그럼 이제 매칭이 뭘까?

위 그래프에서 (철수 - 수학) , (영희- 국어) 같이 서로 다른 두 집합의 원소들이 연결된 것을 말해

다만 이제 중요한 것은 (철수- 수학), (세희- 수학) 같이 서로 공유되는 원소(수학) 이 없어야 한다는거지.

커플이랑 비슷하다고 보면 편해. 파랑은 남자 주황은 여자, 같은 여자 상대로 남자 두명이 데이트하면 싸움 나듯이( 반대도 마찬가지잖아?) -> { 뭐 애초에 나같은 모쏠은 저어기 아예 나가는 선도 없겠지만 큐ㅠㅠㅠ }

자 이제 우리는 이분(bipartite) 랑 매칭(matching) 을 커버했어.

이제 남은건 maximum cardinality 야. 이건 최대갯수라고 해석하면 돼.

요약:

mcbm -> maximum cardinality bipartite matching ->

최대갯수이분그래프매칭. -> 이분 그래프에서 최대 개수의 매칭을 찾아라.

되게 쓸데가 적어 보이지?

사실 mcbm 자체만 두고 보면 남자집합이랑 여자집합이 주어지고 서로 간의 선호도가 있을 때 최대 갯수의 생성 가능 커플 개수 구하는 정도의 쓰잘데기 없는 작업밖에 못하는게 맞아.

다만, 우리는 기존 문제들을 mcbm으로 변형 시켜서 여러 가지 문제를 풀 수 있어.

mcbm변환에 가장 중요한 것은 어떻게 기존 문제를 이분 그래프로 변환 할 수 있는지야. 어떤 상황을 이분하는거랑 비슷하지.

예시도 상당히 많아

등등등

가령 이런 문제도 mcbm으로 줄일 수 있어

[ 추후 그래프 변환 추가 예정 ]

어떤 항공사가 비행기를 몇 대 사야하는지 결정해야하는데, 그 결정을 운항해야하는 노선에 따라서 결정할려고 해.

항공사 입장에선 최소갯수의 비행기를 사고 싶어 하지.

항공사에게 주어진 건

1. 운항해야 하는 항공편 의 출발시간, 도착시간, 출발지, 도착지

2. 각 비행장마다 걸리는 정비 및 재급유 시간

항공사가 쓰는 비행기 갯수를 줄일려고 추가적인 운항을 할 수 도 있다라고 가정할때

우리는

도형의 노드(동그라미들) 을 운항해야 하는 항공편.

정확하게 말하자면

(집합 1: 시작 항공편 | 집합 2: 다음 출발 항공편) 2개의 집합(이분그래프 형성)을 형성하고

{여기서 시작 항공편 = 다음 출발 항공편}

도형의 엣지(동그라미 간 선분)를 해당 항공편의 도착지에서 다른 항공편의 출발지로 이동 시 필요시간 + 총 정비시간 (이) 다른 항공편의 출발 예정 시각보다 일찍 끝나는 경우(<=) 잇는다고 가정하면

mcbm 솔루션을 통해서 우리는 최대한 많은 {시작 항공편, 다음 시작 항공편}들끼리의 매칭을 구할 수 있게 돼.

매칭의 특성상 매칭 간 서로 공유되는 노드가 없어야 한다고 했지? 이건 모든 매칭에서 겹치는 (시작 항공편, 다음 출발 항공편) 세트는 없다는 거야. 즉, 모든 연결이 독자적이라는 거지

조금 더 거시적으로 예시를 들어 보자면, 예를 들어 (서울 - 나고야)

(나고야- LA) 매칭이 결과값으로 나왔다고 가정을 하면

항공사는 비행기 하나로 서울 - 나고야 - LA, 2개의 노선을 운행하면 되는거야.

N 개의 항공편이 주어지면 비행기 N 개면 전부 해결 할 수 있겠지? 이제 여기서 mcbm이 구한 비행기 하나로 해결 가능한 (최대)갯수의 항공편 만큼 줄이면, 우리는 그 모든 항공편들을 최소로 운행할 수 있는 비행기 대수를 구할 수 있는거야.

여기서 mcbm 솔루션을 언급했는데, mcbm을 풀려고 시도하는 알고리즘들은 정말 많아. 사실 mcbm의 세부 종류도 더 많은데( weighted, unweighted ) 그 외 MCM 이라고 이분그래프가 아닌 모든 그래프에서 최대 매칭 개수 구하는 등...

이건 너무 많으니까 각케이스별 관련 사진 하나만 하나 올릴테니까 궁금하면 찾아봐

이상 뻘글이였다

- dc official App

댓글 5