[C#윈폼132] Hungarian Algorithm(Maximum Weighted Matching)을 이용해서 최적해 찾아보기! 그래프이론(Graph Theory)(녹칸다/포로리야공대가자)

 

Hungarian Algorithm(Maximum Weighted Matching)을 이용해서 최적해 찾아보기! 그래프이론(Graph Theory)(녹칸다/포로리야공대가자)
-이번편은 녹칸다가 그냥 생각이 나서 해보는 그래프 이론에 대한 내용을 C#윈폼으로 설명해보는 것이다!
-그래프 이론을 이용해서 최적해를 탐색하는 방법에 대해서 알아보도록 하자!
-녹칸다는 Bipartite Graph로 표현되는 모델에서 Maximum Weighted Matching혹은 Minimum Weighted Matching을 이용해서 2개의 그룹간 최적의 쌍을 찾아내는 방법에 대해서 C#윈폼으로 시각화할 예정이다!
-Bipartite Graph란 2개의 그룹이 있을때 각각의 그룹간에는 관계가 없고 서로다른 그룹간에만 관계가 있는 형태를 말한다!
-그리고 2개의 그룹의 노드 갯수가 동일하고 weighed edge가 N:N으로 구성이 되었을때 Hungarian Algorithm을 이용해서 최적해를 찾을 수 있다!
-만약 우리의 현실문제를 그래프 이론으로 모델링 할 수 있다면, 그래프 이론에서 가진 기법에 따라서 최적의 결과를 찾을 수 있는 것이다!
-그러나 최적해를 탐색하는 알고리즘에 대한 설명은 아니고 알고리즘은 구현된 결과를 추가해서 활용한다!
-녹칸다가 해결해보고자 하는 현실? 문제는 아래와 같다!
-(1)녹칸다가 5:5 미팅을 주선했다! 남녀 각각에게 호감도를 0~100점으로 부여하도록했을때 모든 사람이 만족할만한 커플 쌍을 제시해보라!
-(2)녹칸다는 큰 회사의 인사팀장이다! 5명의 신입직원과 5개의 직무가 있을때 평가 결과에 따라 어떻게 배정하면 좋을지 제시해보라!
-(3)필드에 몬스터가 100마리 있다! 녹칸다의 용병이 100명있다! 랜덤하게 200개의 유닛이 배치되었을때 녹칸다의 100명의 용병이 어떤 몬스터를 공격하면 좋을지 알아보자!(가까운 몬스터를 공격하면 되겠지~~?)

 

C#프로젝트

example132.zip

0.95MB