03. 모든 도시를 한 번씩: 해밀턴 회로와 파이썬 외판원(TSP)

1. 학습 목표 (Learning Objectives)

  • 선(길)이 아니라 각자 거점 도시(점, Node) 들을 한 번씩만 순회해야 하는 전혀 새로운 룰, ‘해밀턴 회로(Hamiltonian Circuit)’ 를 이해합니다.
  • 컴퓨터 과학과 택배 회사 배차 알고리즘의 최대 악몽 난제인 외판원 문제(TSP, Traveling Salesperson Problem) 구조를 파악하고, 파이썬 itertools의 브루트포스 팩토리얼 무차별 대입 코드를 실습합니다.

2. 오일러를 배신한 길 찾기

오일러 회로는 “세상의 모든 도로(선)에 눈치우기 차를 다 보내고 싶은데 중복하면 기름 아까워!”라는 상황이었습니다. (선 중심 어택)

하지만 현금 수송 차량이나 택배 기사는 길 자체에 볼일이 없습니다. 그들은 길바닥이 어떻든 간에 “은행 지점 5곳”, “택배 배송지 집 10곳(점, Node)” 에만 무사히 배송품을 내려주고 다시 우체국 본진으로 귀환하면 장땡입니다.

  • 해밀턴 경로(Path): “모든 길은 알 바 아니고, 모든 도시(점)를 중복 방문 없이 딱 1번씩만 다 밟고 도장 찍을 것!”
  • 해밀턴 회로(Circuit): “모든 도시를 찍고 나서 반드시 내 출발지 무베이스 원점 으로 동그랗게 복귀 사이클을 닫을 것!”

3. 컴퓨터 과학의 최악 폭탄, TSP 팩토리얼 딜레마

오일러는 “그래프의 홀수점 갯수만 세어봐”라는 1초짜리 명쾌한 공식을 줬지만, 아일랜드 수학자 윌리엄 로언 해밀턴(William Rowan Hamilton)이 던진 해밀턴 회로 문제는 “이 그래프가 과연 한바퀴 도시 순회 조건이 되는지 단박에 알아낼 일반화된 수학 공식이 아예 없다!” 라는 충격적인 팩트를 남겼습니다.

심지어 이 도시 간의 이동 거리가 저마다 다를 때 “가장 짧은 기름값으로 5곳 다 찍고 오기” 미션으로 변질하게 되면, 이 문제를 악명 높은 방문 판매원 문제(TSP) 라고 부릅니다. 현대 컴퓨터는 이걸 풀 공식이 없어서, 무조건 무식하게 모든 경로의 묶음을 죄다 뽑고 거리값을 덧셈해 보는 노가다 무차별 대입(Brute-Force) 을 실행해야 합니다.

  • 도시 5곳 순회 조합 계산량 = $(5-1)! / 2 = 12$ 번 검사. 컴퓨터가 피식 비웃습니다.
  • 도시 10곳 순회 = $181,440$ 번 검사. 컴퓨터가 침착하게 0.1초 만에 풉니다.
  • 도시 60곳 순회 = $6.9 \times 10^{79}$ 번 검사. 컴퓨터가 잼버리 걸려서 우주의 나이가 지나도록 연산해도 답이 안 나옵니다! 폭발합니다.

4. 파이썬 택배 배송 브루트포스 봇 (Python TSP)

일단 파워에 덜 밀리는 도시 4곳($A, B, C, D$)으로 택배 배달을 돌면서, 출발지인 물류창고(Home)로 무사히 복귀하는 모든 해밀턴 회로의 조합(Permutation)을 파이썬 itertools 엔진으로 강제 스캔 추출해 보겠습니다.

import itertools

