인공지능 탐색 알고리즘- Uninformed Search Strategies

Uninformed Search Strategies 란 문자 그대로 정보가 없는 상태에서의 검색 방식입니다. 시작 부분에서 목표까지 도달하는데 얼마나 많은 단계가 존재하는지 목표까지 가는데 걸리는 비용에 대한 정보가 전혀 없는 상태에서 목적지를 찾아가는 최적의 경로를 찾아내는 방식입니다.

 

친구네 집에 놀러가고자 하는데  친구네 집 주소는 알고 있지만 가는 길을 모릅니다. 마치 미로에서 탈출구를 찾는 것과 같은 상황입니다. 여기저기 가보면서 경로들을 찾고 그중 최적의 경로를 찾을 수 있습니다. 

 

바로 이와 같이 알려진 정보없이 길도 모르는데 목적지를 찾아가는 최적의 경로를 찾아라 이것이 Uninformed Search 입니다. 

Uninformed Search Strategies 이란 우리가 알고 있는 트리 검색입니다. 

 

트리 검색에 앞서 알아야 할 몇가지 개념이 있습니다. 

 

Completeness: 만약에 완성도가 Yes 라면 검색을 통해 해결책을 찾을 수 있다는 의미입니다.

Optimality : 최적의 해결책을 찾을 수 있냐의 의미입니다. 여기서 최적이란 최단경로, 최소비용을 의미합니다.

Time : 해결책을 찾는데 걸리는 시간을 의미합니다. 

Space : 검색에 필요한 메모리의 공간을 의미합니다. 

 

 

 

Breadth-first serach, 너비 우선 검색 는 각 층을 모두 검색한 후 아래층을 검색하는 방식입니다.

 

Complete : 가지의 수가 유한하다면(한층에 존재하는 노드의 수가 유한하다면) 시간이 걸리더라도 언젠가는 제일 아래층까지 검색이 가능하며 그 안에서 해결책을 찾을 수 있기에 Complete는 yes입니다.

Optimal : 각 step-cost 가 동일하다면 최소비용 경로를 찾을 수 있습니다. 

Time :  가지의 수 b이고 깊이 d 일 때 O(b^d)입니다. 보통 2^n 만 되어 지수 크기라고 해 엄청난 숫자로서 다루기 불가능함을 의미합니다.

Space :  Time과 마찬가지로 b^d의 크기를 요구합니다. 너비 우선 검색에서 한 층에 존재하는 모든 노드들이 동시에 메모리에 저장되는데 이것이 가장 너비 우선 검색의 가장 큰 문제점입니다. 

 

 

우선 가장 꼭대기층 A를 방문합니다. 그리고 2번째 층 B를 방문한 뒤 옆 방 C를 방문합니다. A -> B -> C. 그래고 다시 3번째 층을 방문합니다. D -> E -> F -> G 순서대로 방을 방문합니다. 그래서 이 트리의 방문 순서는 A -> B -> C -> D -> E -> F -> G입니다.

 

 

가지가 10개인 트리가 있습니다. 위 표는 한층이 추가됨에 따라 생기는 노드의 수와 탐색 시간 필요한 메모리가 적혀 있습니다. 층이 12층만 되어도 모든 노드를 검색하는데 걸리는 시간이 13일이나 됩니다. 뭐 13일 동안 검색하면 되지!라고 할 수 있지만 안타깝게도 페타바이트 즉 1024 테라바이트만큼의 메모리를 가지고 있는 사람이 있을까요? 

 

Depth-first serach 깊이 우선 검색 은 하나의 경로에서 끝단까지 검색한 뒤 다시 처음으로 돌아와 두 번째 경로를 끝단까지 검색하는 방식의 알고리즘입니다. 

 

