[KMOOC 강화학습] Week 02-2 외판원 문제

해당 강의는 K-MOOC의 “강화학습의 수학적 기초와 알고리즘 이해” 수업을 수강하며 기록한 내용입니다. 강의는 링크에서 확인하실 수 있습니다.

외판원 문제

: Traveling Salesman Problem(TSP)

여러개 도시 간 거리가 주어졌을 때 정확히 한번씩 방문하는 최단거리를 찾는 문제다!

예시

• 쓰레기차 수거 경로
• 택배 차량들의 경로
• 물류 창고에서 경로 문제
• 회로 장비 최적화

문제 정의

비용

$C$ : 두 node 간 이동(행동)에 따른 비용을 적은 행렬

상태

최단 경로 문제와 유사하며 다음과 같은 요소가 필요하다

• 현재 나의 상태 : $n$
• 이전에 방문 했던 곳 : $N$

행동

방문하지 않은 도시 중 어느 도시를 방문할지 결정

$n^{`} \in TOTAL - (N\cup {n})$

가치 함수

: 현재까지 N에 속한 도시들을 방문했고, n의 위치에 있다고 할 때 나머지 방문하지 않은 도시를 방문하고 다시 원점으로 돌아가는데 걸리는 소요시간(혹은 거리)

$V(N,n) = C(n,n^{‘}) + V(N\cup {n}, n’)$

⚡ 결국 n으로 간다는 선택을 했을 때 남은 비용을 계산하는 것이 가치함수를 말하는 것 ⚡ $C(n,n^{‘})$ 는 그 선택을 했을 때 다음 이동 경로 중 하나($n^{‘}$)를 선택했을 때의 비용 ⚡ $V(N\cup{n},n’)$는 $n^{‘}$을 선택했을 때 남은 비용을 말하는 것!

☝ 즉, 매 상태마다 여러 옵션이 있으면 최적(가장 작은 값)의 값을 선택하게 된다!!