def brute_force_tsp(cities):
    """
    택배 기사가 각 도시를 무중복으로 한 번씩 돌고 다시 출발 도시로 
    되돌아오는 해밀턴 회로 전체 노선(Routing) 목록을 뽑아내는 무차별 스캐너.
    """
    print("-" * 50)
    print(f"📦 [외판원(TSP) 택배 배송 노선망 탐색 가동]")
    print(f"✔️ 타겟 도시 목록: {cities}")
    
    # 1. 효율을 위해 무조건 리스트의 맨 앞 [0] 번째 도시를 '본부(출발점)'으로 고정!
    start_city = cities[0]
    rest_cities = cities[1:]
    
    print(f"🏠 물류 본부 창고(Home): [{start_city}]")
    print("-" * 50)
    
    # 2. itertools.permutations 으로 남은 도시들의 모든 순서 배열(순열) 폭발 나열
    all_routes = list(itertools.permutations(rest_cities))
    
    total_valid_circuits = 0
    print("🛣️ [탐색된 가능한 해밀턴 회로 노선 스케줄]")
    
    for route in all_routes:
        total_valid_circuits += 1
        # 리스트 언패킹 및 스트링 조작으로 경로 시각화
        # 궤적: 출발 -> 중간 도시들 -> 다시 출발
        route_str = " ➔ ".join(route)
        full_circuit = f"🕸️ 루트 {total_valid_circuits:02d}: [{start_city}] ➔ {route_str} ➔ [{start_city}]"
        print(full_circuit)
        
    print("-" * 50)
    print(f"🔥 노가다 연산 종료. 팩토리얼 계산({len(cities)-1}!)을 통해 ")
    print(f"총 [{total_valid_circuits}] 개의 무중복 링(Circuit) 코스를 스캔했습니다.")
    print("만약 각 길에 거리(Cost)가 있었다면 여기서 최소 합 다이어트 판독을 추가하면 됩니다!")

# 시뮬레이션: 도시 4개 지역 렌더링
target_nodes = ['Home_A', 'City_B', 'City_C', 'City_D']
brute_force_tsp(target_nodes)

터미널 실행 콘솔 렌더링:

--------------------------------------------------
📦 [외판원(TSP) 택배 배송 노선망 탐색 가동]
✔️ 타겟 도시 목록: ['Home_A', 'City_B', 'City_C', 'City_D']
🏠 물류 본부 창고(Home): [Home_A]
--------------------------------------------------
🛣️ [탐색된 가능한 해밀턴 회로 노선 스케줄]
🕸️ 루트 01: [Home_A] ➔ City_B ➔ City_C ➔ City_D ➔ [Home_A]
🕸️ 루트 02: [Home_A] ➔ City_B ➔ City_D ➔ City_C ➔ [Home_A]
🕸️ 루트 03: [Home_A] ➔ City_C ➔ City_B ➔ City_D ➔ [Home_A]
🕸️ 루트 04: [Home_A] ➔ City_C ➔ City_D ➔ City_B ➔ [Home_A]
🕸️ 루트 05: [Home_A] ➔ City_D ➔ City_B ➔ City_C ➔ [Home_A]
🕸️ 루트 06: [Home_A] ➔ City_D ➔ City_C ➔ City_B ➔ [Home_A]
--------------------------------------------------
🔥 노가다 연산 종료. 팩토리얼 계산(3!)을 통해 
총 [6] 개의 무중복 링(Circuit) 코스를 스캔했습니다.
만약 각 길에 거리(Cost)가 있었다면 여기서 최소 합 다이어트 판독을 추가하면 됩니다!

비록 위 코드는 목적지($N$)가 커지면 폭발하는 한계가 있지만, 이것이 쿠팡 배송차량, 공항 여객기 순항 루트, 그리고 마이크로 칩 내부 배선 최적화 등 1조 원 대 시장을 굴리는 해밀턴 회로 응용 컴퓨터 과학 분야의 핵심 뼈대 입니다.

5. 학습 정리 (Summary)

  1. 해밀턴 회로(Hamiltonian Circuit): 그래프에서 연결선은 안 지나도 냅두고, 오직 ‘나열된 점(도시, 랜드마크)’ 들만을 단 한 번씩 모조리 무중복으로 밟으면서 출발 기지로 귀환하는 고도의 링 탐색 논리입니다.
  2. 외판원 문제(TSP) 폭발 우주: 오일러와 달리 마법 꼼수 공식이 없는 이 해밀턴 회로는, 도시 수명이 늘어날 때마다 경우의 수가 팩토리얼($N!$) 곱셈으로 우주처럼 확산 폭발하기 때문에 인공지능과 양자컴퓨터가 지금도 가장 매달려 씨름하는 최적화 난제 분야의 최종 보스입니다.
서브목차