[SW_2] Heuristic: a routing problem(TSP, 외판원문제) - Greedy

1. Heuristic : "경험적인, 스스로 발견하게 하는" 이라는 뜻으로 시간이나 정보가 부족하여 합리적인 판단을 할수 없거나 굳이 판단하지 않아도 사람들이 빠르게 사용할 수 있도록 하는 간편추론의 방법이다.

• 휴리스틱의 알고리즘은 문제에 대한  모든 솔루션 중 최선일 수도 있고 단순히 정확한 솔루션에 근접할 수 있다. 즉 휴리스틱을 통해 해결된 문제에 대한 답은 가장 좋은 답이 아닐 수도 있다.
• 관련 알고리즘으로는 가지치기(pruning) 기법, Simulated Annealing(담금질 기법), Genetic Algorithms(유전알고리즘) 이 있다.

 

2. Routing problem : 여러 노드를 방문하는 경로에 대해 가장 최소로 하는 최적의 경로를 찾는 문제

 

3. 외판원 문제(Traveling Salesperson Problem(TSP)

• 다른 지역의 고객을 방문해야 하는 영업 사원을 위한 최단 경로 찾기 위치를 지정하고 시작점으로 돌아갑니다. TSP는 그래프로 나타낼 수 있습니다. 노드는 위치에 해당하고 모서리(또는 호)는 직접 이동을 나타냅니다.

 

 

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

 

Input_data.csv

0.00MB

결과 : 임의로 다음 도착 도시를 선정하는 방법과(Random) 개발한 휴리스틱 방법(near-optimal) 의 결과를 가시적으로 비교

 

풀이 : 모든 도시를 돌아서 작은 비용을 가지는 경로를 가지기 패스를 구하기 위해서 greedy algorithm 을 사용하였다. 

 

코드 : 

import pandas as pd
import math
import random
import matplotlib.pyplot as plt

df = pd.read_csv('Input_data.csv')


def near_optimal(df) :
  path=[]
  path.append(0)
  coord=0
  dis = 0

  for i in range(0,100):
    start = df.loc[coord]
    min=0
    for j in range(1,100):
      if j not in path:
        end = df.loc[j]
        a = start[1] - end[1]
        b = start[2] - end[2]
        d = math.sqrt((a * a) + (b * b))
        if min==0 or d==0:
          min = d
          coord = j
          if d==0:
            break;
        elif d < min:
          min =d
          coord = j
    if i == 99:
      end = df.loc[0]
      a = start[1] - end[1]
      b = start[2] - end[2]
      min= math.sqrt((a * a) + (b * b))
      coord=0
    path.append(coord)
    dis+=min
  return dis, path
  

def random_path(df):
  path=[]
  path.append(0)
  coord=0
  dis=0
  for i in range(0,100):
    start = df.loc[coord]
    j=0
    while j == 0:
      j= random.randrange(1,100)
      if j not in path:
        end = df.loc[j]
        a = start[1] - end[1]
        b = start[2] - end[2]
        d = math.sqrt((a * a) + (b * b))
        min = d
        coord = j
    if i == 99:
      end = df.loc[0]
      a = start[1] - end[1]
      b = start[2] - end[2]
      min= math.sqrt((a * a) + (b * b))
      coord=0
    path.append(coord)
    dis+=min
  return dis


dis, path = near_optimal(df)

heuri_list = []
ran_list=[]
x=[]
for i in range(0,10):
  heuri_list.append(dis)
  ran_list.append(random_path(df))
  x.append(i)

plt.figure(figsize=(32,9))
plt.scatter(x,heuri_list, s =600, c='red', marker = 'o', label="Heuristic")
plt.scatter(x,ran_list, s =600, c='purple', marker = '^',label="Random")
plt.ylabel("distance",fontdict={'size':26})
plt.xlabel("number of attempts",fontdict={'size':26})
plt.legend(loc ='upper left',fontsize = 26)
plt.ylim(0, 7000)
plt.show()

 

 

이 방법을 사용하여 가장 최소의 비용을 가지는 경로를 구하는 것은 불가능합니다.

다음 학습을 통해 최소 비용을 가지는 경로를 구하는 것을 찾아보도록 하겠습니다.