탐색
드러내지 않은 사물이나 현상 따위를 찾아내거나 밝히기 위하여 살피어 찾음.
트리가 있다.
루트 노드를 중심으로 두 개의 하위 노드가 있고 하위 노드들은 왼쪽에서부터 각각 5개, 3개의 하위 노드를 가진다.
방법이 다양할수록 노드는 잔가지를 뻗치며 하위로 확장하게 되는데,
개발에서 탐색은 확장된 노드들에서 Goal, 대상을 찾기 위해서 탐험을 하는 과정이다.
개발에서의 탐색은 두 가지가 있다.
- 맹목적 탐색 (Blind Search, Uninformed Search)
- 경험적 탐색 (Heuristic Search, Informed Search)
맹목적 탐색
Uninformed Search, 즉 정보가 없는 탐색이다.
현재 상태에서 목표까지 도달하기 위한 Step을 알 수 없다는 것인데,
정보가 없기 때문에 Informed Search보다 비효율적이고 오랜 시간이 소요된다.
목표 노드의 위치와 관계없이 단순히 일정한 순서에 따라 탐색을 하는 기법이다.
너비 우선 탐색, 깊이 우선 탐색, 깊이 제한 탐색, 점차적 깊이 제한 탐색, 양방향 탐색 등이 있다.
- 구현하기 쉽고 같은 방식으로 여러 문제를 해결할 수 있다.
- 메모리 과부하 및 소모적
경험적 탐색
맹목적 탐색의 반대라고 생각하면 된다.
Informed Search, 정보가 있는 탐색이다.
논리적이거나 수학적이지 않지만 직관에 의해 효율적으로 얻을 수 있으리라는 기대에서 출발하는 기법으로, 정의하기 어려운 대상을 탐험할 때 사용된다.
맹목적 탐색이 위치와 관계없이 일정한 순서에 따라 탐색을 했다면,
경험적 탐색은 탐색 지점(특정 노드)을 사전에 축적된 평가 기준을 토대로 우선 순위를 부여하고 그 순서에 따라 탐색을 한다.
언덕 등반 기법, A* 알고리즘 등이 있다.
- 정의하기 어려운 대상을 탐험할 때 용이하다.
- 알고리즘이 아니고 직관에 의존하기 때문에 구현하기 어렵다.
- 명확한 솔루션이 없기에 솔루션에 허용치를 부과하는 방식으로 탐색
Back-end Developer