쉽게쉽게 배우는배우는 알고리즘 알고리즘

(1)

http://academy.hanb.co.kr

12 12장 장. . 상태공간 상태공간 트리의 트리의 탐색 탐색

(2)

12 12장 장. . 상태공간 상태공간 트리의 트리의 탐색 탐색

인공지능은 미국인들 특유의 천진난만함의 표현이다.

-에드거 다익스트라

(3)

학습목표

• 상태공간 트리가 무엇인지 이해한다.

• 백트래킹 기법의 작동 원리를 이해한다.

• 한정분기의 작동 원리를 이해하고, 백트래킹 에 비해 장점이 무엇인지 이해하도록 한다.

• A* 알고리즘의 작동 원리를 이해하고, 어떤

문제들이 A* 알고리즘의 적용 대상인지 감지

하도록 한다.

(4)

State-Space Tree

• State-space tree (상태공간트리)

– 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리

• 이 장에서 배우는 세가지 상태공간 탐색 기법

– Backtracking

– Branch-and-bound – A^* algorithm

(5)

1

3

6

4 2

5

1

3

6

4 2

5

1

3

6

4 2

5

TSP 예제 해의 예 최적해

TSP의 예

(6)

0 10 10 30 25 10 0 14 21 10

10 18 0 7 9

8 11 7 0 3

14 10 10 3 0 1

2 3 4 5

1 2 3 4 5

1

3

4 2

5

10 10

25 14

10 10

11 21

30 8 3

3 9

10

7 7

14 18 10 10

TSP와 Adjacency Matrix의 예

(7)

1

1-2-3

1-2-3-4 1-2-3-5

1-2-4

48 44

1-2-5

1-3

1-2-5-4

40 1-2-5-3

45

1-2-5-3-4-1

1-2-3-4-5-1 1-2-3-5-4-1 1-2-5-4-3-1

1-5-4-2 1-5-4-3

63 63

1-5-4-2-3-1 1-5-4-3-2-1

1-4 1-5

1

2

10 11

3 6

4 5 40 41

12 22 32

1-2-4-5

54 1-2-4-3

61

1-2-4-3-5-1 1-2-4-5-3-1

7 8

1-2

9

1-5-4 39

… … …

…

사전적 탐색의 State-Space Tree

(8)

Backtracking

• DFS 또는 그와 유사한 스타일의 탐색을 총칭한다

• Go as deeply as possible, backtrack if impossible

– 가능한 지점까지 탐색하다가 막히면 되돌아간다

• 예

– Maze, 8-Queens problem, Map coloring, …

(9)

S

T 2

3 1

4

5

6 S

1 2 3

4 5 6 T

7

8 9 7 8 9

maze

S

T

그래프로 모델링한 미로

Branching tree

Maze

(10)

maze(v) {

visited[v] ← YES;

if

(v = T) then {print “성공!”; exit( );}

for each x ^∈

L(v) ▷ L(v) : 정점 v의 인접 정점 집합

if

(visited[x] = NO) then { prev[x] ← v;

maze(x);

} }

(11)

Coloring Problem

• Graph에서

– 인접한 vertex는 같은 색을 칠할 수 없다

– k 개의 색상을 사용해서 전체 graph를 칠할 수

있는가?

(12)

1

3 6

4 2

5

1

3

6 2 4

5

(a) 지도 (b) 구역간의 인접관계

(c) 연결관계를 정점과 간선으로 나타낸 것 (d) (c)와 동일한 그래프

Coloring Problem의 예: Map Coloring

(13)

kColoring(i , c)

▷ i: 정점, c: color

▷ 질문: 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색 c로 칠하려면 k 개의 색으로 충분한가?

{

if

(valid(i, c)) then { color[i] ← c;

if

(i = n) then {return TRUE;}

else

{

result ← FALSE;

d ← 1;

▷ d: color

while

(result = FALSE

and d ≤ k) {

result ← kColoring(i+1, d); ▷ i+1: 다음 정점

d++;

} }

return

result;

} else {return FALSE;}

}

(14)

valid(i, c)

▷ i: 정점, c: color

▷ 질문: 정점 i-1까지는 제대로 칠이 된 상태에서 정점 i를 색 c로 칠하려면 이들과 색이 겹치지 않는가?

{

for j ← 1 to i-1 {

▷ 정점 i와 j 사이에 간선이 있고, 두 정점이 같은 색이면 안된다

if

((i, j) ∈ E and color[j] = c) then return FALSE; }

return

TRUE; }

(15)

