적절한 투어 일정을 찾아내는 것이 가능할까요? 외판원이 이동해야 할 총 거리를 최소화하는 최적해는 무엇일까요?
외판원 문제에 등장하는 캐나다의 다섯 도시 간 거리는 다음 표에 정리되어 있습니다.
▼ 표 4-2 외판원 문제 - 캐나다의 다섯 도시 간 거리
|
|
오타와 |
몬트리올 |
킹스턴 |
토론토 |
서드버리 |
|
오타와 |
- |
199 |
196 |
450 |
484 |
|
몬트리올 |
199 |
- |
287 |
542 |
680 |
|
킹스턴 |
196 |
287 |
- |
263 |
634 |
|
토론토 |
450 |
542 |
263 |
- |
400 |
|
서드버리 |
484 |
680 |
634 |
400 |
- |
투어의 시작과 끝은 항상 같은 도시여야 합니다. 예를 들어, 오타와-서드버리-몬트리올-킹스턴-토론토-오타와를 거치는 투어의 이동 거리는 총 484 + 680 + 287 + 263 + 450 = 2,164입니다. 이 투어의 이동 거리가 다른 투어들보다 짧을까요? 이동 거리가 가장 짧은 최적의 투어 일정은 무엇일까요? 여러분이 직접 생각해 보고 계산해 보세요.