문제풀이방식-맹목적 탐색 Ai4.

Presentation on theme: "문제풀이방식-맹목적 탐색 Ai4."— Presentation transcript:

1 문제풀이방식-맹목적 탐색 Ai4

2 지난 주 상태묘사 : 연산자의 정의 방법 : 그래프를 이용한 상태 공간의 표현
문제의 상태를 컴퓨터 내에서 다룰 수 있는 적절한 자료구조로 표현한 것 연산자의 정의 방법 : 가능한 한 일반화된 변환 규칙을 정의 하는 것이 바람직 그래프를 이용한 상태 공간의 표현 Ai4

3 이번 주의 학습 내용 그래프 탐색의 개요 탐색 방법의 종류 맹목적 탐색 깊이 우선 탐색 넓이 우선 탐색 균일 비용 탐색 Ai4

4 상태공간의 그래프 표현 방향성 그래프(directed graph)가 많이 사용 그래프 :
노드의 집합과 노드를 연결하는 아크의 집합으로 구성 Ai4

5 방향성 그래프 상태 : 노드(node) 연산자 : 아크(arc) 방향성 아크 비용이 결부될 수 있다.
아크는 어느 한 노드로 부터 다른 노드로 방향이 주어져 있다. 비용이 결부될 수 있다. Ai4

6 방향성 그래프 Ni  Nj Length Cost 노드 Nj는 노드 Ni의 후계(successor)
노드 Ni는 노드 Nj의 부모(parent) Length ex) 길이가 k인 경로 : Ni0, Ni1, …, Nik Cost C(Ni, Nj) : 노드 Ni로부터 Nj를 향하는 아크 비용 두 노드 사이의 경로에 드는 비용 : 아크 비용 합 Ai4

7 목적 어떤 노드 S로부터 목표상태를 나타내는 노드들의 집합 {Ti}의 한 노드까지의 경로를 찾는 것
노드의 집합 {Si}의 한 노드로부터 노드의 집합 {Ti}의 한 노드까지의 경로를 찾는 것 Ai4

8 2 1 8 7 6 3 4 5 2 1 8 7 6 3 4 5 2 1 8 7 6 3 4 5 2 3 1 8 7 6 4 5 1 2 8 7 6 3 4 5 2 8 1 4 7 6 3 5 2 3 1 7 6 4 8 5 1 2 8 7 6 3 4 5 Ai4

9 탐색을 이용한 문제 풀이 방법 탐색 알고리즘에 대한 고찰
그래프 탐색 탐색을 이용한 문제 풀이 방법 탐색 알고리즘에 대한 고찰 Ai4

10 그래프 탐색 상태공간에서 목표상태의 탐색: 상태들 간의 의존 관계가 형성 그래프로 표현
초기상태로부터 시작하여 연산자를 이용하여 새로운 차기 상태들을 생성하고, 그 중 적절한 대상을 선택하여 다시 차기상태를 생성시키는 과정을 반복 상태들 간의 의존 관계가 형성 그래프로 표현 Ai4

11 탐색 과정 주어진 상태에 적용할 수 있는 모든 연사자를 가하여 모든 차기 상태들을 생성 - 후계노드의 집합 생성
후계 노드에는 부모 노드를 가리키는 포인터를 첨부 - 탐색 경로를 알 수 있도록 함 정해진 기준에 따라 다음 노드를 선택 Ai4

12 Ai4

13 용어 및 자료 구조 확장 : 어떠한 상태의 모든 후계 상태를 생성하는 것 OPEN : 확장할 노드들를 저장하는 리스트
CLOSED : 이미 확장된 노드들을 저장하는 리스트 Ai4

14 탐색에 사용되는 정보에 따른 분류 맹목적 탐색 : 경험적 탐색 :
목표 노드의 위치에 관계없이 단순히 미리 정해진 순서에 따라 탐색을 하는 방법 경험적 탐색 : 목표 노드의 위치에 대한 경험적 정보를 사용하여 확장할 노드 선택 경험적 지식 : 시행착오에 따른 경험적 지식으로, 완벽한 것은 아니지만, 많은 경우 유용하게 사용할 수 있는 지식 Ai4

