일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- 강화학습의 수학적 기초와 알고리듬 이해
- summarize_chat_history
- agenticrag
- chat_history
- rag
- fastapi
- 밑바닥부터 시작하는 딥러닝
- rl
- update_state
- pinecone
- add_subgraph
- Docker
- LangChain
- conditional_edges
- tool_call_chunks
- 밑바닥부터시작하는딥러닝 #딥러닝 #머신러닝 #신경망
- 강화학습
- 추천시스템
- Ai
- Python
- removemessage
- 강화학습의 수학적 기초와 알고리듬의 이해
- subgraph
- RecSys
- langgraph
- toolnode
- tool_calls
- REACT
- langgrpah
- adaptive_rag
- Today
- Total
타임트리
Week3. 동적계획법2 본문
최단 경로 문제(Shortest path problem)
아래 그림과 같이 1번 노드에서 10번 노드까지 최단 거리를 찾는 문제를 생각해보자.

우선 그래프를 살펴보자. 노드끼리 이어진 선은 아크(arc)라고 하며, 화살표(→)로 표시한 아크는 일방통행, 선으로만 표시된 아크는 양방통행을 나타낸다. 또한 아크 옆에 표시된 숫자는 노드에서 노드로 이동까지의 거리 혹은 소요되는 시간으로 볼 수 있다. 여기서는 거리라고 하자.
위와 같은 상황에서 1번 노드에서 10번 노드까지 가장 빨리 이동하는 경로를 찾기 위해서는 어떻게 해야할까? 먼저 가장 단순한 방법은 모든 경로에 대한 거리를 계산하고 비교하는 것이다. 그러나 이 방법은 비효율적이란 걸 금방 알아차릴 수 있다. 이 문제를 동적계획법으로 해결해보자.
동적계획법을 적용하기 위해서는 크게 2가지에 대한 정의가 필요하다. 첫 번째는 상태, 행동에 대한 정의, 두 번째는 재귀식을 통한 가치 함수를 정의하는 것이다. 차례대로 살펴보자.
상태, 행동에 대한 정의
상태(state)는 의사결정을 내리기 위해 필요한 최소한의 정보를 말한다. 순차적인 의사결정의 과정(단계)은 각 노드에서 이루어진다. 따라서, 상태 정보는 현재 노드의 위치가 될 것이다. 자연스럽게 상태를 바탕으로 이루어지는 의사결정인 행동은 다음으로 이동할 노드가 무엇인지가 될 것이다.
- 상태: 현재 위치한 노드
- 행동: 다음으로 이동할 노드
재귀식을 통한 가치 함수 결정
앞서 정의한 상태와 행동을 기반으로 최적화 원리(principle of optimality)를 만족하는 재귀식(recursive equation)을 결정해야 하며 이러한 재귀식을 가치 함수(value function)라고 한다. 아래의 예시를 바탕으로 가치 함수를 도출해보자.

1번 노드에서 출발해 X 노드로 도착하는 문제에서 현재 1번 노드에 위치해 있을 때(상태), 2번, 3번, 4번 노드 중 어떤 노드로 이동해야할까(행동)? 위 그래프가 주어져있다면, 당연히 X 노드까지의 거리가 가장 짧은 2번 노드를 선택할 것이다. 1번 노드에서 2번, 3번, 4번 각각의 노드까지의 거리는 5, 2, 11이며, 각각의 노드부터 X 노드까지의 최단 거리는 20, 25, 17이다. 따라서, 2번, 3번, 4번 각각의 노드를 선택했을 때 1번부터 X 노드까지의 총 소요시간은 25, 27, 28이기 때문에 2번 노드를 선택했을 때 최단 거리가 된다. 이러한 의사결정을 내릴 수 있던 이유는 행동을 선택한 이후의 노드부터 종점까지의 최단 소요시간을 알고 있기 때문이다. 이러한 의사결정의 과정을 참고하여, 가치 함수를 도출해보자.
우선, 가치 함수는 상태에 대한 함수로써
위 그래프에서의 의사결정을 내린 과정을 살펴보면, 현재 위치부터 다음 위치까지의 거리와 다음 상태에서 종점까지 최단 거리에 해당하는 거리를 더해 비교했다. 즉, 다음과 같이 가치 함수를 만들 수 있다.
문제 풀이
그럼 문제를 풀어보자. 아래처럼 표가 주어졌을 때 직접 계산해보면 모든 값이 도출되는 것을 확인할 수 있다.

