[ALGO/AI] 탐색과 탐색 알고리즘(search and search algorithm)

탐색?

문제의 해(solution)이 될 수 있는 것들의 집합을 상태공간(state space)로 간주하고, 문제에 대한 최적의 해(Optimal solution)을 찾기 위해 공간을 찾아보는 것을 탐색이라고 한다. 즉 초기 상태에서 출발하여 목표상태에 도달하는 경로(또는 연산자들의 순서)를 찾는 것을 탐색이라고 한다. 그리고 탐색 알고리즘이란 이런 과정을 수행하도록 설계된 알고리즘을 이야기한다. 

여기서 탐색에서 이야기하는 용어들을 정의해보자.

상태(state): 특정 시점에 문제가 처해있는 모습
- 초기 상태(initial state): 문제가 주어진 시점의 시작 상태
- 목표 상태(goal state): 문제가 원하는 최종 상태
동작(action): 상태의 변화(특정 상태에서 다른 상태로의 움직이는 행동)
상태공간(state space): 문제해결 과정 중 초기상태에서 목표상태에 도달 할 수 있는 모든 상태들의 집합(즉 문제의 해가 될 수 있는 모든 상태들의 집합)
해공간(solution space): (목표상태가 여러 개일 경우) 모든 목표 상태의 집합

문제 정의(Formulating problems)

인공지능을 이용해 기계적으로 문제를 탐색하기 위해서는 문제에 대한 형식화가 필요하다

1. 초기 상태 정의(Initial state): 어디서 또는 어느 상태(state)에서 시작하는지 정의
2. 가능한 동작 정의(action): 에이전트가 행할 수 있는 모든 동작을 의미한다. 상태 s가 주어지면 Actions(s)는 s에서 실행할 수 있는 작업의 집합을 반환한다.
3. 전의 모델 (Transition model): 각 동작의 기능에 대한 설명이다. 후속 상태는 주어진 상태에서 단일 동작을 수행하여 주어진 상태에서 도달할 수 있는 모든 상태를 의미한다..
4. 목표 도달 확인(Goal Test): 가능한 동작을 통해 목표 상태에 도달했는지 확인한다.
5.경로 비용(Path cost) 확인: 어떤 state에서 action을 취해 다른 state로 가는 것을 path라고 하고 이때 드는 비용을 path cost라고 한다.

여기서 transition model에 대해 보충하자면 2x1의 공간을 이동하는 문제가 있다고 가정하자. 이럴 경우 actions = {Left, Right}로 정의되고 transition model는 moves Left, moves Right, 오른쪽 끝에 있다면 오른쪽으로 이동할 수 없음, 왼쪽 끝에 있다면 왼쪽으로 이동할 수 없음 의미한다. 

자세한 예시로 한 번 보도록 하자.

States : 여기서 상태는 에이전트(청소기)의 위치와 먼지의 위치 모두에 의해 결정된다. 에이전트는 두 위치 중 하나에 있으며, 이 위치에는 먼지가 있을 수도 있고 없을 수도 있다. 따라서 가능한 states는 $2 \times 2^2=8$개가 된다. 가능한 location이 많아지면 $n \times 2^n$개의 states가 된다.
Initial state:모든 상태를 초기 상태로 지정할 수 있다.
Actions: 이 간단한 환경에서는 각 상태에는 세 가지 동작만 있습니다: Left, Right, 그리고 Suck. 환경을 확장한다면 Up과 Down도 포함될 수 있다.
Transition model: 오른쪽으로 이동, 왼쪽으로 이동, 흡입하기. 가장 왼쪽 사각형에서 왼쪽으로 이동하기, 가장 오른쪽 사각형에서 오른쪽으로 이동하기, 깨끗한 사각형에서 흡입하기는 아무런 효과가 없다.
Goal test: 모든 사각형이 깨끗한지 확인한다.
Path test: 각 단계의 비용은 1이므로 경로 비용은 몇번 작업을 수행했는가이다.

상태 공간 그래프(State Space Graph)

