[인공지능] Uninformed Search - UCS List로 분석

반갑습니다. :)

 

 

 

 

 

 

저번 글에서는

 

Uninformed Search의 UCS기법을 알아보면서

 

가장 기본적인

 

Tree형태를 살펴보았습니다.

 

 

https://setori-dev.tistory.com/48

[인공지능] Uninformed Search - UCS(균일비용탐색)

 

 

 

 

이번에는

 

BFS, DFS와 동일하게

 

List형태로 표현해보도록 하겠습니다.

 

 

https://setori-dev.tistory.com/46

[인공지능] Uninformed Search - BFS와 DFS 비교

 

 

 

 

---

 

List형태

 

 

 

다음을 UCS기법으로 탐색하는 과정을 List로 표현하시오.

Goal을 모른다고 가정할 때 a~g까지 탐색하는 과정입니다.

 

 

Tree로 표현된 것을 List로 표현해보도록 하겠습니다.

 

 

 

맨 처음 a가 Open List에 들어오고

 

그 때의 비용은 0입니다.

Open	a
비용	0
Close

 

 

 

Open List에 들어온

 

a를 탐색하고, 확장하고자 할 때

 

a가 Close List로 들어옵니다.

Open	a
비용	0
Close	a 확장

 

 

 

즉,

 

a가 Close List에 들어오면

 

a의 fringe를 확장할 수 있습니다.

 

 

확장한 a의 fringe은 b와 c로

 

Open List로 들어옵니다.

 

이때의 비용을 List에 적습니다.

Open	a	b	c
비용	0	5	4
Close	a 확장

 

 

 

UCS는 적은 비용을 선택해

 

확장하기 때문에

 

적은 비용인 c를 확장합니다.

Open	a	b	c
비용	0	5	4
Close	a 확장	c 확장

 

 

 

비용 4인 c 확장

 

각 비용을 List에 적습니다.

Open	a	b	c	b	d	e
비용	0	5	4	9 (0+4+5)	7 (0+4+3)	12 (0+4+8)
Close	a 확장	c 확장

 

 

 

여기서

 

동일한 fringe는 적은 비용을 선택하고,

 

큰 비용은 삭제하며

 

 

삭제 후에는

 

가장 적은 비용의 fringe를 선택하여 확장합니다.

 

 

b의 비용: 5

d의 비용: 7

e의 비용: 12

 

 

b 확장

Open	a	b	c	b	d	e	c	d	e
비용	0	5	4	9	7 (0+4+3)	12 (0+4+8)	10 (0+5+5)	12 (0+5+7)	11 (0+5+6)
Close	a 확장	c 확장	b 확장

 

.

.

.

 

 

똑같이

 

동일한 fringe는 적은 비용을 선택하고,

 

큰 비용은 삭제하며

Open	a	b	c	b	d	e	c	d	e
비용	0	5	4	9	7 (0+4+3)	12	10	12	11 (0+5+6)
Close	a 확장	c 확장	b 확장		d 확장

 

 

 

삭제 후에는

 

가장 적은 비용의 fringe를 선택하여 확장합니다.

 

 

d의 비용: 7

e의 비용: 11

 

 

 

d 확장

Open	a	b	c	b	d	e	c	d	e	b	f
비용	0	5	4	9	7 (0+4+3)	12	10	12	11 (0+5+6)	14 (0+4+3+7)	10 (0+4+3+3)
Close	a 확장	c 확장	b 확장		d 확장

(d 확장 부분은 표 크기 때문에 한 칸 띄었습니다. List에는 영향 없습니다.)

 

 

 

.

.

.

 

 

 

 

한 번 더 똑같이

 

동일한 fringe는 적은 비용을 선택하고,

 

큰 비용은 삭제하며

Open	a	b	c	b	d	e	c	d	e	b	f
비용	0	5	4	9	7 (0+4+3)	12	10	12	11 (0+5+6)	14	10 (0+4+3+3)
Close	a 확장	c 확장	b 확장		d 확장

 

 

 

