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


도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기