최근접 이웃 탐색을 통한 외판원 문제 탐구 with AlgeoMath
설명
- 외판원 문제란, n개의 점을 각각 한 번 지나는 최단 거리 경로를 찾는 문제다.
- 실제 최단 거리 경로를 찾기 위해서는 n의 계승 n!개의 모든 경로를 비교해야 한다.
- 그러나, n이 조금만 커져도 n!은 폭발적으로 커지므로1 모든 경로를 비교하기 어렵다.
- 최근접 이웃 탐색이란, 한 점으로부터 가장 가까운 점 찾는 것이다.
- 여기서는 최근접 이웃 탐색을 통해 외판원 문제를 탐구한다.
- 한 점에서 출발하여 최근접 이웃 탐색을 거듭 반복하면 한 경로를 찾을 수 있다.
- 각 점마다 같은 방법으로 경로를 찾으면, n개의 경로를 찾을 수 있고, 이 중에서 길이가 최소인 경로를 찾는다.
최근접 이웃 탐색을 통한 외판원 문제 탐구 - 빠른 결과 보기 with AlgeoMath
설명
- 위의 콘텐츠에서 설명을 생략하여 최종 결과를 빠르게 볼 수 있다.
최근접 이웃 탐색을 통한 외판원 문제 탐구 with Desmos
설명
- 같은 알고리즘을 데스모스에서 구현했다.