root node 인 A에서 B를 방문합니다 너비 우선 검색은 A -> B -> C로 가게 되지만 깊이 우선 탐색은 B의 자식 노드 D, E 중 하나의 경로를 택하게 됩니다. D를 택하겠습니다 A -> B -> D에서 다시 D의 자식 노드들 중 하나인 H를 택하겠습니다. A -> B -> D -> H로 경로의 끝단에 도달했습니다. 그리고 다시 D로 돌아가 또 다른 경로를 찾습니다. A -> B -> D -> I의 경로를 찾았습니다. 역시 끝단이기에 다시 백트래킹으로 B까지 올라갑니다. 이런 식으로 모든 노드를 검색하게 됩니다. 

 

이 알고리즘의 Complete와 Optimal, Time, Space에 대해 알아보겠습니다.

 

Complete : 깊이가 무한정 깊어질 경우가 있기에 No입니다. 끝도 없이 하나의 경로를 쫒아가다 보면 다시 돌아올 수 없게 되고 최적의 해를 찾을 수 없게 됩니다. 

Optimal : 목적지로 갈 수 있는 경로 자체가 제한적이기 때문에 최소비용의 경로를 찾는 것이 불가능합니다. 

Time : 가짓수가 b이고 깊이가 m 일 때 시간 복잡도는 O(b^m)입니다. 이는 너비 우선 탐색과 같은 시간 복잡도를 가지고 있습니다. 

Space : O(bm) 로서 아주 적은 메모리를 요구합니다. 왜냐하면 현재 조사 중인 하나의 경로 그리고 대체 경로만 메모리에 저장되어 있기 때문에 아주 적은 메모리만을 소비하게 됩니다. 

 

깊이 우선 탐색은 최적의 해를 찾는 것을 보장하지도 최소비용의 루트를 찾는 것도 불가능하며 검색에는 상당한 시간이 걸립니다. 그럼에도 불구하고 공간의 이점은 아주 큰 장점입니다. 

 

 

Depth-limited search 깊이 제한 검색 이란 깊이가 무한정 깊어져 다시 돌아와 다른 경로를 검색하지 못하는 경우가 발생하지 않도록 깊이에 제한을 두는 방식입니다. 이전에 깊이 우선 검색의 유일한 장점인 Space가 깊이가 무한정해진다면 장점이 되지 못하게 됩니다. 무한대가 b^d 이상이 되어버리면서 무한대 공간을 소비해도 해결책을 찾지 못할 것입니다. 왜 이 경로에는 해결책이 존재하지 않기 때문입니다. 얼른 되돌아가 다른 경로를 찾아야는데 경로의 끝이 없죠. 

 

이러한 무한루프?를 방지하기 위해 깊이에 제한을 두는 것입니다. 그런데 다소 길어 보이는 이 경로의 끝쯤에 해결책이 존재한다면 어떻게 될까요? 해결책을 눈앞에 두고 엄한 길로 되돌아가버리고 나머지 경로를 검색하더라도 결국 해결책을 찾을 수 없게 돼버립니다. 그렇기 때문에 깊이를 제한할 수 있는 좋은 방법이 있을대 이 알고리즘은 효과적입니다. 

 

 

 

iterative deepening depth-first search 반복적 깊이 심화 탐색 이란 깊이 우선 검색에서 깊이 제한을 두되 점차적으로 깊이를 증가시키는 방법입니다. 

 

 

Complete : 기본적으로 깊이 우선 탐색이기 때문에 Space에 장점을 갖추고 있는 데다가 깊이 제한을 통해 너비 우선 검색의 장점을 가질 수 있어 해결책을 찾을 수 있습니다. 

Optimal : 너비 우선 검색도 가능하기 때문에 최단경로를 찾을수 있습니다.

Time : 너비 우선 검색 트리의 시간 복잡도인 O(b^d)를 가지고 있습니다. 

Space : 현재 검색 중인 경로와 이 경로에서 추가적으로 탐색 가능한 대체 경로에 대한 정보만을 저장하기 때문에 깊이 우선 검색과 마찬가지로 O(bd)의 공간을 차지하게 됩니다.

 

