TSP: Greedy Algorithm

나도잘몰라·2022년 12월 22일

그리디 알고리즘 외판원 문제

algorithm

목록 보기

1/1

Routing problems(경로 설정 문제)

일련의 위치를 방문할 때 최적의 경로를 찾는 것을 말한다. 최적의 경로란 거리나 비용이 최소인 경로를 말한다.

Traveling Salesperson Problem(TSP) 외판원 문제

가장 유명한 routing problem으로, 외판원이 각 고객의 집을 방문한 뒤 다시 출발지로 돌아올 때의 가장 짧은 경로를 찾는 것

If simple TSP(exhaustive method)

Step 1 : 모든 경로 구하기

_nP_r = \frac{n!}{(n-r)!}

Step 2 : 최적 경로 선택하기

But, larger problems

노드가 많아지면 문제가 어려워짐
철저하게 모든 경로를 탐색한다면 최적의 해를 보장할 수 있지만 계산적으로 다루기 힘듦
더 큰 문제의 경우에는 솔루션 공간을 합리적으로 검색하고 최적 또는 최적에 가까운 최적화 기술이 필요
⇒ Near-optimal solution

So, Heuristicv Algoritms

휴리스틱(heuristics)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편 추론의 방법

Greedy Algoritms

미래를 생각하지 않고 각 단계에서 값이 최소인 경로를 선택

100개의 도시 정보가 있다. 이 파일은 도시별 일련변호(NO.), x좌표(XCOORD.), y좌표(YCOORD.) 등의 정보를 포함하고 있다. 모든 도시를 여행하고 출발지(0번 도시)로 돌아오는 경로(route)와 거리(distance)를 구하시오.
단, 두 도시(A, B) 사이의 거리(D)는 Euclidean Distance 방식으로 계산한다.

# 드라이브 마운트
from google.colab import drive
drive.mount('/content/drive')

Google Drive에 연결 - 계정 선택 - 허용

# 파일 불러오기
import pandas as pd
df = pd.read_csv('/content/drive/MyDrive/Input_data.csv')
df.head()

저는 미리 드라이브에 폴더 만들어서 넣어놨습니다.
임시로 업로드하는 것 말고 찾아서 경로 복사한 값 사용했습니다.

# 경로, 거리 리스트 초기화
r_route = [0]
r_distance = []

# 다른 노드까지의 거리를 비교해 최적 노드와 거리를 반환하는 함수
def findOptimal(route) :
  distance = []
  for i in df.index:
    d = ((df.loc[i, "XCOORD."] - df.loc[route[-1], "XCOORD."]) ** 2 + (df.loc[i, "YCOORD."] - df.loc[route[-1], "YCOORD."]) ** 2) ** (1/2)
    distance.append(d)
  while True:
    if distance.index(min(distance)) in route:
      distance[distance.index(min(distance))] = 9999
    if distance.index(min(distance)) not in route:
        break
  return [distance.index(min(distance)), min(distance)]
  
# 출발지로 돌아오는 최적의 경로와 거리값 찾기
while True:
  x, y = findOptimal(r_route)
  r_route.append(x)
  r_distance.append(y)
  if len(r_route) == 100:
    break

# 마지막 노드에서 0까지 경로, 거리 추가
r_distance.append(((df.loc[r_route[-1], "XCOORD."] - 0) ** 2 + (df.loc[r_route[-1], "YCOORD."] - 0) ** 2) ** (1/2))
r_route.append(0)

# 답
print("경로(", len(r_route), ") : ", r_route)
print("경로 간 거리(", len(r_distance), ") : ", r_distance)
print("총 거리 : ", sum(r_distance))

위의 경로를 도식화하시오.

import matplotlib.pyplot as plt

# 최적 경로의 좌표 저장하기
x = []
y = []

for i in range(0, 101):
  x.append(df.loc[r_route[i], "XCOORD."])
  y.append(df.loc[r_route[i], "YCOORD."])

# 그래프 그리기
fig = plt.figure()
ax = fig.add_subplot(1, 1, 1)

# 노드와 이동 경로(간선) 그리기
plt.plot(x, y, color='black', marker=5, markersize=10, linestyle='--')
plt.plot(x, y, 'ko')
plt.plot(0, 0, 'ro')

오랜만에 파이썬 쓰니까 까먹었습니다.
과제였는데 코랩도 잘 몰라서 헤맸네요.
참고될까 남깁니다~

혹시 도식화 부분 중에 노드의 마커랑 간선 간의 점선 화살표를 위와 같은 방식 말고 plt.arrow를 사용해서 예쁘게 한 사람 있으면 아이디어 남겨 주시길 바랍니다!

나도잘몰라