예를 들어,
사실 여기엔 한 가지 문제가 있다. 만약 위와 같이 표가 주어지지 않았다면, 재귀식을 통해 문제를 해결할 수 없다. 재귀식이 만족되기 위해서는 하위 문제를 풀 수 있어야 한다. 그러나, 표가 주어지지 않은 상황에서
이러한 상황을 순환 참조 상황이 발생했다고 하며, 동적계획법에 기반해 문제를 해결할 수 없다. 이를 해결하기 위해서는 상태에 대해 재정의를 해야 한다. 즉, 현재 상태 정보만으로는 재귀식을 도출하기 어렵다고 해석해야 하며, 추가적인 정보를 포함한 상태를 재정의 후 재귀식을 도출해야 한다.
그러나, 이 부분은 현재 수업 내용의 범위를 벗어나기 때문에 현재 내가 어느 노드에 있는지라는 상태만으로 문제 해결이 가능한 다음 예시를 살펴보자.
Stagecoach 문제
앞서 순환 참조 상황이 발생한 이유는 양방통행이 가능했기 때문인데, stagecoach 문제는 최단 경로에서도 일방통행만이 존재하는 특별한 경우를 의미한다. 그래서 앞서 정의한 재귀식만으로 문제 해결이 가능하다.

위 그림을 보면, A 노드에서 J 노드까지 최단 경로를 찾고자 할 때, 상태
먼저 Stage4를 구해보자.

다음으로 Stage3을 보자.

다음으로 Stage2를 보자.

우리의 목적은 궁극적으로

그럼 노드 A부터 J까지 구체적인 최단 경로는 어떻게 찾을까? 예를 들어, A에서 C를 선택했다고 하자. 그러면 (A → C → E → H → J)가 최단 경로가 될 것이다. 혹은 (A → D → E → H → J), (A → D → F → I → J)도 가능하다.
방문판매원 문제(Traveling Salesman Problem, TSP)
방문판매원 문제는 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 정확히 한 번씩만 방문해 원래 도시로 돌아오는 가장 짧은 경로를 찾는 문제를 일컫는다. 외판원 문제가에 대해 가치 함수의 기반한 재귀식을 도출해보자. 주어진 행렬은 4개 도시가 주어졌을 때, 각 행과 열의 순서는 해당 도시, 그리고 각 원소는

상태, 행동에 대한 정의
먼저 재귀식을 도출하기 위해 상태와 행동을 정의해보자. 상태는 최단 경로와 유사하게 현재 어떤 도시에 있는가가 될 것이다. 그런데, 상태는 의사결정을 내리기 위해 필요한 최소한의 정보를 의미한다는 점을 되짚어봤을 때, 이 한 가지 정보만으로는 의사결정을 내릴 수 없다. 왜냐하면, 이전에 방문한 도시는 다시 방문하면 안된다는 요구조건이 있기 때문이다. 따라서, 어떤 도시에 방문했었는가라는 추가적인 정보가 필요하다. 즉, 상태는 다음과 같이

다음은 행동을 정의해야 한다. 행동은 현재 도시에서 방문하지 않은 도시들 중 어떤 도시에 방문할지를 결정하는 것이다. 즉, 현재
재귀식을 통한 가치 함수 결정
앞서 정의한 상태와 행동을 기반으로 가치 함수를 결정해보자. 가치 함수는
여기서,
문제 해결
방문판매원 문제의 가능한 모든 상태(

마찬가지로 가장 작은 문제부터 풀어보면 다음과 같이 계산할 수 있다.

그 이전 단계도 마찬가지로 계산할 수 있다.


따라서 최단 경로는 다음과 같다.

'Reinforcement Learning > 강화학습의 수학적 기초와 알고리듬 이해' 카테고리의 다른 글
Week6. MDP-2 (0) | 2022.04.03 |
---|---|
Week5. MDP-1 (0) | 2022.04.01 |
Week4. 마르코프 과정 (0) | 2022.03.31 |
Week2. 동적계획법1 (0) | 2022.03.27 |
Week1. 강화학습의 이해 (0) | 2022.03.23 |