Christofides (2) 썸네일형 리스트형 크리스토피데스 알고리즘으로 경로 외판원 문제 풀기 (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.. 이전 1 다음
