인공지능 : 핵심기술 (3) : 검색, 탐색 알고리즘

AI : 검색 알고리즘

인공지능은 이성적으로 행동하는 요원을 만드는 학문입니다. 대부분의 경우, 목표를 달성하기 위해 어떤 종류의 검색 알고리즘을 백그라운드에서 수행합니다.

검색 문제는 다음과 같이 구성됩니다.

A State Space : 있을 수 있는 모든 가능한 상태들의 집합.

A Start Space : 검색이 시작되는 시점부터의 상태.

A Goal Test : 목표 상태인지 아닌지를 반환.

검색 문제의 해결책은 시작 상태를 목표 상태로 변환하는 계획으로 하는 일련의 동작입니다. 이 계획은 검색 알고리즘을 통해 달성됩니다. 

검색 알고리즘 유형

강력한 검색 알고리즘이 너무 많아서 모든 것을 다룰 수는 없습니다. 대신, 아래 나온 것과 같이 두 가지 범주로 나누어 6가지 기본 검색 알고리즘에 대해 알아보겠습니다.

Uninformed 검색 알고리즘

이 검색 알고리즘은 문제 정의에 제공된 것 외에 목표 노드에 대한 추가 정보를 가지고 있지 않습니다. 출발 상태에서 목표 상태에 도달하는 계획은 순서 또는 길이에 의해서만 달라집니다. 이러한 검색은 블라인드 검색이라고도 불립니다.

Depth First Search

Breath First Search

Uniform Cost Search

각 알고리즘에 대해 알아보겠습니다. 

Depth First Search

깊이 우선 검색(DFS)은 트리 또는 그래프 데이터 구조를 이동하거나 검색하기 위한 알고리즘입니다. 알고리즘은 루트 노드에서 시작하여 각 분기를 따라 가능한 한 멀리 탐색한 후 역추적을 합니다.

Breadth First Search

BFS(Breadth-first search)는 트리 또는 그래프 데이터 구조를 이동하거나 검색하기 위한 알고리즘입니다. 트리 루트에서 시작하여 다음 깊이 수준에서 노드로 이동하기 전에 현재 깊이에서 모든 인접 노드를 탐색합니다.

Uniform Cost Search

UCS는 BFS 및 DFS와 다릅니다. 왜냐하면 비용이 발생하기 때문입니다. 즉, 다른 가장자리를 통한 이동은 동일한 비용을 가지지 않을 수 있습니다. 누적 비용 합계가 가장 적은 길을 찾는 것이 목표입니다.

Informed 검색 알고리즘

여기서, 알고리즘은 목표 상태에 대한 정보를 가지고 있으며, 이것은 더 효율적인 검색에 도움이 됩니다. 이 정보는 휴리스틱이라고 불리는 것에 의해 얻어집니다.

이 절에서는 다음과 같은 검색 알고리즘에 대해 논의합니다.

Greedy Search

A* Tree Search

A* Graph Search

검색 휴리스틱스 : 정보에 입각한 검색에서 휴리스틱은 상태가 목표 상태에 얼마나 가까운지를 추정하는 함수입니다. 아래에 설명된 서로 다른 정보 알고리즘에는 다양한 휴리스틱스가 사용됩니다.

Greedy Search

탐욕스러운 검색에서는 목표 노드에 가장 가까운 노드를 확장합니다. "closeness"는 휴리스틱 h(x)로 추정됩니다.

A* Tree Search

A* Tree Search 또는 간단히 A* Search로 알려진 Tree Search는 균일한 비용 검색과 탐욕스러운 검색의 장점을 결합한 것입니다. 이 검색에서 휴리스틱은 g(x)로 표시된 UCS 비용의 요약과 h(x)로 표시된 탐욕스러운 검색의 비용입니다. 총 비용은 f(x)로 표시됩니다.

A* Graph Search

A* Tree Search는 이미 탐색한 가지를 다시 탐색하는 데 시간이 걸린다는 점을 제외하면 효과가 좋습니다. 즉, 동일한 노드가 검색 트리의 서로 다른 가지에서 두 번 확장된 경우 A* 검색은 두 가지 지점을 모두 탐색하여 시간을 낭비할 수 있습니다.

A* Graph Search 또는 단순 그래프 검색은 다음과 규칙을 추가하여 이 제한을 제거합니다. (규칙 : 동일한 노드를 두 번 이상 확장하지 말아야 합니다. )

휴리스틱 : 그래프 검색은 h(A) - h(B) 가 부여한 두 연속 노드 A와 B 사이의 선비용이 해당 노드 g(A -> B) 사이의 후비용보다 작거나 같을 때만 최적입니다. 그래프 검색 휴리스틱의 이러한 속성을 Consistency이라고 합니다.