인공지능에서는 상태공간에서 최적의 해를 찾기 위해서 각 동작에 따른 상태 변화를 그래프로 나타내어 표현한다.

따라서 탐색 전략 역시 tree 구조에서 어떠한 순서로 노드를 확장할지 고르는 전략으로 생각할 수 있다. 

탐색 알고리즘

탐색 알고리즘은 크게 uniformed search와 Informed search로 구분할 수 있다.

uninformed search(무정보 탐색)은 탐색공간을 탐색하는 가장 단순하고 직관적인 (intuitive) 방법을 사용한다. 반면에 informed search(정보 탐색, 휴리스틱 탐색)은 알고리즘은 탐색시간을 줄이기 위해 탐색공간의 구조에 대한 지식을 응용하는 휴리스틱을 사용한다.

물론 무정보 탐색과 정보 탐색 외에도 지역 탐색, 게임 탐색 같은 알고리즘도 존재한다.

Uninformed Search

이는 blind search라고도 불리우며, 문제 정의에 제공된 것 외에 상태에 대한 추가 정보가 없음을 의미한다. 즉, 주어진 정보만 활용해 탐색하는 방법이다. 상태 공간에 대한 아무런 정보 없이, 정해진 순서에 따라 상태 공간 그래프를 점차 생성해 가면서 해를 탐색해간다.

문제의 독특한 성질을 고려하지 않아 쉽게 구현할 수 있고 똑같은 구현방식을 추상화 (abstraction) 해서 넓은 범위의 문제들에 사용가능하게 한다. 리스트 탐색 알고리즘, 트리 탐색 알고리즘 등이 이곳에 속한다.

대표적인 무정보 탐색에는 너비우선 탐색(BFS), 깊이우선 탐색(DFS), 반복적 깊이증가 탐색 (Iterative Deepening Depth-first Search), Depth-limited search, 양방향 탐색 (Bidirectional Search), Uniform-cost search 등이 있다.

Informed Search

상태 공간에 대한 추가적인 정보나 지식을 활용해서 탐색한다. 휴리스틱($H(n)$, 평가함수)을 이용하기 때문에 휴리스틱 탐색이라고하기도 한다.

휴리스틱(Heuristic): optimal solution을 찾는다는 보장은 없지만 신속한 어림짐작을 통해 충분히 좋은 해를 찾을 수 있는 경험적 지식. 잘 추측하는 기술 (art of good guessing) 이라고 표현하기도 한다.

대표적인 정보이용 탐색에는 최선 우선 탐색, 빔 탐색, A*알고리즘이 존재한다.

Local Search

지역적인 탐색을 하는 알고리즘으로 현재의 상황만 대충 파악해서 가장 적절하다고 여겨지는 행동을 한다. 또한 대부분의 탐색에서 경로는 그닥 중요하지 않다. 따라서 지역 탐색에서는 경로를 무시한다. 적은 메모리를 이용하며, 무한하거나 아주 큰 상태 공간에서 합리적인 해를 찾는다.

언덕오르기 알고리즘(경사하강법), Genetic Algorithms, Simulated Annealing Search, Continuous State Spaces, Constrained Optimization Problem 등이 대표적이다.

Game Search

적대탐색 (adversarial search)이라고 부르기도 하며, 두 개 이상의 에이전트가 서로 적대적인 관계를 가진다고 가정했을 때 이루어진다. 여러 agent가 서로의 이득을 취하기 위해 움직이는 상황을 ‘게임’이라고 하기 때문에 game search라고 부른다. 상대방의 행동을 예측하고 그 결과를 활용하여 내 이익을 극대화 시키며 탐색을 진행한다.

최소최대 (Mini-max) 알고리즘, search tree pruning, 알파베타 가지치기 (Alpha-Beta Pruning) 과 같은 탐색 알고리즘이 존재한다.

참고

AIMA-3rd-edition

https://web.cs.ucla.edu/~srinath/static/pdfs/AIMA.pdf

http://www.aistudy.com/heuristic/search.htm