4.3.1 무차별 대입 전략 사용하기

첫 번째로 머릿속에 떠오르는 방법은 무차별 대입 전략(brute-force strategy)입니다. 무차별 대입 전략은 다음과 같은 방식으로 동작합니다.

합리적인 접근 방법인 것 같습니다. 하지만 문제가 있습니다. n개의 도시를 순회하는 투어는 총 (n-1)!개라는 것입니다. 방문할 도시가 다섯 개뿐이라면 총 4! = 24개 투어 일정을 만들고 이들의 거리를 재면 됩니다. 이 예제에서는 무차별 대입 전략을 충분히 사용할 만합니다. 그러나 방문해야 할 도시가 늘어나면 그에 따라 필요한 연산 횟수가 매우 크게 증가하기 때문에 무차별 대입 전략은 금세 쓸모없어집니다.

파이썬으로 무차별 대입 전략을 구현하는 방법을 살펴봅시다.

먼저, 투어 {1, 2, 3}은 도시 1, 도시 2, 도시 3을 거치는 투어를 의미합니다. 도시 간 이동 거리는 도시 간 최소 거리인 유클리드 거리라는 가정을 사용합니다.

먼저 세 가지 유틸리티 함수를 정의합니다.