삭제 후에는

 

가장 적은 비용의 fringe를 선택하여 확장합니다.

 

 

 

e의 비용: 11

f의 비용: 10

 

 

 

f 확장

Open

a

b

c

b

d

e

c

d

e

b

f

g

비용

0

5

4

9

7 (0+4+3)

12

10

12

11 (0+5+6)

14

10 (0+4+3+3)

12 (0+4+3+3+2)

Close

a 확장

c 확장

b 확장

d 확장

f 확장

(f 확장 부분은 표 크기 때문에 한 칸 띄었습니다. List에는 영향 없습니다.)

 

 

 

.

.

.

 

 

또

 

동일한 fringe는 적은 비용을 선택하고,

 

큰 비용은 삭제하며

Open

a

b

c

b

d

e

c

d

e

b

f

g

비용

0

5

4

9

7 (0+4+3)

12

10

12

11 (0+5+6)

14

10 (0+4+3+3)

12 (0+4+3+3+2)

Close

a 확장

c 확장

b 확장

d 확장

f 확장

(마지막인 g가 확장이 되었지만, 정답인지 아직은 모릅니다. 그렇기 때문에 가장 적은 비용을 확장합니다)

 

 

 

 

삭제 후에는

 

가장 적은 비용의 fringe를 선택하여 확장합니다.

 

 

 

e의 비용: 11

g의 비용: 12

 

 

 

e 확장

Open

a

b

c

b

d

e

c

d

e

b

f

g

c

g

비용

0

5

4

9

7 (0+4+3)

12

10

12

11 (0+5+6)

14

10 (0+4+3+3)

12 (0+4+3+3+2)

19 (0+5+6+8)

14 (0+5+6+3)

Close

a 확장

c 확장

b 확장

d 확장

f 확장

e 확장

(e 확장 부분은 표 크기 때문에 한 칸 띄었습니다. List에는 영향 없습니다.)

 

 

.

.

.

 

 

마지막으로

 

동일한 fringe는 적은 비용을 선택하고,

 

큰 비용은 삭제하면

Open

a

b

c

b

d

e

c

d

e

b

f

g

c

g

비용

0

5

4

9

7 (0+4+3)

12

10

12

11 (0+5+6)

14

10 (0+4+3+3)

12 (0+4+3+3+2)

19 (0+5+6+8)

14 (0+5+6+3)

Close

a 확장

c 확장

b 확장

d 확장

f 확장

e 확장

 

 

삭제 후에는

 

남은 fringe은 g로

 

가장 적은 비용인 12가 남게 됩니다.

 

 

g의 비용: 12

 

 

 

그럼 마지막으로

 

g 확장

Open

a

b

c

b

d

e

c

d

e

b

f

g

c

g

비용

0

5

4

9

7 (0+4+3)

12

10

12

11 (0+5+6)

14

10 (0+4+3+3)

12 (0+4+3+3+2)

19

14

Close

a 확장

c 확장

b 확장

d 확장

f 확장

e 확장

g 확장

 

 

 

 

 

 

 

 

이렇게 탐색의 순서는 Close List에 들어온 순서대로 진행됩니다.

 

 

따라서, 탐색 순서는 다음과 같습니다.

 

a , c , b , d , f , e , g

 

 

 

 

List로 보면 다음과 같습니다.

Open	a	b	c	d	e	f	g
Close	a 확장	c 확장	b 확장	d 확장	f 확장	e 확장	g 확장

 

 

 

UCS는 Tree형태로 보는 것보다는

 

List형태로 계산하는 것이

 

비용을 비교하고

 

fringe를 비교하는 측면에서

 

편리한것을 볼 수 있습니다!

 

 

 

 

 

많은 도움 되셨다면❤와 구독 부탁드릴게요!

 

:)