1, 1

3, 1 3, 2

2, 1

1

5 2, 2

3

4

4, 1 4, 2

7 6

5, 1

6, 1 6, 2

9

6, 3

10 11

8 2

State-Space Tree

1

3

6 2 4

5

(16)

Branch-and-Bound

• 분기

^branch

와 한정

bound

의 결합

– 분기를 한정시켜 쓸데없는 시간 낭비를 줄이는 방법

• Backtracking과 공통점, 차이점

– 공통점

• 경우들을 차례로 나열하는 방법 필요

– 차이점

• Backtracking – 가보고 더 이상 진행이 되지 않으면 돌아온다

• Branch-&-Bound – 최적해를 찾을 가능성이 없으면 분기는 하지 않는다

(17)

P₁

P₂

P₃ P₄

P₅

P₆ P₁

P₂

P₃ P₄

P₅

P₆

어느 시점에 가능한 선택들 최적해를 포함하지 않아 제외하는 선택들

(18)

1

1-2

1-2-3

1-2-3-4 1-2-3-5

(33) 0+33

(33) 10+23

(37) 24+13

1-2-4 (44) 31+13

1-2-5 (33)

20+13

1-3 (33) 10+23

1-3-2 (44)

28+16

1-3-4 (33)

17+16

1-3-5 (35)

19+16

1-2-5-4

1-2-5-3 1-3-4-2 1-3-4-5 1-3-5-2 1-3-5-4

1-4 (53)

30+23

1-5 (48)

25+23 1

2

4 5

6 9

7 8

11

12 13 15 16

10 19 18

3 17 14

40 45

1-2-5-3-4-1

1-2-3-4-5-1 1-2-3-5-4-1 1-2-5-4-3-1

40 58 43

1-3-5-2-4-1

1-3-4-2-5-1 1-3-4-5-2-1 1-3-5-4-2-1

48 44 52

(19)

A ^* Algorithm

• Best-First-Search

– 각 정점이 매력함수값 g(x)를 갖고 있다

– 방문하지 않은 정점들 중 g(x) 값이 가장 매력적인 것부터 방문한다

• A ^* algorithm은 best-first search에 목적점에 이르는 잔여추정거리를 고려하는 알고리즘이다

– Vertex x로부터 목적점에 이르는 잔여거리의 추정치 h(x)는 실제치보다 크면 안된다

(20)

Shortest Path 문제

• Remind: Dijkstra algorithm

– 시작점은 하나

– 시작점으로부터 다른 모든 vertex에 이르는 최단경로를 구한다 (목적점이 하나가 아니다)

• A ^* algorithm에서는 목적점이 하나다

(21)

30 23

25

24

18

28 20

29 25

39

20

40 28 16

10

19

17 20

17

0 30 23

25

24

18

28 20

29 25

39

∞

20

40 28 16

10

19

17 20

17

10 30

17 23

∞

25

0 30 23

25

24

18

28 20

29 25

39

∞

20

40 28 16

10

19

17 20

17

10 30

17 23

∞

25

0 30 23

25

24

18

28 20

29 25

39

20

40 28 16

10

19

17 20

17

∞ ∞

∞

s

t

Dijkstra Algorithm의 작동 예

(22)

0 30 23

25

24

18

28 20

29 25

39

∞

20

40 28 16

10

19

17 20

17

10 30

17 23

∞

25

0 30 23

25

24

18

28 20

29 25

39

∞

20

40 28 16

10

19

17 20

17

10 30

17 23

41

∞

25

0 30 23

25

24

18

28 20

29 25

39

∞

20

40 28 16

10

19

17 20

17

10 30

17 23

41

∞

50

25 0 30

23

25

24

18

28 20

29 25

39

61 20

40 28 16

10

19

17 20

17

10 30

17 23

41

64

50

25

(23)

0 30 23

25

24

18

28 20

29 25

39

61 20

40 28 16

10

19

17 20

17

10 30

17 23

41

64 50

25

0 30 23

25

24

18

28 20

29 25

39

61 20

40 28 16

10

19

17 20

17

10 30

17 23

41

64 50

25

(24)

16 25

52

40

39 34

19 19

52 68

61

30 23

25

24

18

28 20

29 25

39

20

40 28 16

10

19

17 20

17

(77)

(57) (71)

(85)

(70)

0 30 23

25

24

18

28 20

29 39

∞

20

40 28 10

19

17 20

17

10 30

17 23

∞

25

∞

추정 잔여거리

0 30 23

25

24

18

28 20

