가장 가까운 이웃 알고리즘

가장 가까운 이웃 알고리즘

클래스	근사 알고리즘
데이터 구조	그래프
최악의 경우 공연	${\displaystyle \Teta(N^{2})}$
최악의 경우 공간 복잡성	$[\displaystyle \Teta(N)}$

가장 가까운 이웃 알고리즘은 대략적으로 여행하는 세일즈맨 문제를 해결하는 데 사용되는 첫 번째 알고리즘 중 하나이다. 그 문제에서 판매원은 무작위 도시에서 시작해서 모든 사람이 방문할 때까지 가까운 도시를 반복해서 방문한다. 이 알고리즘은 빠른 속도로 짧은 투어를 제공하지만 대개 최적의 투어는 아니다.

알고리즘.

알고리즘의 단계는 다음과 같다.

1. 모든 정점을 방문하지 않은 것으로 초기화하십시오.
2. 임의 정점을 선택하고 현재 정점 u로 설정하십시오. 방문자임을 표시하십시오.
3. 현재 꼭지점 u와 방문하지 않은 꼭지점 v를 연결하는 가장 짧은 에지를 찾아 보십시오.
4. v를 현재 꼭지점 u로 설정하십시오. 방문자로 v를 표시한다.
5. 도메인의 모든 정점을 방문하면 종료하십시오. 그렇지 않으면 3단계로 이동하십시오.

방문한 정점의 순서는 알고리즘의 출력이다.

가장 가까운 이웃 알고리즘은 구현이 쉽고 빠르게 실행되지만, '자랑'하는 성격 때문에 인간의 통찰력으로 쉽게 알아차릴 수 있는 짧은 경로를 놓칠 수 있다. 일반적인 가이드로서, 투어의 마지막 몇 단계가 첫 번째 단계와 비교할 수 있다면 투어는 합리적이고, 훨씬 더 크다면 훨씬 더 나은 투어가 존재할 가능성이 높다. 또 다른 점검은 이 투어가 충분한지 추정하기 위해 하한 알고리즘과 같은 알고리즘을 사용하는 것이다.

최악의 경우 알고리즘은 최적 투어보다 훨씬 긴 투어를 낳는다. 정확히 말하면, 모든 상수 r에 대해 가장 가까운 이웃 알고리즘에 의해 계산된 둘러보기 길이가 최적 둘러보기 길이의 r배보다 더 큰 여행 판매원 문제의 예가 있다. 또한 각 도시 수에 대해 가장 가까운 이웃의 휴리스틱이 유일한 최악의 투어를 생산하는 도시들 사이의 거리 배정이 있다. (모든 꼭지점에 알고리즘을 시작 꼭지점으로 적용한다면, N이 정점의 수인 N/2-1 다른 투어보다 발견된 최상의 경로가 더 나을 것이다.)^[1]

가장 가까운 이웃 알고리즘은 심지어 그것이 존재하는 경우에도 실현 가능한 여행을 전혀 찾지 못할 수 있다.

메모들

참조

• G. 구틴, A. 여와 A. Zverovitch, 지수 근린 및 TSP에 대한 지배 분석, 여행 세일즈맨 문제와 그것의 변화, G. Gutin과 A.P. Punnen (eds), Kluwer (2002) and Springer (2007)에서.
• G. 구틴, A. 여와 A. Zverovich, 여행 세일즈맨은 탐욕스러워서는 안 된다: TSP에 대한 탐욕스러운 유형의 휴리스틱스의 지배 분석. 이산 응용 수학 117(2002), 81–86.
• J. 뱅 젠슨, G. 구틴, A. 여, 탐욕스러운 알고리즘이 실패했을 때. 이산 최적화 1(2004), 121–127.
• G. 벤달과 F. Margot, 결합 문제의 탐욕스러운 유형 저항, 이산 최적화 3(2006), 288–298.