탐색 (Lecture Note #3) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides

Presentation on theme: "탐색 (Lecture Note #3) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides"— Presentation transcript:

1 탐색 (Lecture Note #3) 인공지능 이복주 단국대학교 컴퓨터공학과 Modified from the slides
by SciTech Media 탐색 (Lecture Note #3) 인공지능 이복주 단국대학교 컴퓨터공학과

2 Outline 탐색 문제 해결 상태 공간 탐색 기법 휴리스틱 기법 게임 트리 기법 알파베타 탐색 문제 제약 조건 만족 문제
Slide made by Bogju Lee

3 언덕등반기법 (hill-climbing)
평가함수 (evaluation function or objective function) 사용 한 경로가 목표에 이르는데 얼마나 지름길일 것인지 판단하는 함수 평가함수 값을 증가(감소)시키는 방향으로 나가는 탐색전략 계곡 하강법 (valley declining) 깊이우선 탐색기법에 평가함수를 활용한 형태 최단의 경로에 대한 보장이 없다 국부최대가 존재할 수 있다 (plateau) 과정 회복 불가능 (irrevocable) 예) 8-퍼즐 문제 (그림 2.9) Plateau: 고원 2 3 1 2 3 1 8 4 8 4 7 6 5 7 6 5 초기상태 목표상태 Slide made by Bogju Lee

4 언덕등반기법 (hill-climbing)
8-퍼즐 문제 평가함수 = 목표상태와 같은 위치에 있는 타일 수 초기상태 = 5 (3, 4, 5, 6, 7 이 같은 위치) 목표상태 = 8 연산자 = blank cell을 전후좌우로 이동시키는 것 2 3 1 2 3 1 8 4 8 4 7 6 5 7 6 5 초기상태 목표상태 Slide made by Bogju Lee

5 언덕등반기법 (hill-climbing)
8-퍼즐문제의 탐색 (그림 2.10) 1 2 3 1 8 4 5 7 6 5 2 2 3 2 8 3 2 3 1 8 4 1 4 1 8 4 6 5 4 7 6 5 7 6 5 7 6 5 3 1 2 3 2 3 8 4 1 8 4 7 5 7 6 5 7 6 5 4 1 2 3 2 3 1 2 3 7 8 4 1 8 4 8 4 6 6 8 6 5 7 6 5 7 6 5 Slide made by Bogju Lee

6 언덕등반기법 (hill-climbing)
언덕등반기법의 실패 (그림 2.11) 평가함수의 값을 높이는 방향으로 탐색할 수 없음 국부 최대 (local maximum)에 빠짐 많은 실제적 문제에서 국부 최대 문제 발생 2 8 3 1 4 5 7 6 5 2 8 3 2 3 2 8 3 2 8 3 1 4 1 8 4 1 4 1 6 4 5 5 4 4 7 6 5 7 6 5 7 6 5 7 5 Slide made by Bogju Lee

7 최고우선탐색 (best-first) 최고우선탐색 (best-first)
모든 말단 노드(열린 노드)를 대상으로 평가함수 값을 비교하는 방법 선택 안 된 노드도 추후 선택 가능 Vs. 언덕등반기법: 하나의 노드가 선택되면 같은 레벨의 다른 노드들 다시 고려되지 않음 Slide made by Bogju Lee

8 최고우선탐색 (best-first) 최고우선 탐색법 예 (그림 2.12) s s a b c a b c d e s s a b c
4 1 5 4 1 5 d e 2 3 s s 2 2 a b c a b c 4 1 5 4 1 5 f g d e f g d e 5 6 2 3 5 6 2 3 h i j 5 3 8 Slide made by Bogju Lee

9 최고우선탐색 (best-first) 최고우선탐색 (best-first) 국부최대를 만나도 탐색이 계속된다
Vs. 언덕등반기법: 자녀노드에 더 좋은 함수 값이 없으면 탐색 진행 안됨 너비우선 방식에 비해 탐색비용이 절감된다 열린노드를 대상으로 가장 좋은 것 선택 그러나 역시 최적의 경로를 보장할 수 없다 아직 선택 안 된 노드를 또 확장해 보면 더 나은 해를 발견 가능 예: 앞의 예에서 b의 자녀 중에 최적의 해가 있을 수도 해결책: 해를 찾은 후라도 아직 open 안된 노드 open 하여 확인한다 Slide made by Bogju Lee

10 최고우선탐색 (best-first) 빔 탐색 (beam search)
최고우선기법에서 기억노드(열린 노드)의 수를 제한하는 방법 기억공간이 축소되지만 너무 빠른 가지치기(pruning)를 초래 Slide made by Bogju Lee

11 A-알고리즘 A-알고리즘 지금까지의 평가함수: 노드의 목표노드와의 근접도
실제 최적의 경로: 초기노드에서 목표노드까지의 최단 경로 임의의 노드 N의 평가함수를 정의 f(N) = g(N) + h(N) g(N): 초기노드에서 N노드 까지의 최단거리 h(N): N노드에서 목표노드까지 최단 거리 h(N)은 해가 주어지지 않으면 알 수 없으므로, h(N)대신에 추정치 h*(N)을 사용 f(N) = g(N) + h*(N): 평가함수 Slide made by Bogju Lee

12 A* 알고리즘 A* 알고리즘 A 알고리즘에서 모든 N에 대해 h*(N)  h(N)가 성립되도록 하면 허용성을 가짐  A* 알고리즘 허용성 (admissibility): 최적의 경로를 보장하는 조건 Admissible: h* never overestimates h (i.e., underestimate or equal) 예: straight line, # tiles out of place h 2 3 1 2 3 1 8 4 8 4 7 6 5 7 6 5 h* # tiles out of place h* = 4 h >= 4 # tiles out of place = 0 Slide made by Bogju Lee

13 A* 알고리즘 A* 알고리즘 f(N) = g(N)로 두면(h*(N)=0), 허용성 조건을 만족
평가함수로 초기노드와의 거리만을 고려  낮은 깊이 노드를 우선 탐색  BFS BFS가 최단 경로를 발견한다는 것을 다시 입증 BFS를 해나가는 데 있어 각 노드에서 목표에 이르는 경로가 얼마나 짧은 것인가의 추정치를 이용하는 방법 cf. 8-puzzle에서 상태 N에서의 평가 함수 f(N) = g(N) + W(N) 여기서 W(N)은 목표상태와 틀린 위치의 타일의 갯수 Slide made by Bogju Lee

14 Summary 언덕 등반 기법 최고 우선 탐색 언덕 등반 기법과 최고 우선 탐색의 차이점 A* 알고리즘
Admissibility 모두 heuristic 기법의 일종 Slide made by Bogju Lee