====== TSP ======

Travelling Salesman Problem. **외판원 순회 문제**라고 [[번역]]하는 것 같지만 귀찮으니 영문 약자로 많이 쓴다.

임의의 무방향 가중 [[그래프]] $$G = (V, E, w)$$에 대하여 각 정점을 한 번씩만 지나고 다시 돌아오는 경로 (즉, 사실상 $$V$$의 [[순열]]) $$\pi = \langle v_0, \cdots, v_{|V|-1}, v_{|V|} = v_0 \rangle$$를 생각하자. (편의상 $$(u,v) \notin E$$일 경우 $$w(u,v) = \infty$$로 가정한다.) 이 경로의 길이 $$d(\pi) = \Sigma_{i=0}^{|V|-1} w(v_i, v_{i+1})$$를 정의할 때 $$\arg\min_\pi d(\pi)$$는 무엇인가?

전형적인 [[NP-완전]] 문제로, 현실에서 굉장히 활용할 거리가 많기 때문에 상당한 연구가 진행되어 왔다. 다양한 [[근사알고리즘]]이 존재하며 상당히 큰 입력에 대하여 정확한 해를 구하는 용도로 [[유전알고리즘]] 따위를 쓰는 사례도 많다.

{{tag>전산학}}