동적 계획 알고리즘

(1)

동적 계획 알고리즘

명지대학교 컴퓨터공학과

이 충기

(2)

지난 주 강의 내용

• 탐욕적인 접근 방법

• 거스름돈 구하기

• 최소비용 신장 트리 찾기

• 단일 출발점 최단경로 찾기

• 0-1 배낭 채우기

(3)

이번 주 강의 내용

• 동적 계획 알고리즘의 개념, 전략, 설계 과정

• 행렬 곱셈

• 모든 쌍 최단 경로 찾기

• 배낭 채우기

(4)

동적 계획 알고리즘

• _________________은 하향식 해결법으로서 나누어진 부분 문제들 사이에 서로 상관 관계가 없는 문제를 해결하는 데 적합하다.

• 토끼문제 알고리즘의 경우에는 나누어진 부분문제들이 서로 연관이 있다. 즉, 분할 정복을 적용하여 알고리즘을 설계하게 되면 같은 계산을 한 번 이상 하는 결과를 초 래하게 되므로 효율적이지 않다.

• 동적 계획 알고리즘은 ____ 해결법을 사용하여 알고리즘 을 설계하는 방법이다. 이 방법은 분할정복식 방법과 마 찬가지로 문제를 나눈 후에 나누어진 부분문제들을 먼 저 푼다. 그러나 이미 풀어서 답을 알고 있는 부분문제 의 결과가 다시 필요한 경우에는 반복하여 계산하는 대 신에 이미 계산된 결과를 그냥 사용한다.

(5)

• 분할 정복 알고리즘의 부분문제들 사이의 관계: A는 B와 C로 분할되고, B는 D와 E로 분할되는데, D와 E의 해를 취합하여 B의 해를 구한다. 단, D, E, F, G는 각각 더 이상 분할할 수 없는 (또는 가장 작은 크기의) 부분문제들이다.

• 마찬가지로 F와 G의 해를 취합하여 C의 해를 구하고, 마 지막으로 B와 C의 해를 취합하여 A의 해를 구한다.

분할 정복과 동적 계획 비교

(6)

분할 정복과 동적 계획 비교(계속)

• 동적 계획 알고리즘은 먼저 최소 단위의 부분 문제 D, E, F, G의 해를 각각 구한다.

그 다음에

• D, E, F의 해를 이용하여 B의 해를 구한다.

• E, F, G의 해를 이용하여 C의 해를 구한다.

• B와 C의 해를 구하는데 E와 F의 해 모두를 이용한다.

• 분할 정복 알고리즘은 부분문제의 해를 중

복 사용하지 않는다.

(7)

분할 정복과 동적 계획 비교(계속)

• 동적 계획 알고리즘에는 부분문제들 사이 에 ______ 관계가 존재한다.

– 예를 들면, D, E, F의 해가 B를 해결하는데 사 용되는 의존적 관계가 있다.

• 이러한 관계는 문제 또는 입력에 따라 다

르고, 대부분의 경우 뚜렷이 보이지 않아

서 ‘함축적인 순서’ (implicit order)라고 한

다.

(8)

동적 계획 알고리즘 전략

• 문제를 더 작은 _________들로 분할한다.

• 작은 부분 문제들을 먼저 풀고 그 결과를 ____한다.

• 나중에 우리가 한 결과를 필요로 할 때마 다 그 결과를 다시 하는 대신에 _

사용한다.

(9)

동적 계획 알고리즘 설계 과정

1. 우리가 풀고자 하는 문제의 ___________(form)을 정의한다.

2. 이 문제들을 풀기 위한 ___를 정한다. 한 문제는 순서에서 앞선 문제들에 대한 해법을 이용하여 풀 수 있다.

3. 문제 풀이 순서의 처음에 있는 문제들은 자명한 해법들을 가져야 한다.

4. 문제풀이 순서의 목록에 나와 있는 순서대로 문제들을 푼 다. 이미 풀은 문제들에 대한 해법들을 저장하기 위해 표 를 사용한다. 목록의 마지막 문제는 본래의 문제여야 한 다.

