728x90
반응형
⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️
Traveling Salesperson Problem(TSP) / 외판원 문제
외판원이 여러 지역을 돌아다닌다. 출발지는 존재하고, 모든 도시 한번씩은 반드시 방문해야 한다.
하지만, 한번 간 도시는 재방문할 수 없고, 출발지로 돌아와야한다.
=> 최적경로 찾기 문제
ex)
A
B
C D
A-B : 10
A-C : 35
A-C : 30
B-C : 30
B-D : 15
C-D : 30
A Simple TSP
1단계 : 모든 경로를 List Up
2단계 : 그 중 최소 경로 선택
모든경로 결과값
ABCDA : 100
ABDCA : 90 -> shortest!
ACBDA : 110
ACDBA : 90 -> shortest!
ADBCA : 110
ADCBA : 100
위 방법의 문제점 : 목록이 너무 많으면 RAM 낭비가 심함. 계산량이 과하게 많음 => 잘못된 방법
Near-optimal Solution
A Grid Method
현재 연결돼있는 경로중 가장 짧은(코스트가 낮은) 경로로 이동.
But! 최적의 방법은 아닐 수 있음. 거시적인 관점에서 최적해를 장담할 순 없지만, 아무렇게나 가는것 보다는 그나마 더 나을 수 도 있음
Problem 1
100개의 도시정보가 있다. 일련번호, X좌표, Y좌표 등의 정보를 포함하고 있다.
모든 도시를 여행하고 출발지(0번) 도시로 돌아오는 경로와 거리를 구하시오.
단, 두 도시 사이의 거리는 Euclidean Distance 방식으로 계산한다.
Problem 2
Problem 1에서 구한 경로를 도식화 하시오
출발도시 : 빨간 동그라미
나머지 도시 : 검은 동그라미
경로 : 전선 화살표
728x90
반응형