조합론적 최적화/Routing (1) 썸네일형 리스트형 중국인 우체부 문제 (Chinese Postman Problem) 어느 작은 마을의 우체부의 고민을 한번 들어봅시다. 이 마을은 하도 작아서 마을의 우체부는 이 사람 혼자입니다. 이 우체부의 하루 일과는 아침에 모든 우체통에 들어있는 편지나 소포를 우체국으로 가지고 오는 것으로 시작합니다. 잘 아시다시피 우체통은 길가에 듬성듬성 설치되어 있죠. 다시 말해, 마을의 모든 길을 최소한 한 번은 지나간다면 모든 우체통을 방문할 수 있게 됩니다. 이 우체부는 아침 일과를 빨리 끝내고 돌아와 아침 햇살을 쬐며 한 잔의 커피를 즐기는 낭만(?)적인 사람입니다. 그래서 어떻게 하면 가장 짧은 경로로 마을의 모든 길목을 지나칠 수 있을지 고민하고 있습니다. 과연 모든 길목을 최소 한 번씩은 지나는 가장 짧은 경로는 어떻게 구할 수 있을까요? 이 우체부가 고민하는 문제가 바로 중국인 .. 이전 1 다음
