Dynamic Programming.

Slides:



Advertisements
Similar presentations
알고리즘 (algorithms) The word algorithm is a corruption of early English algorisme, which came from Latin algorismus, which came from the name of the Persian.
Advertisements

15 장. 알고리즘의 설계 알고리즘 설계 학습목표 기본 패턴 패턴의 한계점 일곱 가지 패턴의 알고리즘 설계 기법을 이해한다.
Lecture 9 프로그램 실행의 비용 computation cost – 시간 time, 메모리 memory – tractable vs intractable problems.
Multimedia Programming 04: Point Processing Departments of Digital Contents Sang Il Park.
Chapter 7 ARP and RARP.
Shortest Path Algorithm
Activation Records & Recursion
Internet Computing KUT Youn-Hee Han
제 6 장 그래프 6.1 그래프의 정의 6.2 용어 및 표현법 6.3 그래프의 표현 방법 6.4 그래프의 순회와 신장 트리
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
Dynamic Programming.
REINFORCEMENT LEARNING
Discrete Math II Howon Kim
Ch.04 Greedy Method (탐욕적 방법)
CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 생능출판사 학기 데이터구조.
CHAP 10:그래프 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 10 : 그래프 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 62).
쉽게 배우는 알고리즘 5장. 검색트리
Multimedia Programming 06: Point Processing3
On the computation of multidimensional Aggregates
Genetic Algorithm 신희성.
쉽게 배우는 알고리즘 9장. 그래프 알고리즘.
Dynamic Programming.
Ch. 10 Algorithm Efficiency & Sorting
Ch. 10 Algorithm Efficiency & Sorting
Internet Computing KUT Youn-Hee Han
 Branch-and-Bound (분기한정)
알고리즘(Algorithm) – Greedy Method (탐욕적 방법)
Chapter 10 그래프(graph) SANGJI University Kwangman KO
Chapter 2. Finite Automata Exercises
10장. 그래프 알고리즘.
그래프(graph) 연결되어 있는 객체 간의 관계를 표현하는 자료구조 가장 일반적인 자료구조 형태
계수와 응용 (Counting and Its Applications)
9장. 동적 프로그래밍Dynamic Programming (DP)
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
자료구조(SCSC) Data Structures
동적 계획(Dynamic Programming)
Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법)
Ch.02 Divide and Conquer (분할정복)
Course Guide - Algorithms and Practice -
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
Chap. 1 Data Structure & Algorithms
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
5장 동적계획법 (Dynamic Programming)
Discrete Math II Howon Kim
Operating System Multiple Access Chatting Program using Multithread
동적계획법과 최적화 문제 Dynamic Programming을 사용한 최적화 문제를 해결하는 알고리즘 설계 절차
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
CHAP 1:자료구조와 알고리즘.
이산수학(Discrete Mathematics)
Internet Computing KUT Youn-Hee Han
CHAP 10 : 그래프.
스케줄링 (Scheduling) 시스템 내부시간(time in the system): 스케줄링 문제
점화와 응용 (Recurrence and Its Applications)
알고리즘 강의 슬라이드 2 분할정복 제 2 장 분할정복 도경구역, 알고리즘, 사이텍미디어, 1999.
DP 기반 최단경로 – 자료 구조 및 전략 (1/4) 주어진 그래프에 대한 W:인접행렬(adjacent matrix) 표현 W
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
이산수학(Discrete Mathematics)
The general form of 0-1 programming problem based on DNA computing
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
알고리즘(Algorithm) – Divide and Conquer (분할정복)
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
이산수학(Discrete Mathematics) 수열과 합 (Sequences and Summations)
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
3D Vision This course is a basic introduction to parts of the field of computer vision. This version of the course covers topics in 'early' or 'low' level.
[CPA340] Algorithms and Practice Youn-Hee Han
Traditional Methods – Part 1
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
Chapter 7: Deadlocks.
Presentation transcript:

Dynamic Programming

Dijkstra’s Algorithm Goal: Find the shortest path from s to t 2 3 s 6 24 3 9 s 18 14 2 6 6 4 30 19 11 15 5 5 6 20 16 t 7 44

       S = { } PQ = { s, 2, 3, 4, 5, 6, 7, t } 2 3 s 6 4 5 t 7 24 3 9 s 18 14  2 6 6  4 30  19 11 15 5 5 6 20 16 t 7 44  

9 14 15        S = { s } PQ = { 2, 3, 4, 5, 6, 7, t } X 2 3 s X 24 3 9 s 18 14  X 14 2 6 6  30  4 19 11 15 5 5 6 20 16 t 7 44   15 X