(10)

행렬 곱셈 적용 예

(11)

행렬 곱셈 적용 예 (계속)

행렬 A와 B의 곱은 각 대학이 구입한 상품들의 총액과 총 무게를 나 타낸다:

14 9 3 20000 0.5 5380000 28 AB= 2 11 15 500000 2 = 8540000 38 0 12 17 200000 1 9400000 41 5 2 3 1700000 9.5

(12)

행렬 곱셈 문제







 ^p

k

kj ik pj

ip j

i j

i

ij a b a b a b a b

c

1 2

2 1

1 ...

(13)

예: 행렬 곱셈 문제

(14)

행렬 곱셈 (계속)

1

100 1100 1005

100 100 



5 100

 5 100 

000 , 50 5

100 100

000 , 10 100

1 100









 수 곱셈의

000 , 60

 5 100

500 5

1 100

500 5

100 1









1000

1

100 15

(15)

행렬 곱셈 문제

j k i r r r ₁ j)

, 1 matmult(k k)

matmult(i,    _

  

(16)

분할 정복 해법



(17)

동적 계획 알고리즘

(18)

예: 동적 계획 알고리즘 수행 과정

20

*

10 20*50 50*1 1*100

110

m m₂₂0 m₃₃0 m₄₄0 000

,

1210 m

200 ,

131 m

200 ,

142 m

000 ,

231 m

000 ,

24 3 m

000 ,

345 m

m14

)

( ₂ ₃ ₄

1 M M M

M   

4 3

2

1 M M M

M   

4 3

2

1 M M M

M   

20

10 20100

50

10 50100

! 2200

100

* 1

* 10 0 1200

최선





 100

1

110

m m₂₄3,000

000 ,

1210

m ^m³⁴^⁵^,⁰⁰⁰

200 ,

131

m m₄₄0

000 , 23

100

* 20

* 10 000 , 3 0





000 , 65

100

* 50

* 10 000 , 5 000 , 10





1 10

(19)

예: 동적 계획 알고리즘 수행 과정

3 2

1 )

(M  M M

50

10 501

000 ,

12 10

m m₃₃0

)