29 25

39

20

40 28 16

10

19

17 20

17

∞ ∞

∞

(25)

0 30 23

25

24

18

28 20

29 25

39

61 20

40 28 16

10

19

17 20

17

10 30

17 23

41

∞

50

25

(60)

(89)

0 30 23

25

24

18

28 20

29 25

39

61 20

40 28 16

10

19

17 20

17

10 30

17 23

41

∞

50

25

(77)

(57) (71)

(85)

(70)

(60)

(89) (77)

(57) (71)

(85)

(70)

ü

추정잔여거리를 사용함으로써 탐색의 단계가 현저히 줄었다

(26)

1

1-2

1-2-3

1-2-3-4 1-2-3-5

(33) 0+33

(33) 10+23

(37) 24+13

1-2-4 (44) 31+13

1-2-5 (33)

20+13

1-3 (33) 10+23

1-3-2 (44)

28+16

1-3-4 (33)

17+16

1-3-5 (35)

19+16

1-2-5-4

40 1-2-5-3

45 1-2-5-3-4-1

1-2-3-4-5-1 1-2-3-5-4-1 1-2-5-4-3-1

1-3-4-2 1-3-4-5

40

1-3-5-4

43 1-3-5-2

58 1-3-5-2-4-1

1-3-4-2-5-1 1-3-4-5-2-1 1-3-5-4-2-1 1-4

(53) 30+23

1-5 (48)

25+23 1

2

8

7 5

3

4 6

48 44 52

(27)

153241 153421 1-5

154231

152351 152431 154321

(48) 25+23

1-2-5 (33)

20+13

1-2-5-4

40

1-2-5-3

45

125341 125431

1-3-5 (35)

19+16

1-3-5-4

41

1-3-5-2

58

125341 125431

… … …

계산된 leaf node들 계산되지 않은 leaf node들 방문된 leaf node

A Algorithm이 첫 Leaf Node를 방문하는 순간 종료되는 이유

영역과 영역의 leaf node들이 모두

40 보다 커질 수 없는 이유를 이해할 것

(28)

쉽게쉽게 배우는배우는 알고리즘 알고리즘

12

12장 장. . 상태공간 상태공간 트리의 트리의 탐색 탐색

12

12장 장. . 상태공간 상태공간 트리의 트리의 탐색 탐색

인공지능은 미국인들 특유의 천진난만함의 표현이다.

-에드거 다익스트라

학습목표

• 상태공간 트리가 무엇인지 이해한다.

• 백트래킹 기법의 작동 원리를 이해한다.

• 한정분기의 작동 원리를 이해하고, 백트래킹 에 비해 장점이 무엇인지 이해하도록 한다.

• A* 알고리즘의 작동 원리를 이해하고, 어떤

문제들이 A* 알고리즘의 적용 대상인지 감지

하도록 한다.

State-Space Tree

• State-space tree (상태공간트리)

• 이 장에서 배우는 세가지 상태공간 탐색 기법

TSP의 예

TSP와 Adjacency Matrix의 예

사전적 탐색의 State-Space Tree

Backtracking

• DFS 또는 그와 유사한 스타일의 탐색을 총칭한다

• Go as deeply as possible, backtrack if impossible

– 가능한 지점까지 탐색하다가 막히면 되돌아간다

• 예

– Maze, 8-Queens problem, Map coloring, …

S

T 2

3 1

4

5

6

S

1

2 3

4

5 6 T

7

8

9 7 8 9

S

T

Maze

if

for each x ∈

if

Coloring Problem

• Graph에서

– 인접한 vertex는 같은 색을 칠할 수 없다

– k 개의 색상을 사용해서 전체 graph를 칠할 수

있는가?

Coloring Problem의 예: Map Coloring

if

if

else

d ← 1;

while

and d ≤ k) {

d++;

return

for j ← 1 to i-1 {

if

return

State-Space Tree

Branch-and-Bound

• 분기

와 한정

의 결합

• Backtracking과 공통점, 차이점

A * Algorithm

• Best-First-Search

• A * algorithm은 best-first search에 목적점에 이르는 잔여추정거리를 고려하는 알고리즘이다

Shortest Path 문제

• Remind: Dijkstra algorithm

• A * algorithm에서는 목적점이 하나다

∞

∞

∞

∞

∞

for each x ^∈

A ^* Algorithm

• A ^* algorithm은 best-first search에 목적점에 이르는 잔여추정거리를 고려하는 알고리즘이다

• A ^* algorithm에서는 목적점이 하나다