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

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

언덕등반기법 (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

언덕등반기법 (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

언덕등반기법 (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

언덕등반기법 (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

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

최고우선탐색 (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

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

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

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

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

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

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