고려대학교 산업공학과 정태수 교수님 강의 정리

Week3: 동적계획법-2

• Lecture

3-1. 최단거리 문제 (Shortest Path)

• 문제 정의: 시작 지점부터 종료지점까지 최단 경로를 찾는 문제
• 예시
  • 각 노드가 존재
  • 노드간의 걸리는 시간/거리가 존재 (ex. 1 -> 2: 5)
    

도입 예시

문제 해결 방법

• 상태와 행동을 정의
• 재귀식을 통해 가치함수를 결정
  • 최단 거리에 해당하는 거리나 시간($`v^*(s_t)`$)
  • $`v(s_t) = min(r(s_t, s_{t+1}) + v(s_{t+1}))`$
    • 내가 선택할 수 있는 다음 노드 중에 가장 작은 값을 선택

예시

• 문제
  
  
• 예시 (8->10)
  • min(7, 4+10, 4+5) = 7
• 결과
  
  
• 위 문제에서 $`v(s_9)$ 값을 구하려면 $v(s_8)$, $v(s_7)$, $v(s_{10})`$의 값을 알아야함
  • 순환 참조 상황이 발생함
    --> 재귀식을 도출하기 어렵기 때문에, 동적 계획법을 사용할 수 없음

Stagecoach문제

• Stagecoach: 역마차
  
  
• 문제 정의
  • 미국에서 동부/서부에서 금광이 개발이 되었을 때, 사람들이 이동을 하는 상황
  • 이동 중, 중간에 있는 도시들을 거쳐서 금광이 있는 지역으로 이동할 때, 어떻게하면 빨리 갈 수 있는지 푸는 문제
• 문제 그림
  
  
• 문제 풀이 방향
  • 가장 목적지가 가까운 도시부터 먼 쪽으로 순차적으로 문제를 풀어나가야함

문제 해결

• 단계 4
  
  
  
• 단계 3
  
  
  
• 단계 2
  
  
  
• 단계 1
  
  
  

3-2. 방문판매원 문제 (Traveling Salesman Problem, TSP)

도입 예시

• 물류 최적화의 문제
• 택배 배송 문제
• 물류창고 자동화 로봇 운영 문제
• 통학 버스
• 가장 빨리 드릴 공정을 끝내는 법
• 대통령 선거 후보자가 유세 일정을 찾는 방법

문제 해결

• 문제 정의: 해당 도시를 단 한번만 방문하여 최소 경로를 구하라
• 문제 그림
  
• 문제 해결
  • 상태
    
    
  • 행동: 현재 기준으로 방문하지 않은 도시들 중, 어떤 도시를 방문할 것인지 결정
    
  • 가치함수($`V(N,n)`$): 현재 N에 속한 도시를 방문하였고, n 위치에 있을 때 나머지 방문하지 않은 도시를 방문하고 원점으로 돌아가는데 걸리는 소요 시간 (최소 거리, 최소 시간)
    
    
    
• TSP문제의 모든 가능한 상태
  
  
• 가치함수값 계산
  
  
  
  
  
• 최단 경로
  

3-3. 배낭문제 (Knapsack Problem)

• 문제 정의:
  • 물건을 담을 수 있는 최대 무게가 정해짐
  • 일정한 가치와 무게가 있는 짐들을 가방에 담아야 함
  • 가방에 담긴 짐들의 총 가치의 합이 최대가 되도록 짐을 고르는 방법은?
• 활용 예시
  • 예산에 제약이 있는 지방정부의 프로젝트 실행할 경우
    • 문제점: 주민들이 느끼는 혜택이 프로젝트에 따라 차이가 발생
    • 문제 해결 방법: 한정된 예산으로 프로젝트 수행 시 주민들의 이익을 최대화하는 방법을 결정
  • 투자 시 포트폴리오를 결정할 경우
    • 문제점: 투자할 예산이 정해져 있고 포트폴리오는 여러 개임
    • 문제 해결 방법: 기대수익을 최대화할 수 있는 포트폴리오를 결정

도입 예시

• 어떤 물건을 훔쳐야할까? ==> 단위 무게 당 가치가 가장 높은 물건 (물론.. 도둑질은 하면 안된다!)
  

문제 해결

• 상태, 행동, 가치 함수를 결정
• 재귀방정식의 최적화 원리를 만족시키는 방법을 도출

상태, 행동, 가치함수 결정

• 상태
  
  
• 행동: 가방에 물건을 선택해서 담는다
• 가치함수: 7개의 상자가 있고, 가방의 무게가 15일 때 내가 이 가방에 담을 수 있는 물건의 가치의 최대값
  
  

재귀 방정식의 최적화 원리를 만족시키는 방법

• $`v(n, x)`$:n개 아이템에서 우리가 넣을 수 있는 제품의 최대값
• n번째 아이템을 넣었을 때 $`v(n, x)`$의 상태