Nearest Neighbor는 탐욕적인(Greedy) 접근 방식을 취하는 휴리스틱입니다.
각 단계에서 즉각적으로 가장 유리한 선택을 반복함으로써 전체적인 해를 구성합니다.
알고리즘의 절차는 다음과 같습니다.
1.
시작 도시를 하나 선택합니다.
2.
현재 도시에서 아직 방문하지 않은 도시들 중 가장 가까운 도시를 찾습니다.
3.
그 도시로 이동합니다. 이동한 도시는 이제 방문한 도시로 표시됩니다.
4.
모든 도시를 방문할 때까지 2-3단계를 반복합니다.
5.
마지막으로 방문한 도시에서 시작 도시로 돌아와 경로를 완성합니다.
Nearest Neighbor 알고리즘은 그 단순함 때문에 TSP와 같은 순회 문제의 기본적인 휴리스틱으로 널리 알려져 있습니다.
import numpy as np
import matplotlib.pyplot as plt
def calculate_distance(point1, point2):
return int(np.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2))
def nearest_neighbor_tsp(coordinates):
num_cities = len(coordinates)
unvisited_cities = list(range(num_cities))
current_city = 0 # 시작 도시를 0번으로 설정
tour = [current_city]
unvisited_cities.remove(current_city)
while unvisited_cities:
nearest_distance = np.inf
nearest_city = -1
for neighbor in unvisited_cities:
distance = calculate_distance(coordinates[current_city], coordinates[neighbor])
if distance < nearest_distance:
nearest_distance = distance
nearest_city = neighbor
tour.append(nearest_city)
unvisited_cities.remove(nearest_city)
current_city = nearest_city
# 마지막 도시에서 시작 도시로 돌아가는 경로 추가
tour.append(tour[0])
return tour
def calculate_total_distance(coordinates, tour):
total_distance = 0
num_cities = len(coordinates)
for i in range(num_cities):
current_city_index = tour[i]
next_city_index = tour[i+1]
total_distance += calculate_distance(coordinates[current_city_index], coordinates[next_city_index])
return total_distance
# 주어진 좌표
coordinates = np.array([[0.0, 0.0], [0.0, 900], [100, 500], [200, 200], [400, 100], [400, 800], [700, 200], [800, 500], [900, 0.0], [900, 900], [0.0, 100], [0.0, 700], [400, 0.0], [400, 100], [400, 800], [400, 900], [700, 0.0], [700, 900], [900, 200], [900, 700]])
# Nearest Neighbor 알고리즘으로 TSP 경로 찾기
tour = nearest_neighbor_tsp(coordinates)
total_distance = calculate_total_distance(coordinates, tour)
print("TSP 경로 (Nearest Neighbor):", tour)
print("총 이동 거리 (Nearest Neighbor):", total_distance)
# 결과 시각화
plt.figure(figsize=(10, 10))
plt.scatter(coordinates[:, 0], coordinates[:, 1], color='red')
# 경로 시각화
for i in range(len(tour) - 1):
start_index = tour[i]
end_index = tour[i+1]
plt.plot([coordinates[start_index, 0], coordinates[end_index, 0]],
[coordinates[start_index, 1], coordinates[end_index, 1]],
'b-', linewidth=1)
plt.title('TSP Heuristic: '+str(total_distance))
plt.xlabel('X Coordinate')
plt.ylabel('Y Coordinate')
plt.legend()
plt.grid(True)
plt.show()
Python
복사
결과는 아래와 같습니다.
OR Tools 보다는 품질이 약간 낮아진 결과를 확인할 수 있지만 그럭 저럭 수긍할 만한 품질을 제공합니다.
Reference:
