자, 이제 무차별 대입 전략을 이용해 최적의 투어를 생성해 봅시다.
[in :]
import time
from collections import Counter
def tsp(algorithm, cities):
t0 = time.perf_counter()
tour = algorithm(cities)
t1 = time.perf_counter()
assert Counter(tour) == Counter(cities) # 모든 도시는 한 번만 등장해야 합니다.
visualize_tour(tour)
print("{}:{} cities = tour length {:.0f} (in {:.3f} sec)".format(name(algorithm), len(tour), distance_tour(tour), t1 - t0))
def name(algorithm): return algorithm.__name__.replace('_tsp', '')
tsp(brute_force, generate_cities(10))
[out:]
brute_force: 10 cities => tour length 1107 (in 16.737 sec)
이 코드에서는 도시 10개를 생성했습니다. n = 10이라면 모든 가능한 조합의 개수는 (10-1)! = 362,880이 됩니다. n이 커지면 조합의 개수가 급격히 늘어나므로 무차별 대입 전략을 사용하기 어렵습니다.