| [ QuizWit ] in KIDS 글 쓴 이(By): birdeee (별사랑이) 날 짜 (Date): 2003년 11월 11일 화요일 오후 06시 07분 18초 제 목(Title): Re: 정치인 문제 포크레인이라는 것은 인정합니다만 정치인들이 함께 탄 다고 하면 조금 얘기가 됩니다. 정치인들이라고 하면 300명을 300개의 그룹으로 나누지 않아도 되기만 해도 다행 아니겠습니까? 같은 당이라고 해도 서로 함께 있어도 꺼림찍한게 없다는 의미는 아닐것이니까요. 서로 싫어하는 정도를 Weight로 표시한다면 (꼭 1, 0이 아니고 0과 1 사이의 실수로 한다든가...) 예를 들어 50개의 그룹으로 나누었을 때 Cost를 Minimize하는 Graph Partitioning 문제가 의미가 있겠죠. 하필이면 왜 정치인이 주제인지 모르지만, 또 구체적인 응용이 어떤 것이 있는지 모르지만 이런 Application은 딱히 Graph Coloring으로 적용한다는 것이 어색하다는 생각에 이런 생각을 해봤습니다. 더구나 지금 풀고 계신다니까... 가능하면 정치인은 초청 안하는게 좋긴 한데 어쩔 수 없이 부족한 일정에 초청해야 한다면 썰렁한 분위기를 minimize 하는 쪽으로 가야 하지 않겠습니까? 그게 더 현실적이고요. 또 Graph Partitioning에는 쓸만한 Heuristic이 꽤 있습니다. 필요하시다면 쑥스럽지만 제가 비슷한 문제를 푼 적이 있으니 참조할 문헌을 알려 드릴 수도 있습니다. 그 논문 보다는 Reference가 더 유용할 것이지만요. ==================================== 다시 읽다 보니, 예를 들어 성격 안좋은 다섯 명의 정치인이 서로간에 Full-mesh 형태로 사이가 안좋다면 일단 Infeasible 하지 않나요? Formulation을 고쳐 보시는게 어떨까요? 제시하신 Greedy Algorithm을 4일이라는 제약을 없애고 고쳐본다면 이렇게 하는게 나을 것 같습니다. 첫날 초대할 명단 고르는 법: 1. 현재 정치인들 가운데 가장 많은 사람들과 사이가 안좋은 사람을 골라 첫날에 초대한다. 그리고 그 사람과 사이 안좋은 사람들은 모두 첫날 후보에서 제외한다. 2. 남은 정치인 가운데 역시 가장 많은 사람들과 사이가 안좋은 사람을 골라 첫날에 초대한다. 마찬가지 요령으로 그 사람과 사이 안좋은 사람들은 모두 후보에서 제외한다. 3. 이렇게 끝까지 해서 더이상 후보가 없을 때까지 계속한다. 이와 마찬가지 방식으로 둘째날 초대할 명단을 고른다. 세째날, 네째날... 모두 초대될 때까지 한다. |