개념
탐색은 가능한 많은 후보 중에서 목표에 도달하는 경로 또는 좋은 선택을 찾는 과정이다. 인공지능에서 가장 기본적인 문제 해결 전략 중 하나이다.
예시
- 체스나 바둑에서 다음 수 찾기
- 내비게이션에서 빠른 경로 찾기
- 로봇이 장애물을 피해 목적지로 이동하기
- 8-puzzle에서 목표 상태 만들기
- 최적의 화학 구조 후보 찾기
문제 표현
탐색 문제는 보통 상태 공간으로 표현한다. 시작 상태에서 연산자를 적용해 다음 상태로 이동하고, 문제 해결이 끝났다고 판단되는 목표 상태에 도달하는 경로를 찾는다. 탐색 알고리즘은 현재 상태가 목표 상태인지 반복해서 검사하며, 목표 상태를 발견하면 성공을 반환한다.
경로 의 총비용은 각 이동 비용의 합으로 나타낸다.
종류
탐색은 정보 사용 여부에 따라 맹목 탐색과 휴리스틱 탐색으로 나눌 수 있다. 상대가 있는 게임에서는 게임 탐색, 미니맥스 알고리즘, MCTS가 중요해진다.