Dijkstra's Algorithm과 근본적으로 동일.
Dynamic Programming과 다르게 cyclic하다는 게 특징임.
액션을 취할 때마다 비용이 누적됨. --> 총 누적 비용이 가장 적은 경로를 찾음.
- 모든 행동 비용은 음수가 아닙니다. --> Cost(s,a) >= 0
- UCS는 past cost 순으로 상태를 열거함.
explored --> frontier --> unexplored
explored는 이미 최적 경로에 추가된 노드들
Frontier는 대충 priority queue라고 생각하면 될듯. (탐색 기록은 있지만 아직 최적 누적 비용이 계산되지는 않은)
프론티어가 빌 때까지 알고리즘은 반복됨. 혹은 특정 목표 노드를 찾을 때까지.
가장 낮은 누적 비용을 가진 노드를 우선 탐색
자식 노드를 탐색하면서 누적 비용이 가장 적은 자식 노드를 저장소에 추가하면서 데이터를 확장함.
** Priority Queue를 저장 구조로 사용함.
가능한 모든 노드 경로를 택하되 (큐에 추가하되) 다음 경로를 택할 때 누적 비용이 가장 적은 경로를 택한 후 해당 경로는 업데이트 됨.
일단 누적 비용이 가장 적은 방향을 택함.
누적 비용 == cumulative cost, accumulated cost, total cost, path cost
** 최소 비용 경로 우선: 항상 현재까지의 누적 비용이 가장 낮은 경로를 먼저 탐색합니다.
UCS find the path that has the smallest current cumulative cost.
이미 CLOSED 된 노드면 추가하지 않음.
경로의 가장 마지막에 오는 노드가 STATE라고 가정하자.
Let's assume that the very last node of the path is the state.
1. [(A,0)]
2. [(A-B, 1), (A-C,2) ,(A-D, 4)]
3. [(A-B-E, 3), (A-C,2) ,(A-D, 4)]
Since the cumulative cost of 'A-B-C'is larger than 'A-C', it's automatically dropped.
4. [(A-B-E, 3), (A-C-D, 3)]
Since the cumulative cost of 'A-C-B' is larger than 'A-B', it's automatically dropped.
Since the cumulative cost of 'A-C-D' is more effective path rahter than 'A-D', the path for D is updated to 'A-C-D'.
- [(A-B-E-F, 4), (A-C-D, 3)]
[(A,0)][(A-B, 1), (A-C, 100)]
[(A-B-C, 2), (B-D, 101)][(A-B-C-D, 3), (B-D, 101)]
[(B, ?+1)]
UCS summary:
-
ucs란?
-
ucs 특성?
-
ucs 예제
*UCS가 DP보다 적은 상태를 탐색함. 하지만 UCS는 우선순위 큐를 유지하는 데 더 많은 오버헤드가 요구됨.
