Traveling Salesman Problem

Presentation on theme: "Traveling Salesman Problem"— Presentation transcript:

1 Traveling Salesman Problem
Homework Traveling Salesman Problem By Greedy Algorithm

2 Traveling Salesman Problem
물류산업에서의 배차, 항공기 스케줄링, 반도체 설계, 드릴머신 배치 등은 물론 게놈정보 분석, 천체망원경 배치, 엑스선 결정학 등에서도 사용되고 있다. 따라서 수많은 수학자, 컴퓨터과학자. 산업공학자, 경영과학자들이 수학적 성질, 컴퓨터 알고리즘·데이터 구조 연구, 소프트웨어 개발, 산업·경영 문제 응용 등을 위해 연구하고 있다.

3 Pipeline

4

5 Procedure Input Coordinates VBA Coding Draw a Chart Improvement
Distance on a Sphere

6 NAVER

7

8 위도: 세로축 y 값 경도: 가로축 x 값

9 Google

10

11 위도: 세로축 y 값 경도: 가로축 x 값

12 Another

13 출발지점 방문지

14

15 Sub TSP_Greedy() Cities = 5 ReDim x(Cities), y(Cities), Visited(Cities) As Boolean x(0) = Cells(1, "F") y(0) = Cells(1, "G") For City = 1 To Cities x(City) = Cells(City, "B") y(City) = Cells(City, "C") Visited(City) = False Next City Ref_City = 0 For Sequence = 1 To Cities Distance_Min = If (City <> Ref_City) And (Visited(City) = False) Then Distance = (x(City) - x(Ref_City)) ^ 2 + (y(City) - y(Ref_City)) ^ 2 If Distance < Distance_Min Then Distance_Min = Distance Nearest_City = City End If R1 = Trim(Str(Sequence + 1)) R2 = Trim(Str(Nearest_City)) Range("E" + R1, "G" + R1).Value = Range("A" + R2, "C" + R2).Value Visited(Nearest_City) = True Ref_City = Nearest_City Next Sequence R1 = Trim(Str(Cities + 2)) Range("E" + R1, "G" + R1).Value = Range("E1", "G1").Value End Sub

16 춘천 서울 영덕 대전 부산 광주

17 Greedy Algorithm 결과에 만족하시나요?
더 나은 경로를 찾아서 수정하세요. Greedy Algorithm 개선 방법이 있다면 제시하세요.

18 지표상 두 점 사이의 거리 지구 반지름은 R=6,400km 위도 θ에서 단면 원의 반지름 = R cosθ
두 점 사이의 거리는?

19 Thanks for your attention!