15 탐색의 목표에 따른 분류 임의 경로 탐색 : 최적 경로 탐색 :
어떤 경로를 거치든 목표 상태에 도달하는 경로를 찾기만 하면 되는 문제 최적 경로 탐색 : 목표상태에 도달하는 최적의 경로를 탐색하는 문제 Ai4

16 깊이 우선 균일비용 넓이 우선 언덕 오르기 A*알고리즘 최적 우선 목적 정보사용 임의 경로 탐색 최적 경로 탐색 맹목적 탐 색
탐 색 깊이 우선 넓이 우선 균일비용 경험적 탐 색 언덕 오르기 최적 우선 A*알고리즘 Ai4

17 깊이 우선 방법 Depth-first search OPEN은 스택 구조(LIFO) 백트래킹(backtracking)
최근의 탐색하지 않은 후계노드로 복귀 다른 방향으로의 탐색이 가능한 최근의 상태로 복귀하는 것 Ai4

18 깊이 우선 탐색 알고리즘 1. 출발 노드를 OPEN에 삽입 2. OPEN에 남은 노드가 있으면 다음 반복
(1) Open의 제일 앞 노드를 꺼내어 Closed에 넣는다. (노드n) (2) n이 깊이 제한에 도달하지 않았다면 a. 노드 n을 확장 b. 생성된 후계 노드들에 노드n을 가리키는 포인터 첨부 c. 후계노드 중 목표노드가 존재하면 포인터를 역추적하여 탐색 경로를 구성(탐색 성공) d. 후계 노드들을 Open의 앞에 넣는다 Ai4

19 A OPEN A CLOSED Ai4

20 A B C D OPEN D C B CLOSED A Ai4

21 A B C D E F OPEN D C E F CLOSED A B Ai4

22 A B C D E F G H OPEN D C F G H CLOSED A B E Ai4

23 A B C D E F G H OPEN D C F H CLOSED A B E G Ai4

24 A B C D E F G H OPEN D C F CLOSED A B E G H Ai4

25 A B C D E F I J G H OPEN D C J I CLOSED A B E G H F Ai4

26 8-퍼즐 문제 2 3 1 5 3 8 2 4 7 6 1 8 4 7 6 5 초기상태 목표상태 Ai4

27 연습 문제 Ai4

28 2 1 8 7 6 3 4 5 2 1 8 7 6 3 4 5 2 1 8 7 6 3 4 5 ① 2 3 1 8 7 6 4 5 ② 1 2 8 7 6 3 4 5 ④ 2 3 1 7 6 4 8 5 ③ 1 2 8 7 6 3 4 5 ⑤ Ai4

29 넓이 우선 방법 Breadth-first search 탐색 트리의 한 레벨씩 단계적으로 탐색 최단 길이 경로 탐색
OPEN은 큐 구조(FIFO) Ai4

30 넓이 우선 탐색 알고리즘 1. 출발 노드를 OPEN에 삽입 2. OPEN에 남은 노드가 있으면 다음 반복
(1) Open의 제일 앞 노드를 꺼내어 Closed에 넣는다. (노드n) (2) 노드 n을 확장 (2) 후계 노드가 생성되었다면 다음을 수행 a. 생성된 후계 노드들에 노드n을 가리키는 포인터 첨부 b. 후계노드 중 목표노드가 존재하면 포인터를 역 추적 하여 탐색 경로를 구성(탐색 성공) d. 후계 노드들을 Open의 뒤에 넣는다 Ai4

31 A CLOSED OPEN A Ai4

32 A B C D OPEN B C D CLOSED A Ai4

33 A B C D E F OPEN C D F E CLOSED A B Ai4

34 A B C D G E F OPEN D E F G CLOSED A B C Ai4

35 A B C D H I J E F G OPEN E F G I J H CLOSED A B C D Ai4

36 A B C D E F G H I J K L OPEN F G H I J L K CLOSED A B C D E Ai4

37 연습 문제 Ai4

