인공지능 탐색 알고리즘 1-기본

우선 검색 알고리즘의 종류에 대해 알아보기 전에 검색알고리즘에 대한 간단한 용어에 대해 알아 보려고 합니다.

먼저 그림을 보시면 Arad에서 Bucharest까지 가는 최적의 길을 찾으려고 합니다.

각 노드간의 숫자는 거리입니다. 

따라서 가장 적은숫자(가장 빠른길)로 가는 길을 찾으려고 합니다.

위 그림처럼 초기 상태에는 Arad 밖에 없고, Arad에서 갈 수 있는길은 Sibu, Timisoara, Zerind 

3군데입니다.

그리고 밑으로 내려와 갈 수 있는 길을 보면, 각각의 길에서 Arad가 또 반복되게 됩니다.

이렇게 되면 그 밑에서 무한루프에 걸리게 됩니다.

이러한 탐색(Search)을 Tree Search라고 하고, 

이전에 나왔던 걸 배제하는 탐색(Search)을 Graph Search라고 합니다.

그리고 위 그림의 (b)에서 이미 전개한 것(expanding)은 explored set이라고 하며,

그 밑의 전개되지 않은 것은 frontier라고 합니다.

frontier의 경우 queue라는 일종의 메모리에 저장되는데 종류로는

FIFO(First Input First Output)와 LIFO(Last Input First Output)가 있습니다.

Graph Search의 경우 중복을 막기위해서는 임의의 메모리 공간에 explored set을저장해야 합니다.

탐색 알고리즘의 평가기준으로는 

Completeness, Optimality, Time complexity, Space complexity등이 있으며, 

Space complexity에는 branching factor와 depth가 있습니다.

탐색 알고리즘의 종류로는 크게 Uninformed Search와 Informed Search가 있습니다.

Uninformed Search는 현재까지의 소요비용만으로 탐색하는 방법이고,

Informed Search는 그 외의 정보를 더하여 탐색하는 방법입니다.

평가함수 f(n), 지난비용 g(n), 휴리스틱함수 h(n)라 하면

Uinformed Search의 경우 f(n)=g(n)이고, Informed Search는 f(n)=g(n)+h(n)이 됩니다.