Traveling Salesman Problem Homework Traveling Salesman Problem By Greedy Algorithm
Traveling Salesman Problem 물류산업에서의 배차, 항공기 스케줄링, 반도체 설계, 드릴머신 배치 등은 물론 게놈정보 분석, 천체망원경 배치, 엑스선 결정학 등에서도 사용되고 있다. 따라서 수많은 수학자, 컴퓨터과학자. 산업공학자, 경영과학자들이 수학적 성질, 컴퓨터 알고리즘·데이터 구조 연구, 소프트웨어 개발, 산업·경영 문제 응용 등을 위해 연구하고 있다.
Pipeline http://www.youtube.com/watch?v=tqC3BjIyq_0&feature=player_detailpage
Procedure Input Coordinates VBA Coding Draw a Chart Improvement Distance on a Sphere
NAVER
위도: 세로축 y 값 경도: 가로축 x 값
위도: 세로축 y 값 경도: 가로축 x 값
Another http://universimmedia.pagesperso-orange.fr/geo/loc.htm
출발지점 방문지
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 = 1000000 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
춘천 서울 영덕 대전 부산 광주
Greedy Algorithm 결과에 만족하시나요? 더 나은 경로를 찾아서 수정하세요. Greedy Algorithm 개선 방법이 있다면 제시하세요.
지표상 두 점 사이의 거리 지구 반지름은 R=6,400km 위도 θ에서 단면 원의 반지름 = R cosθ 두 점 사이의 거리는?
Thanks for your attention!