4.3.2 탐욕 알고리즘 사용하기
이번에는 탐욕 알고리즘을 사용해서 외판원 문제를 풀어 보겠습니다. 탐욕 알고리즘은 전체 관점에서 최적인 도시를 선택하는 것이 아니라, 매 순간 그 상황에서만 최적인 도시를 다음 방문지로 결정합니다. 즉, 현 위치에서 가장 가까운 도시로 이동하는 것입니다. 당연하게도 이 선택은 전체 투어의 관점에서는 최적의 선택이 아닐 확률이 높습니다.
탐욕 알고리즘은 매우 간단합니다.
1. 출발지를 무작위로 선택합니다.
2. 현 위치에서 가장 거리가 가까우면서도 방문한 적이 없는 도시로 이동합니다.
3. 단계 2를 반복합니다.
이를 파이썬 함수로 구현하면 다음과 같습니다.
[in :]
def greedy_algorithm(cities, start=None):
C = start or first(cities)
tour = [C]
unvisited = set(cities - {C})
while unvisited:
C = nearest_neighbor(C, unvisited)
tour.append(C)
unvisited.remove(C)
return tour
def first(collection): return next(iter(collection))
def nearest_neighbor(A, cities):
return min(cities, key=lambda C: distance_points(C, A))