반복적 깊이 심화 탐색은 깊이 우선 탐색 + 너비 우선 탐색의 방법을 적절히 이용하기 때문에 깊이 우선 탐색의 공간적 이점과 너비 우선 탐색의 완성도, 최적화의 장점을 모두 취하고 있습니다. 그런데 말이죠! 분명히 이름에서 반복적!! 이란 문구가 들어가는 것을 보아 이전에 탐색한 경로를 또다시 탐색하는 번거로움 때문에 비효율적이지 않을까 라고 생각할 수 있습니다. 하지만 실질적으로 비효율성을 크게 늘어나지 않습니다. 예를 들어 각 노드가 10개의 지식 노드를 가질 때  너비 우선 탐색 대비 약 11% 정도의 추가 노드가 생성될 정도의 비효율성이 늘어납니다. 

 

어쨌든 이 반복적 깊이 심화 탐색 이 가지는 공간의 절약이라는 장점으로 인해 자원이 제한적인 상황에서 유용한 알고리즘입니다. 

 

Bidirectional search 양방향 탐색 이란 하나의 root node에서 출발하는 것이 아니라 양방향에서 출발해 해결책을 찾는 방법입니다. 두 방향에서 검색을 시작하기 때문에 시간 복잡도 측면에서 장점을 가지고 있습니다. 우리가 위에서 살펴본 탐색 알고리즘들은 O(b^d)의 시간 복잡도를 가지고 있습니다. 하지만 이 양방향 탐색은 2가지 b에서 시작하지만 탐색시간으 2배로 줄게 되어 O(2b^d/2)의 시간 복잡도를 가지고 됩니다. start와 goal에서 시작하기 때문에 2b가 되며 d/2 는 start 와 goal 에서 동시에 검색을 하기 때문에 줄어드는 깊이입니다. 

 

예를 들어 키워드를 검색할 때 Bidirectional search에서 하나는 B에서 시작해 i-d-r-e를 찾고 나머지 하나는 h에서 시작해 h-c-r-a 식으로 찾아가게 됩니다. 

 

그런데 말이죠! 이 반복적 깊이 심화 탐색 은 쉽지 않은 녀석입니다. 그 이유는 start에서 시작한 검색과 goal에서 시직 한 검색이 만나는 것은 상당한 비용이 드는 업무입니다. 

 

 

영화 마션 마지막 장면에 주인공 마크 와트니의 구출 장면입니다. 우주 공간 속에서 둘은 가까이 다가는 가지만 도킹?은 실패합니다. 마찬가지로 start와 goal 이 근처까진 다가가지만 한 노드에서 만나는 것은 쉽지 않습니다. 

 

두 번째로는 start에서 갈 수 있는 goal은 하나가 아니라는 것입니다.  start에서 설정한 목표는 맛있는 식당을 찾아가는 것입니다. 그렇게 goal에는 가장 핫한 식당으로 설정해 놓았지만 start에서 경로를 탐색하는 중 조금 덜 핫하지만 대기시간이 적은 곳으로 가기로 정했습니다. 이렇게 start에서 설정할 수 있는 goal은 단 하나로 정하지 않기 때문에 양방향 탐색이 어려운 이유입니다.

 

그 밖에는 backward step의 구성이 어렵고 backwards branching factor 가 실제 가짓수보다 커질 수 있다는 문제들이 있습니다. 저도 솔직히 이 부분은 잘 이해가 안돼서 그냥 언급만 하겠습니다. 

 

이번 글에는 Uninformed Search 의 몇가지 검색 알고리즘에 대해서 알아보았습니다. 다음 글에는 Uninformed Search 와는 반대로 알려진 정보를 이용해 goal에 다가가기 위한 더욱더 효율적인 경로를 찾을수 있는 Informed Search에 대해 알아 보겠습니다.