[인공지능 입문]탐색 알고리즘

안녕하세요

 

오늘은 인공지능 시스템이 문제 해결을 위해서 사용하는 기법 중 '탐색' 기법에 대해 알아보겠습니다.

문제를 해결하기 위해서는 어떤 방법이 가장 효율적이고 최단 시간이 걸리는지 등 방법 탐색이 필요한 경우가 많습니다.

미로찾기를 예로 들면 사람이라면 직관적으로 또는 일부 시행착오 과정을 거쳐 가장 효율적인 길을 찾을 수 있겠지만 컴퓨터는 직관적일 수 없기 때문에 다양한 경우의 수를 고려하여 길을 탐색해야 합니다.

 

인공지능은 주어진 문제를 빠른 시간 내 정확한 계산 과정을 거쳐 답을 내는 것이 매우 중요합니다. 그렇기 때문에 아무리 정확한 답이라고 해도 시간이 너무 오래 걸리면 무용지물이 됩니다. 가능한 바른 시간 내에 답을 찾아내는 여러가지 기법에 대해 알아보겠습니다.

 

'무정보 탐색기법'은 시작점인 초기상태에서 목표인 목표상태(목적상태)까지 도달하는 중간 상태들을 찾는 기법입니다. 처음부터 끝까지 생길 수 있는 모든 상태들을 탐색하는 것입니다. 이러한 상태들의 집합을 상태공간이라고 하며, 탐색의 대상으로 생각되는 것을 탐색 공간이라고 합니다. 여기에는 '깊이우선 탐색'과 '너비우선 탐색'이 있습니다.

 

'깊이우선 탐색'은 이 기법은 순서를 정하여 한 방향으로 간 뒤 끝이 나오면 다시 돌아와 다른 길로 가는 방식으로 모든 방법을 반복합니다. 그러나 이 기법은 시작노드에서 목적노드까지의 가장 짧은 거리를 처음에 찾는 것을 보장할 수 없다는 것입니다. 모든 방법을 찾은 뒤에야 가장 최단 거리를 찾을 수 있는 것입니다.

 

'너비우선 탐색'은 상위 노드를 하위 노드보다 먼저 탐색하는 기법으로 탐색 방향이 깊이 우선 탐색과는 다르기 때문에 처음 찾는 방법이 가장 최단거리의 방법이 됩니다. 즉 너비우선 탐색은 깊이우선 탐색과 다르게 자노드보다 형제노드를 먼저 탐색하는 것을 알 수 있습니다. 

 

'휴리스틱 탐색'은 탐색공간에 관한 정보를 탐색에 활용하여 탐색 공간을 줄이거나, 정확한 답이 아니어도 가능한 근사값을 빨리 찾을 수 있도록 하는 탐색 기법입니다. 즉 빠른 시간 내 가장 가까운 답을 도출해낼 수 있는 탐색 기법입니다. 여러 가지 경우의 수가 많은 문제를 한 가지 조건으로 빠른 시간 내 사용 가능한 답을 찾아내는 것이다. 물론 정확하지는 않지만 문제 해결을 목적으로 한다면 사용 가능한 기법입니다. 여기에는 '언덕등반 탐색'과 '최고 우선 탐색','A*알고리즘' 기법이 있습니다.

 

'언덕등반 탐색'은 높은 언덕을 찾기 위해서 현재 자신보다 높은 언덕을 오르는 방법을 말합니다. 깊이 우선 탐색과의 차이점은 깊이우선 탐색은 언덕이 높은지 안높은지 정보를 고려하지 않고 모든 언덕을 올라보는 방식이지만, 언덕등반 탐색은 현재의 자신보다 높은 언덕을 기준으로 오른다는 차이점이 있습니다. 문제는 저 멀리 더 높은 언덕이 있음에도 주변에 있는 언덕들은 높지 않아 목적에 도달하지 못하는 '지역최고 상태'에 빠지는 것입니다.

 

'최고우선 탐색'은 언덕등반 탐색 알고리즘을 개선한 탐색기법으로, 지역최고 상태에 빠지지 않도록 언덕을 오르면서 더 높은 언덕이 없는지 자료를 업데이트 해가면서 오르는 방법입니다. 현재의 언덕만을 대상으로 하는 언덕등반 탐색과는 다른 업그레이드 된 탐색 기법이라고 할 수 있습니다.

 

'A*알고리즘'은 시작점에서 목적점까지 최단 경로를 찾아야 하는 경우 사용하는 탐색 기법입니다. 시작점에서 현재점까지의 최단 거리를 구한 뒤 현재점에서 목적점까지의 최단 거리를 구하여 두 거리를 더하는 것을 계산됩니다. 탐색 순서에 따른 거리르 계산하여 가장 짧은 거리로 이동한 경로를 최종 경로로 인식하는 것입니다. 최고우선 탐색은 현재점에서 목적점까지의 거리만을 계산하지만 A*알고리즘은 시작점 - 현재점 - 목적점의 모든 거리를 계산하기 때문입니다.

시작점에서 목적점 사이에 최단 경로가 존재하고 이를 항상 찾을 수 있는 탐색 알고리즘은 '허용성'이 있다고 합니다. 너비우선 탐색 기법과 비교하면 탐색공간의 크기가 너비우선 탐색이 더 크다고 말할 수 있습니다. 

 

다음은 '게임과 탐색' 중 'Minimax 기법'과 '알파베타 절단 기법'에 대해 알아보겠습니다.

 

'Minimax 기법'에서 게임을 이기고자 하는 사람을 MAX라 하고 MAX의 점수를 적게 하여 자기가 이기고자 하는 상대편을 MIN이라고 합니다. 각 레벨에서 MAX는 평가함수값 중 가장 큰 값을 선택하고, MIN은 가장 작은 값을 선택하는 것입니다. 가능한 깊게 탐색하는 것이 좋지만 특정 레벨의 깊이를 정하여 정해진 시간 내 답을 찾을 수 있는 '시계제한 효과'가 발생할 수 있습니다. 

 

'알파베타 절단기법'은 상태 공간 중에 탐색에 고려하지 않아도 되는 것들은 절단하여 탐색 공간을 줄이는 탐색기법입니다. MAX 값인 알파와 MIN 값인 베타값을 사용합니다. 알파값이 절단되면 알파 절단, 베타값이 절단되면 베타 절단이라고 합니다. 더 적은 탐색 공간을 통해 빠른 시간 안에 더 많이 탐색할 수 있는 장점이 있습니다. 

 

문제를 해결하기 위해서는 가능한 경로를 빠르고 쉽게 찾는 것이 중요할 것입니다. 문제를 탐색해가는 과정은 데이터의 성격이나 배열, 양에 따라 달라질 수 있습니다. 시간에 따른 제약도 있을 것입니다. 중요한 것은 어떻게 하면 가장 빠른 시간 안에 더 정확한 답을 찾아 낼 것인가입니다. 그리고 어느 한쪽을 선택해야 한다면 덜 피해를 입을 수 있도록 선택하는 것이 중요하겠습니다. 

다음에는 논리와 자동 논증에 대해 알아보겠습니다.

 

감사합니다.