근사 알고리즘/Traveling salesman (3) 썸네일형 리스트형 크리스토피데스 알고리즘으로 경로 외판원 문제 풀기 (Path TSP by Christofides' Algorithm) 오랜만에 근사 알고리즘으로 돌아왔습니다. 지난번 크리스토피데스 알고리즘(Christofides' algorithm)을 공부하면서 마지막에 외판원 문제(traveling salesman problem, TSP)의 변형인 경로 외판원 문제(path TSP)를 소개하면서 끝냈습니다. 2019/07/23 - [근사 알고리즘/Traveling salesman problem] - [외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm) [외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm) 지난 포스팅에서 traveling salesman problem이 (우리말로 외판원 문제) 무엇인지 알아보았습니다. 안타깝게도 일반적인 거리에 대해.. [외판원 문제 / TSP] 크리스토피데스 알고리즘 (Christofides' Algorithm) 지난 포스팅에서 traveling salesman problem이 (우리말로 외판원 문제) 무엇인지 알아보았습니다. 안타깝게도 일반적인 거리에 대해서는 적절한 근사 알고리즘이 존재하기 어렵다는 것을 보였습니다. 하지만 metric인 경우에는 2-근사 알고리즘이 존재한다는 것을 보였습니다. 아직 보지 않으셨다면 다음 링크를 참조해 주세요. :) 2019/07/20 - [근사 알고리즘/Traveling salesman problem] - [Traveling Salesman Problem] Metricity & 2-Approximation [외판원 문제 / Traveling Salesman Problem] 메트릭 & 2-근사 (Metricity & 2-Approximation) 안녕하세요. 이번에는 trave.. [외판원 문제 / TSP] 메트릭 & 2-근사 (Metricity & 2-Approximation) 안녕하세요. 이번에는 traveling salesman problem에 대해서 알아보도록 하겠습니다. 주로 줄여서 TSP라고도 부르며, 제가 알기로 우리말로는 외판원 문제로 불립니다. 개괄적인 설명은 이전 글에서 했습니다. 2019/07/10 - [근사 알고리즘] - 근사 알고리즘 근사 알고리즘 (Approximation Algorithm) 현대 사회는 컴퓨터와 떼어낼 수 없는 관계를 맺고 있습니다. 우리는 컴퓨터를 통해 문제를 해결하고, 다른 이들과 소통하며, 여가를 즐기기도 합니다. 그렇다면, 과연 컴퓨터는 모든 것을 해줄 수 있을까요? 아.. gazelle-and-cs.tistory.com 그러니 이번에는 서두 없이 바로 문제를 정의해 보도록 하겠습니다. 문제의 입력으로 지점들의 집합 \(V\)와 .. 이전 1 다음