38 2 1 8 7 6 3 4 5 2 1 8 7 6 3 4 5 2 1 8 7 6 3 4 5 2 3 1 8 7 6 4 5 1 2 8 7 6 3 4 5 2 8 1 4 7 6 3 5 2 3 1 7 6 4 8 5 1 2 8 7 6 3 4 5 Ai4

39 Review 깊이 우선 탐색 넓이 우선 탐색 넓이 우선 탐색에 비해 적은 메모리 공간을 소비.
우연히 아주 빠르게 풀이 경로를 찾을 수 있다. 넓이 우선 탐색 해가 없는 경로를 불필요하게 깊이 탐색할 필요가 없다. 해가 존재하면 반드시 찾을 수 있고, 그 풀이 경로는 최단 경로이다. Ai4

40 균일 비용 탐색 Uniform-cost search
출발 노드로부터의 경로비용이 최소인 노드를 선택하여 확장시키는 방법을 사용. Ai4

41 경로비용의 계산 S N N1 N2 Nm ... g(Ni) = g(N) +C(N,Ni), i=1,2,...,m g(N)
C(N,Nm) N1 N2 Nm ... Ai4

42 경로비용의 계산 최소 비용 경로의 탐색 : g(N)이 최소인 노드N을 우선 선택
g(N) : 출발노드(S)로부터 노드N까지의 최소 경로 비용 C(N,Ni) : 노드N과 후계 노드 Ni 사이의 경로 비용 후계 노드 Ni의 비용은 노드N의 최소 경로 비용에 노드N과 후계 노드 Ni 사이의 경로 비용을 합한 것 g(Ni) = g(N) + C(N, Ni) 최소 비용 경로의 탐색 : g(N)이 최소인 노드N을 우선 선택 Ai4

43 균일비용 탐색 알고리즘1/2 1. 출발 노드를 OPEN에 삽입(출발 노드의 비용은 0)
1) OPEN의 제일 앞 노드를 꺼내어 CLOSED에 넣는다. (노드n) 2) 노드n이 목표 노드라면 탐색 성공 - 포인터를 역추적하여 탐색 경로를 구성 3) 노드n을 확장하여 후계노드 n1, n2, ..., ni를 생성하고, 부모노드n을 가리키는 포인터 첨부 4) 후계노드 n1, n2, ..., ni의 경로 비용 계산 Ai4

44 균일비용 탐색 알고리즘2/2 3. 탐색 실패 5) 각각의 후계노드 nj, j=1,...,i에 대하여
1. nj 와 동일한 노드가 OPEN에 존재하면 새로 생성된 노드의 경로 비용이 적을 경우 OPEN의 노드를 대체하고, 그렇지 않으면 무시 2. nj 와 동일한 노드가 CLOSED에 존재하면 새로 생성된 노드 무시 3. nj 와 동일한 노드가 OPEN이나 CLOSED에 존재하지 않으면 OPEN에 첨가 6) OPEN에 저장된 노드들을 경로 비용의 오름차순으로 정렬 3. 탐색 실패 Ai4

45 문제 풀이 과정의 예 최단 경로 탐색 문제 문제: a~g의 7개의 도시가 있다. 도시 사이에는 도로가 건설되어 있고, 각 도로의 거리는 그림과 같다. 도시a에서 g까지 가는 최단 경로를 찾아라. 상태 : 현재 위치한 도시 연산자 : 각 도시로 이동하라는 지시 Ai4

46 최단 경로 탐색 문제 6 b e 3 5 8 7 5 g a 2 f 4 c d 3 3 Ai4

47 a a c d f g b c 5 4 10 12 11 d c e d b e 9 12 7 c g b f 10 14 19 14 g 12 Ai4

48 Review 경로 비용이 최소인 노드를 선택하여 확장하므로 선택된 노드가 목표 노드이면 그 경로는 최소 비용 경로.
8-퍼즐 문제에서는 조각의 이동 횟수가 비용이며, 따라서 모든 연산자의 적용 비용이 동일하므로 균일 비용 탐색은 넓이 우선 탐색과 동일한 탐색을 하게 된다. Ai4