맹목적 탐색 vs 정보이용 탐색

인공지능 기초 · 인공지능의 이해 — 같은 길찾기 문제라도 맹목적 탐색(BFS, 목표까지 거리를 모르고 무작정 넓게 퍼짐)과 정보이용 탐색(목표까지의 거리를 추정하는 「휴리스틱」을 이용해 유망한 쪽부터 탐색)은 살펴보는 칸의 수가 크게 다르다.

1. 같은 미로, 두 방식으로 비교하기

맵을 클릭해 초록(시작)·분홍(도착)을 지정하고, 각 버튼을 눌러 두 탐색 방식이 얼마나 다른지 비교해 보세요.

맹목적 탐색 방문 수

–

정보이용 탐색 방문 수

–

절감된 칸 수

–

절감률

–

시작과 도착을 지정한 뒤 두 방식을 모두 실행해 비교해 보세요.

핵심 — 정보이용 탐색이 항상 더 정확한 것은 아니다. 대신 «어디부터 살펴봐야 유망한지»에 대한 힌트(휴리스틱)를 이용해서 탐색해야 할 상태 수를 크게 줄인다. 이번 시뮬레이션에서 그리디 탐색은 목표까지의 직선거리를 휴리스틱으로 사용한다.

한 줄 요약 — 맹목적 탐색은 «넓고 얕게», 정보이용 탐색은 «목표 방향으로 좁고 빠르게» 상태공간을 살펴본다.

관련: 탐색 문제 설계 체험 · A* 탐색 체험