9 14 15        S = { s, 2 } PQ = { 3, 4, 5, 6, 7, t } X 2 3 s X 24 3 9 s 18 14  X 14 2 6 6  30  4 19 11 15 5 5 6 20 16 t 7 44   15 X

9 15        S = { s, 2 } PQ = { 3, 4, 5, 6, 7, t } X 33 X 2 3 s 24 3 9 s 18 14  X 14 2 6 6  30  4 19 11 15 5 5 6 20 16 t 7 44   15 X

32 9 14 15        S = { s, 2, 6 } PQ = { 3, 4, 5, 7, t } X 33 X 24 3 9 s 18 14  X 14 2 6 6  44 30  X 4 19 11 15 5 5 6 20 16 t 7 44   15 X

9 14 15     X    S = { s, 2, 6, 7 } PQ = { 3, 4, 5, t } 32 X 33 24 3 9 s 18 14  X 14 2 6 6  44 X 35 30  X 4 19 11 15 5 5 6 20 16 t 7 44  15 59  X X

32 9 14 35 15        S = { s, 2, 3, 6, 7 } PQ = { 4, 5, t } X X 24 3 9 s 18 14  X 14 2 6 6 35  4 30  X 19 11 15 5 5 6 20 16 t 7 44 51   15 X X X

S = { s, 2, 3, 5, 6, 7 } PQ = { 4, t } 32  X 9 2 24 3 9 s 18 14  X 14 2 6 6 45  X 34 4 30 19 11 15 5 5 6 20 16 t 7 44 50  15 X

S = { s, 2, 3, 4, 5, 6, 7 } PQ = { t } 32  X 9 2 24 3 9 s 18 14  X 14 2 6 6 45  X 34 4 30 19 11 15 5 5 6 20 16 t 7 44 50  15 X

Dynamic Programming In mathematics and computer science, dynamic programming is a method of solving complex problems by breaking them down into simpler steps - wikipedia

Algorithms Review Backtracking Greedy Algorithm Dynamic Programming search every possible solution optimal guaranteed inefficient Greedy Algorithm find the best at each stage – MST not always optimal needs a proof Dynamic Programming efficient recursive algorithm

Recursive Algorithm Divide-and-Conquor Dynamic Programming top-down solution Fibonnaci can be inefficient duplicated computations Dynamic Programming bottom-up recursive and solve above limitations Fibonacci calculate F(1), F(2), .... and store the results use them to calculate F(n) F(n) = F(n-1) + F(n-2) = {F(n-2)+F(n-3)} + {F(n-3)+F(n-4)} = [{F(n-3)+F(n-4)}+{F(n-4)+F(n-5)}] +[{F(n-4)+F(n-5)}+{F(n-5)+F(n-6)}] = ...

Binomial Coefficient Redundancy ! n k n - 1 k - 1 n - 1 k = + int bino(int n, int k) { if (k==0 || n==k) return 1; else return bino(n-1, k-1) + bino(n-1, k); } {bino(n-2, k-2) + bino(n-2, k-1)} + {bino(n-2, k-1) + bino(n-2, k)} Redundancy !

Binomial Coefficient (2) kC0 = kCk = 1 2C1 = 1C0 + 1C1 3C1 = 2C0 + 2C1 3C2 = 2C1 + 2C2 4C1 = 3C0 + 3C1 4C2 = 3C1 + 3C2 ... ... ... ... 1 2 3 4 6 bino(int n, int k) { long bc[n][k]; for( int i=0; i<=n; i++) for( int j=0; j<=min(i,k); j++ ) if( j==0 || j==i ) bc[i][j]=1; else bc[i][j] = bc[i-1][j-1] + bc[i-1][j]; return bc[n][k]; }

Floyd’s Algorithm find all pairs shortest paths Floyd Alg. apply Dijkstra alg. for each vertex inefficient Floyd Alg. number each vertex from 1 to n start from W(0)=W, ends with W(n) which is a set of shortest paths – bottom up compute W(k) from W(k-1) - recursion typical dynamic programming problem

Floyd’s Algorithm W(k)[i][j] Adjacent Matrix: W shortest path from vi to vj the path traverses vertices among {v1, v2, ... , vk} 1 v1 v2 9 3 5 1 3 v5 v4 2 v3 3 4

Floyd’s Algorithm W(k)[i][j] = min(W(k-1)[i][j], W(k-1)[i][k]+W(k-1)[k][j]) shortest path from vi to vj using {v1, v2, … , vk} Case 1: the path does not visit vk Ex) W(5)[1][3] = W(4)[1][3] = 3 Case 2: the path visits vk Ex) W(2)[5][3] = W(1)[5][2] + W(1)[2][3] = 4+3 = 7 Case 1 Case 2

플로이드 알고리즘 <4> 데이터 구조 초기화 인접배열

