[알고리즘] TSP (Traveling Salesperson Problem, 외판원 문제)

TSP (Traveling Salesperson Problem)

1. 해밀턴 경로(Hamiltonian Circuit), 일주여행경로 : 모든 정점을 한 번씩만 거쳐서 출발한 정점으로 다시 돌아오는 경로
2. TSP (Traveling Salesperson Problem), 외판원 문제
   • Mathematically formulated in the 1800s by the Irish mathematician William Rowan Hamilton
   • an NP-hard problem in combinatorial optimization
   • Is important in theoretical computer science and operations research.
   • 최소한 하나의 일주여행 경로가 존재하는 경우, 가중치 포함 방향 그래프에서 최적 일주여행경로를 찾는 문제

• TSP 문제에 쓰일 용어
  • 𝑉 : 모든 정점의 집합
  • 𝐴 : 𝑉의 부분집합
  • 𝐷[][𝐴] = 𝐴에 속한 정점을 각각 한 번씩만 거쳐서 에서 로 가는 최단경로의 길이
    • : 정점, 𝐴 : 집합