approximation_algorithms (1) 썸네일형 리스트형 [외판원 문제 / TSP] 메트릭 & 2-근사 (Metricity & 2-Approximation) 안녕하세요. 이번에는 traveling salesman problem에 대해서 알아보도록 하겠습니다. 주로 줄여서 TSP라고도 부르며, 제가 알기로 우리말로는 외판원 문제로 불립니다. 개괄적인 설명은 이전 글에서 했습니다. 2019/07/10 - [근사 알고리즘] - 근사 알고리즘 근사 알고리즘 (Approximation Algorithm) 현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요? 아.. gazelle-and-cs.tistory.com 그러니 이번에는 서두 없이 바로 문제를 정의해 보도록 하겠습니다. 문제의 입력으로 지점들의 집합 \(V\)와 .. 이전 1 다음