플로이드 알고리즘 <5> 재귀 관계식 계산 W(k)[i][j] = min(W(k-1)[i][j], W(k-1)[i][k]+W(k-1)[k][j])

String Matching Edit Distance number of any following costs to make two strings match subs – match insertion deletion after any above operation, you are given shorter strings to match

delete remaining tail of t the characters match or substitute to make them match – i-1 and j-1 insert a char to s – append the last char of t to s, so compare s with t[0:n-1] delete a char from s – s is shorter, t is the same

Algorithm Review The number of function call grows exponentially The maximum number of distinct function call is Let’s make a table like .... the number of unique function calls is |s| * |t|

cell[i, j] means cost to make two strings match s[0..i] and t[0..j] worst case: subs all chars – diagonal values are i computing a cell requires three cells

엘리베이터 최적화 <1> 엘리베이터 최적화 문제 소개 모든 사람들이 입력한 층에서 엘리베이터가 멈춘다면 최악의 경우, 모든 층에서 멈춰야 하는 경우가 발생하므로, 최적화가 필요하다. 탑승객들은 엘리베이터가 움직이기 전에 원하는 층을 입력한다. 엘리베이터가 멈추는 횟수는 k번으로 제한되어 있다고 가정. 계단을 올라가는 것과 내려가는 것 사이에 차이가 없다고 가정. 걸어 올라가거나 내려가는 사람 수가 같은 층이 여러 명 존재할 경우 가장 낮은 층에 세운다. 반드시 탑승객이 내리겠다고 한 위치에서만 서는 것은 아니다. 예) 27층과 29층에서 내리는 탑승객이 있을 경우 28층에서 멈출 수 있음. 문제의 목적은 걸어서 올라가거나 내려가야 하는 사람 수를 최소화할 수 있는 층에 멈추는 것이다. 이때, 사람 수를 최소화한다는 것은 걷는 비용의 최소화를 의미한다.

엘리베이터 최적화 <2> 동적 프로그래밍을 이용한 해결 방법 f2층 f1층 동적 프로그래밍은 재귀 알고리즘을 바탕으로 함을 생각하자. k번째 멈출 층을 결정하는 것은 k-1번째 멈추는 모든 가능한 풀이의 비용에 따라 결정할 수 있다. 우선, f1층에서 선 후에 f2층에서 서는 경우를 생각해 보자. 이때, f2층은 목적지가 f1층 이하인 탑승객과는 상관이 없다. 즉, 문제를 두 조각으로 나눌 수 있다. 이 부분에서 동적 프로그래밍을 사용할 수 있음을 알 수 있다. f2층에서 내릴 탑승객은 f1층 위의 탑승객들만 관계되어 있다. 물론 f1층과 f2층 사이의 탑승객들은 f1층 f2층 중에서 한 곳에 내릴 것이다. f2층 f1층

엘리베이터 최적화 <3> mi,j i층 까지, j번 멈추면서 모든 승객을 운반하기 위한 최소 비용을 mi,j으로 정의한다. 그렇다면, (j+1)번째 멈출 위치는 이전에 i층에서 j번째로 멈추는 층보다 높으며, 이것은 i층보다 위로 올라갈 사람에게만 유효하다. 즉, 어느 층이 더 가까운지를 바탕으로 새로 멈추게 될 층과 i층에서 내릴 승객 으로 나눠야 한다. j+1번째 stop! ?층 i층 k층 j번 이동

엘리베이터 최적화 <3> mi,j=min{k=0…i-1}{mk,j-1 - walk(k,∞)+walk(k,i)+walk(i,∞)} 마지막으로 (j번째) 멈춘 층이 i층이었다면, 그 전에 (j-1번째) 멈췄던 층은 i층보다 작은 어떤 k층이었다. 그렇다면, mi,j은 mk,j-1로부터 k층 위로 올라가는 모든 승객에 대한 비용(walk(k,∞)) 을 빼고, i층에 멈추는 비용(walk(k,i)+walk(i,∞))을 더하면 된다. 이 문제를 해결하는데 있어 가장 중요한 것은 a층에서 멈춘 다음 b층에서 멈출 때, 승객들이 걸어서 이동한 층수의 총합을 계산하는 walk(a,b) 함수이다. walk(i,∞) walk(k,∞) j번째 stop! i층 k층 walk(k,i) j-1번 이동

Similar Problems A numerical sequence is monotonically increasing if the ith element is at least as big as the (i − 1)st element. The maximum monotone subsequence problem seeks to delete the fewest number of elements from an input string S to leave a monotonically increasing subsequence. Thus a longest increasing subsequence of “243517698” is “23568.” Find the longest sequence of elephants whose weights are increasing but whose IQ’s are decreasing. Can this be done as a special case of edit distance?