( ₂ ₃

1 M M

M  

20

10 201

110

m m₂₃1,000

500 , 10

1

* 50

* 10 0 000 , 10





최선!

6

) 1 2 )(

1 ( 2

) 1 ) (

(

1



 

 





^ 



n n

n n l l n

n

l

) 6 (

) 1 )(

1 ( 6

2 3

2 2

3 2

3 2 3

n n n

n n

n n n

n        



1200

1

* 20

* 10 1000 0





(20)

모든 쌍 최단 경로 찾기

예: 한 도시에서 다른 도시로 가는 최단 경로를

찾아라

(21)

모든 쌍 최단 경로 찾기 문제

가중치를 포함한 방향 그래프가 주어지

면 각 정점에서 모든 다른 정점으로 가

는 가장 짧은 경로를 찾아라. 즉, 가중치

를 포함한 방향 그래프를 나타내는 행

렬 W 가 주어지면 행렬 D [1.. N , 1.. N ]을

구하라. D [i, j]는 정점 i에서 정점 j로 가

는 가장 짧은 경로의 비용이다.

(22)

모든 쌍 최단 경로 찾기

(23)

무작정 알고리즘(brute – force algorithm)

(24)

동적 계획 알고리즘 아이디어

• 동적 계획 알고리즘으로 모든 쌍 최단 경로 문제를 해결 하려면 먼저 부분문제들을 찾아야 한다.

• 이를 위해 일단 그래프의 정점의 수가 적을 때를 생각해 보자.

• 그래프에 3개의 정점이 있는 경우, 정점 i에서 정점 j까지 의 최단 경로를 찾으려면 2가지 경로, 즉, 정점 i에서 정 점 j로 직접 가는 경로와 정점 1을 경유하는 경로 중에서 짧은 것을 선택하면 된다.

i j

1

(25)

동적 계획 알고리즘 아이디어

• 또 하나의 중요한 아이디어

– 경유 가능한 정점들을 정점 1로부터 시작하여, 정점 1 과 2, 그 다음엔 정점 1, 2, 3으로 하나씩 추가하여, 마 지막에는 정점 1∼n까지의 모든 정점을 경유 가능한 정점들로 고려하면서, 모든 쌍의 최단 경로의 거리를 계산한다.

• 부분문제 정의:

단, 입력 그래프의 정점을 각각 1, 2, 3, ⋯, n이라 하자.

D

_ij^k

= 집합 {1, 2, ⋯, k}에 있는 정점만을 경유 가능

한 정점들로 고려하여, 정점 i로부터 정점 j

까지의 모든 경로 중에서 가장 짧은 경로의

거리

(26)

동적 계획 알고리즘 아이디어

• 여기서 주의할 것은 정점 1에서 정점 k까지의 모 든 정점들을 반드시 경유하는 경로를 의미하는 것 이 아니다.

• 심지어는 D

_ij^k

는 이 정점들을 하나도 경유하지 않 으면서 정점 i에서 정점 j에 도달하는 경로, 즉 연 결선 (i, j)가 최단 경로가 될 수도 있다.

• 여기서 k≠i, k≠j이고, k=0인 경우, 정점 0은 그래프

에 없으므로 어떤 정점도 경유하지 않는다는 것을

의미한다. 따라서D

_ij⁰

은 입력으로 주어지는 연결선

(i, j)의 가중치이다.

(27)

동적 계획 알고리즘 아이디어

D

_ij¹

i j

1

(28)

동적 계획 알고리즘 아이디어

• 다음으로 i에서 정점 2를 경유하여 j로 가는 경로 의 거리와 D

_ij¹

중에서 짧은 거리를 D

_ij²

로 정한다.

단, 정점 2를 경유하는 경로의 거리는 D

_i2¹

+ D

_2j¹

이다.

• 모든 쌍 i와 j에 대하여 D

_ij²

를 계산하는 것이 그 다음으로 큰 부분 문제들이다. 단, i≠2, j≠2이다 .

i j

2 D

_ij²

(29)

동적 계획 알고리즘 아이디어

• 정점 i에서 정점 k 를 경유하여 j로 가는 경로의 거리와 D

_ij^k-1

중에서 짧은 것으로 정한다. 단, 정 점 k를 경유하는 경로의 거리는 D

_ik^k-1

+ D

_kj^k-1

이 고, i≠k, j≠k이다.

i j

k

D

_ij^k

(30)

동적 계획 알고리즘 아이디어

• 이런 방식으로 k가 1에서 n이 될 때까지 D

_ij^k

를 계산해서, D

_ijⁿ

, 즉, 모든 점을 경유

가능한 점들로 고려된 모든 쌍 i와 j의 최단

경로의 거리를 찾는 방식이 플로이드의 모

든 쌍 최단 경로 알고리즘이다.

(31)

동적 계획 주 아이디어

x ^y

모두L내에있다

) ( )

1 ( ) 0

( ,D ,....,D ⁿ D

i j

(32)

예 1: 모든 쌍 최단 경로 찾기

예 1: 0 1 ∞ 1 5 9 0 3 2 ∞ ∞ ∞ 0 4 ∞ ∞ ∞ 2 0 3 3 ∞ ∞ ∞ 0

1

v v2

3 v 4

v 5

v

1

1 2

2

3 3

3

4 5

9

5 ] 5 ][

2 [

5 ] 5 ][

2 [

14 ]

5 ][

2 [

14 ]

5 ][

2 [

14 ]

5 ][

2 [

) 5 (

) 4 (

) 3 (

) 2 (

) 1 (



D D D D D



W D⁽⁰⁾

5 4

2

5 4

2

5 1

2

5 1

2

5 1

2

v v

v

v v

v

v v

v

v v

v

v v

v



6 ] 3 ][

5 [

7 ] 3 ][

5 [

7 ] 3 ][

5 [

] 3 ][

5 [

) 4 (

) 3 (

) 2 (

) 1 (







D D D D

3 4

1 5

3 2

1 5

3 2

1 5

v v



(33)

모든 쌍 최단 경로 찾기

• 어떻게 로부터 을 구하는가?

고려해야 할 새 경로

을 통과하는 정점 i 부터 정점 j 까지 경로는 두 가지 경우로 나눌 수 있다.

- 을 통과하지 않는 경로

이는 내의 정점들만을 통과하는 정점 i 부터 정점 j 까지의 경로들의 집합이다.

- 을 통과하는 경로

= MIN(MIN cost(p), MIN cost(p)) MIN cost(p)=

에 속하는 모든 경로 p는 위 그림에서 보여진 대로 2개의 경로들로 나누어 질 수 있다.

q - 내의 정점들만을 통과하는 정점 i 부터 정점 k + 1 까지의 경로

)

D(k D⁽^k^¹⁾

} ,...., ,

{v₁ v₂ v_k L

} ,

,...

,

{v₁ v₂ v_k v_k_₁

P1 vk1

} ,...

,

{v₁ v₂ v_k

P2 vk1 ) 1 (k

Dij D_ij^(k⁾

P1

p pP₂

P2

} ,...

,

{v₁ v₂ v_k

P1

p

(34)

모든 쌍 최단 경로 찾기 (계속)

} ,...

,

{v₁ v₂ v_k

) ,

( ⁽ ⁾ _, ₁⁽ ⁾ ₁_, ⁽ ⁾

) 1

( k

j k k

k i k

ij k

ij MIN D D D

D ^  _  _

P2

p _

(35)

예 2: 모든 쌍 최단 경로 찾기

예 2: 1 2 3 4 5 1 0 1.5 1 0.8

W =2 2 0 ∞ 1.8 ∞ 3 1.4 ∞ 0 0.6 1 4 1.5 1.5 0.5 0 0.9

5 2 ∞ 1.2 ∞ 0

인천 서울

용인 수원

대전

1 v 2

v

3 v 4

v

5 v

5 . 1

5 .

1 1

1 5 . 8 1

. 1

2 8 . 0

5 . 0

6 . 0

2 . 9 1

. 0

4 .

1 2

∞

W D⁽⁰⁾ 

7 . 1 ] 5 ][

1 [

7 . 1 ] 5 ][

1 [

2 ] 5 ][

1 [

] 5 ][

1 [

] 5 ][

1 [

) 5 (

) 4 (

) 3 (

) 2 (

) 1 (











D D D D D

1 . 2 ] 2 ][

3 [

1 . 2 ] 2 ][

3 [

9 . 2 ] 2 ][

3 [

9 . 2 ] 2 ][

3 [

9 . 2 ] 2 ][

3 [

) 5 (

) 4 (

) 3 (

) 2 (

) 1 (



D D D D

D v3  v1  v2

5 3

1 v v

v  

5 4

1 v v

v  

5 4

1 v v

v  

2 4

3 v v

v  

1 1

8 .

0 0.9

4 .

1 1.5

2 4

3 v v

v  

2 1

3 v v

v  

2 1

3 v v

v  

(36)

예 2: 모든 쌍 최단 경로 찾기 (계속)

L = {서울, 인천, 수원} L = {서울, 인천, 수원, 용인}

서울

대전

서울

용인

대전

(37)

모든 쌍 최단 경로 찾기 알고리즘

(38)

모든 쌍 최단 경로 찾기 알고리즘 2

(39)

시간복잡도

• 모든 쌍 최단 경로 찾기 알고리즘의 시간 복잡도는 위의 예제에서 보았듯이 각 k에 대해서 모든 i, j 쌍에 대해 계산되므로, 총 nxnxn = n

³

회 계산이 이루어지고, 각 계산 은 O(1) 시간이 걸린다.

• 따라서 모든 쌍 최단 경로 찾기 알고리즘

의 시간복잡도는 O(n

³

)이다.

(40)

응용

• 네이버와 구글 (Google) 웹사이트의 지도 서비스

• 자동차 네비게이션 서비스

• 지리 정보 시스템 (GIS)에서의 네트워크 분석

• 통신 네트워크와 모바일 통신 분야

• 게임

• 산업 공학,경영 공학의 Operations Research (운영 연구)

• 로봇 공학

• 교통 공학

• VLSI 디자인 분야 등

(41)

배낭 채우기 문제

• 배낭 (Knapsack) 문제는 n 개의 물건과 각 물건 i의 무게 w

_i

와 가치 v

_i

가 주어 지고, 배낭의 용량은 C일 때, 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 단, 배낭에 담은 물건의 무게의 합이 C를 초과하지 말아야 하고, 각 물건은 1개씩만 있다.

6kg

4kg 5kg

3kg

10만원 30만원

50만원

(42)

배낭 채우기 문제

• 배낭 문제는 제한적인 입력에 대해서 동적 계획 알고리즘으로 해결할 수 있 다.

• 먼저 배낭 문제의 부분 문제를 찾아내기 위해 문제의 주어진 조건을 살펴보 면 물건, 물건의 무게, 물건의 가치, 배낭의 용량, 모두 4가지의 요소가 있다.

• 이중에서 물건과 물건의 무게는 부분 문제를 정의하는데 반드시 필요하다.

• 왜냐하면 배낭이 비어 있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것과 안 담는 것을 현재 배낭에 들어 있는 물건의 가치의 합에 근거하여 결 정해야 하기 때문이다.

• 또한 물건을 배낭에 담으려고 할 경우에 배낭 용량의 초과 여부를 검사해야 한다.

(43)

배낭 채우기 문제

• 따라서 배낭 문제의 부분문제를 아래와 같이 정의할 수 있다.

• K[i, w] = 물건 1 ∼ i까지만 고려하고, (임시) 배낭의 용량이 w일 때 의 최대 가치

단, i = 1, 2, ⋯, n이고, w = 1, 2, 3, ⋯, C이다.

• 그러므로 문제의 최적해는 K[n, C]이다.

• 여기서 주의하여 볼 것은 배낭의 용량이 C이지만, 배낭의 용량을 1 부터 C까지 1씩 증가시킨다는 것이다.

• 이 때문에 C의 값이 매우 크면, 알고리즘의 수행시간이 너무 길어지 게 된다.

• 따라서 다음의 알고리즘은 제한적인 입력에 대해서만 효용성을 가 진다.

(44)

배낭 채우기 알고리즘

입력: 배낭의 용량 C, n개의 물건과 각 물건 i의 무게 w_i와 가치 v_i, 단, i = 1, 2, ⋯, n

반환 값: K[n, C]

1. for i = 0 to n K[i, 0]=0 // 배낭의 용량이 0일 때

2. for w = 0 to C K[0,w]=0 // 물건 0이란 어떤 물건도 고려하지 않을 때 3. for i = 1 to n

4. for w = 1 to C // w는 배낭의 (임시) 용량

5. if ( w_i > w ) // 물건 i의 무게가 임시 배낭 용량을 초과하면 6. K[i, w] = K[i-1, w]

7. else // 물건 i를 배낭에 담지 않을 경우와 담을 경우 고려 8. K[i ,w] = max{K[i-1, w], K[i-1, w-w_i] + v_i}

9. return K[n, C]

(45)

배낭 채우기 알고리즘 설명

• Line 1에서는 2차원 배열 K의 0번 열을 0으로 초기화시킨다.

그 의미는 배낭의 (임시) 용량이 0일 때, 물건 1∼n까지 각각 배낭에 담아보려고 해도 배낭에 담을 수 없으므로 그에 대한 각각의 가치는 0일 수밖에 없다는 뜻이다.

• Line 2에서는 0번 행의 각 원소를 0으로 초기화시킨다. 여기서 물건 0이란 어떤 물건도 배낭에 담으려고 고려하지 않는다는 뜻이다. 따라서 배낭의 용량을 0에서 C까지 각각 증가시켜도 담을 물건이 없으므로 각각의 최대 가치는 0이다.

• Line 3 ~ 8에서는 물건을 1에서 n까지 하나씩 고려하여 배낭 의 (임시) 용량을 1에서 C까지 각각 증가시키며, 다음을 수행 한다.

(46)

배낭 채우기 알고리즘 설명

• Line 5 ~ 6에서는 현재 배낭에 담아보려고 고려하 는 물건 i의 무게 w

_i

가 (임시) 배낭 용량 w보다 크 면 물건 i를 배낭에 담을 수 없으므로, 물건 i까지 고려했을 때의 최대 가치 K[i, w]는 물건 (i-1)까지 고려했을 때의 최대 가치 K[i-1, w]가 된다.

• Line 7 ~ 8에서는 만일 현재 고려하는 물건 i의 무

게 w

_i

가 현재 배낭의 용량 w보다 같거나 작으면,

물건 i를 배낭에 담을 수 있다. 그러나 현재 상태에

서 물건 i를 추가로 배낭에 담으면 배낭의 무게가

(w+w

_i

)로 늘어난다. 따라서 현재의 배낭 용량인 w

를 초과하게 되어, 물건 i를 추가로 담을 수는 없다.

(47)

K[i-1, w]

K[i-1, w-w

_i

]

K[i, w]

물건 1 ∼(i-1)까지 고려하여 현재 배낭의 용량이 (w - w_i) 인 경우의 최대 가치

물건 i의 가치 v

i

+

물건 1 ∼ (i-1)까지 고려하여 현재 배낭의 용량이 w인 경 우의 최대 가치

물건 i

0

1

배낭에서 물건 i를 담을 공간을 마련

(48)

배낭 채우기 알고리즘 설명

• 그러므로 앞의 그림에서와 같이, 물건 i를 배낭에 담기 위해서 는 2가지 경우를 살펴보아야 한다.

• 물건 i를 배낭에 담지 않는 경우 K[i,w] = K[i-1,w]가 된다.

• 물건 i를 배낭에 담는 경우, 현재 무게인 w에서 물건 i의 무게 인 w_i를 뺀 상태에서 물건을 (i-1)까지 고려했을 때의 최대 가 치인 K[i-1,w-w_i]와 물건 i의 가치 v_i의 합이 K[i,w]가 되는 것이 다.

• Line 8에서는 이 2가지 경우 중에서 큰 값이 K[i, w]가 된다.

(49)

배낭 채우기 알고리즘 설명

• 배낭 문제의 부분 문제간의 함축적 순서는 다음과 같다.

즉, 2개의 부분 문제 K[i - 1, w - w_i]과 K[i - 1, w]가 미리 계산되어 있어야만 K[i, w]를 계산할 수 있다.

(50)

시간복잡도

• 하나의 부분 문제에 대한 해를 구할 때의 시 간복잡도는 line 5에서의 무게를 한 번 비교 한 후 line 6에서는 1개의 부분문제의 해를 참 조하고, line 8에서는 2개의 해를 참조한 계산 하므로 O(1) 시간이 걸린다.

• 그런데 부분 문제의 수는 배열 K의 원소 수인 nC개이다. 여기서 C는 배낭의 용량이다.

• 따라서 배낭채우기 알고리즘의 시간복잡도는

O(1)xnxC = O(nC)이다.

(51)

동적 계획 알고리즘

동적 계획 알고리즘

명지대학교 컴퓨터공학과

이 충기

지난 주 강의 내용

• 탐욕적인 접근 방법

• 거스름돈 구하기

• 최소비용 신장 트리 찾기

• 단일 출발점 최단경로 찾기

• 0-1 배낭 채우기

이번 주 강의 내용

• 동적 계획 알고리즘의 개념, 전략, 설계 과정

• 행렬 곱셈

• 모든 쌍 최단 경로 찾기

• 배낭 채우기

동적 계획 알고리즘

분할 정복과 동적 계획 비교

분할 정복과 동적 계획 비교(계속)

• 동적 계획 알고리즘은 먼저 최소 단위의 부분 문제 D, E, F, G의 해를 각각 구한다.

그 다음에

• D, E, F의 해를 이용하여 B의 해를 구한다.

• E, F, G의 해를 이용하여 C의 해를 구한다.

• B와 C의 해를 구하는데 E와 F의 해 모두를 이용한다.

• 분할 정복 알고리즘은 부분문제의 해를 중

복 사용하지 않는다.

분할 정복과 동적 계획 비교(계속)

• 동적 계획 알고리즘에는 부분문제들 사이 에 ______ 관계가 존재한다.

– 예를 들면, D, E, F의 해가 B를 해결하는데 사 용되는 의존적 관계가 있다.

• 이러한 관계는 문제 또는 입력에 따라 다

르고, 대부분의 경우 뚜렷이 보이지 않아

서 ‘함축적인 순서’ (implicit order)라고 한

다.

동적 계획 알고리즘 전략

• 문제를 더 작은 _________들로 분할한다.

• 작은 부분 문제들을 먼저 풀고 그 결과를 ____한다.

• 나중에 우리가 한 결과를 필요로 할 때마 다 그 결과를 다시 ____하는 대신에 _____

사용한다.

동적 계획 알고리즘 설계 과정

행렬 곱셈 적용 예

행렬 곱셈 적용 예 (계속)

행렬 곱셈 문제



예: 행렬 곱셈 문제

행렬 곱셈 (계속)

행렬 곱셈 문제

분할 정복 해법

동적 계획 알고리즘

예: 동적 계획 알고리즘 수행 과정

예: 동적 계획 알고리즘 수행 과정

모든 쌍 최단 경로 찾기

예: 한 도시에서 다른 도시로 가는 최단 경로를

찾아라

모든 쌍 최단 경로 찾기 문제

가중치를 포함한 방향 그래프가 주어지

면 각 정점에서 모든 다른 정점으로 가

는 가장 짧은 경로를 찾아라. 즉, 가중치

를 포함한 방향 그래프를 나타내는 행

렬 W 가 주어지면 행렬 D [1.. N , 1.. N ]을

구하라. D [i, j]는 정점 i에서 정점 j로 가

는 가장 짧은 경로의 비용이다.

모든 쌍 최단 경로 찾기

무작정 알고리즘(brute – force algorithm)

동적 계획 알고리즘 아이디어

동적 계획 알고리즘 아이디어

• 또 하나의 중요한 아이디어

• 부분문제 정의:

D

= 집합 {1, 2, ⋯, k}에 있는 정점만을 경유 가능

한 정점들로 고려하여, 정점 i로부터 정점 j

까지의 모든 경로 중에서 가장 짧은 경로의

거리

동적 계획 알고리즘 아이디어

• 여기서 주의할 것은 정점 1에서 정점 k까지의 모 든 정점들을 반드시 경유하는 경로를 의미하는 것 이 아니다.

• 심지어는 D

는 이 정점들을 하나도 경유하지 않 으면서 정점 i에서 정점 j에 도달하는 경로, 즉 연 결선 (i, j)가 최단 경로가 될 수도 있다.

• 여기서 k≠i, k≠j이고, k=0인 경우, 정점 0은 그래프

에 없으므로 어떤 정점도 경유하지 않는다는 것을

의미한다. 따라서D

은 입력으로 주어지는 연결선

(i, j)의 가중치이다.

• 나중에 우리가 한 결과를 필요로 할 때마 다 그 결과를 다시 하는 대신에 _