[인공지능] Uninformed Search란? (Blind Search, Search trees, State Space)

Uninformed Search란 무엇인가? 

• Blind Search라고도 불리는 이 방법은 문제 해결을 위한 탐색 전략 중 하나이다 (=search algorithm)
• "uninformed"로 알 수 있듯이 목표 상태(goal state)에 도달하기 위해 탐색 공간(search space) 내에서 결정을 내릴 때, 문제에 대한 사전 지식(heuristic information) 없이 단순히 탐색 공간을 넓혀가는 방식이다
• 이와 대조되는 알고리즘은 "Informed" 혹은 "Heuristic" Search라고 한다

목표 상태? 탐색 공간?

Uninformed Search 알고리즘에 대해 완벽히 이해하기 위해선 State Space의 개념부터 파악할 필요가 있다.

 

State Space란? 

• 탐색문제 (search problem)의 요소 중 하나인 상태공간(state space)은 특정 문제를 해결하기 위해 고려해야 할 모든 가능한 상태들의 집합이다 
• 예를 들어, 특정 도시에서 출발하여 목표도시까지 달성하기 위한 탐색문제에서 state space는 이 약도에 있는 모든 도시들이다. 

CS188

조금 더 복잡한 예시를 들어보자.

• 클래식 게임 PAC-MAN에서 모든 점(dot)을 먹는 탐색 문제가 주어진다면, state space는 무엇으로 구성될까? 
  • Agent position 팩맨의 위치
  • Ghost position 유령의 위치
  • Dot boolean 점의 상태 {먹힘,안먹힘}
  • Power pellet boolean 파워 펠릿의 상태 

CS188

 

Tree Search 트리 탐색?

주로 트리 구조를 사용하여 탐색 알고리즘을 구현한다. 

GeeksForGeeks

• 탐색문제의 state space를 트리 구조로 모델링하고, 노드를 확장하며 트리를 시스템적으로 탐색하는 방법이다
• 구체적인 탐색 전략에 따라 다양하게 구현될 수 있다 (깊이 우선 탐색할까? 너비 우선 탐색할까?)

아래는 트리 탐색의 유사코드이다:

• 구체적인 탐색 전략이 이 유사코드의 "strategy"가 되고, 탐색 문제가 "problem"이다
• 우선, 탐색트리를 초기화한다. 루트 노드를 생성하여 탐색 대기열(스택, 큐)에 넣는다.
• 다음, 탐색 대기열이 비어있지 않는 동안 루프를 실행하는데, 
  • 탐색 대기열에서 노드를 선택한다
  • 선택된 노드가 목표상태인가? 맞으면 =>  탐색을 종료한다
  • 아니라면 => 노드를 확장한다 (이때 확장 방법은 각 알고리즘의 전략에 따라 다르다)
  • 생성된 후속 노드들을 탐색 대기열에 추가하여 업데이트한다
• 결과 반환: 목표 상태에 도달한 노드를 찾으면 그 노드에서 초기 상태까지의 경로를 역추적하여 해결책을 반환한다

 

그렇다면, Uninformed Search 알고리즘의 트리 탐색은 어떠한 전략들이 있을까?

 

Uninformed Search 알고리즘의 Search Strategy

1) 깊이 우선 탐색 Depth-First Search: 탐색 대기열을 Last-in-Last-out 스택으로 관리하는 전략이며, 뿌리하나를 완전히 탐색한 후 다음 트리로 넘어가는 방식이다. 

 

2) 너비 우선 탐색 Breadth-First Search : 탐색 대기열을 First-in-First-out 큐로 관리하는 전략이며, 트리의 루트노드로 시작하여, 한층 한층 씩 탐색하는 방식이다.

 

3) 비용 기반 탐색 Uniform Cost Search : 탐색 대기열을 우선순위 큐로 관리하며, 누적 비용이 가장 낮은 노드를 가장 먼저 확장한다. 비용 측에서 가장 효율적인 방법이다.

 

탐색 알고리즘의 고려 요소

탐색 알고리즘들의 특징이나 효율성을 분석하기 위해서 여러 요소들을 고려해야한다. 

• Time Complexity: 시간복잡도는 얼마인가?
• Space Complexity: 공간복잡도는 얼마인가?
• Completeness: 완전한가?
• Optimality: 최단 경로인가?