인공지능 Uninformed Search, BFS, DFS, Depth-limted Search, Iterative Deepening Search, Bi-directional Search 알고리즘들의 차이점

지난 글에서 Uninformed Search Starategs 중 BFS, DFS,  Depth-limted Search,  Iterative Deepening Search, Bi-directional Search 알고리즘들에 대해 알아보았습니다. 역시 그렇듯이 여러 가지를 동시에 배우면 잘 알던 것도 헷갈리고 이게 누구의 장점인지 단점인지 더 헷갈립니다. 그래서 각 알고리즘들의 특징을 눈에 보기 쉽게 정리하고자 합니다. 

 

 

죄송하게도 저는 Uniform-Cost Search에 대해서는 언급하지 못했습니다 너비 우선 검색에서 각 노드에 다양한 코스트를 부여하는 방법으로 최소비용이 드는 경로를 찾기 위해 사용되는 알고리즘이라고만 알고 있는데 저도 잘 이해가 안 돼 언급하지 못했습니다. 

 

아무튼 그외 나머지 탐색 알고리즘들의 특징들? Complete, Time, Space, Optimal에 대해 설명된  표가 위에 있습니다. 

 

 

 

너비 우선 검색부터 알아보겠습니다. Complete 가 yes입니다. 이 말은 root node에서 n층을 검색할 때 n층의 노드의 수가 무한하지 않다면 해결책을 찾을 수 있습니다.

 

모든 층의 모든 노드를 다 방문하기 때문에 완벽하게 해결책을 찾을 수 있고 최적의 경로 역시 찾을 수 있습니다. 그래서 Optimal 도 yes입니다.

 

Time과 Space에 대해 언급하자면 하나의 노드마다 b개의 노드가 추가되며 깊이가 d일 때 검색에 필요한 시간과 공간은 O(b^d)입니다. 특히나 한층에 존재하는 모든 노드가 동시에 메모리에 저장되기 때문에 깊이가 깊어질수록 엄청난 공간을 요구하게 됩니다. 완벽한 최적의 해결책을 찾을 수 있음에도 불구하고 이 공간은 너비 우선 검색에서 가장 큰 문제입니다. 

 

 

 

깊이 우선 검색은 하나의 경로를 정해 이 경로의 끝까지 조사하는 방식입니다. 탐색하는 중 갈림길이 생긴다면 하나의 길을 조사 후 다시 되돌아와 나머지 길을 검색합니다. 되돌아가는 이 과정을 backtracking 또는 backward라고 합니다.

 

나는 한놈만 패! 같은 뚝심으로 한길만 파는 이 탐색법은 그 길이 끝이 없는 경우 다시 되돌아 올수 없게 됩니다. 그렇기 때문에 complete는 no입니다. 마찬가지 이유로 optimal 역시 no입니다. time은 너비 우선 검색과 마찬가지로 O(b^m) 이 걸립니다.

 

모든 층의 모든 방을 다 검색하는 것이 uninform search 의 기본 전략이기 때문이죠. 하지만  space 현재 탐색 중인 경로와 갈림길에 나온 대체 경로만 메모리에 저장해 두기 때문에 공간에서 큰 장점을 가지고 있습니다. 오직 O(bm)의 메모리만 차지하게 됩니다. 그렇기 때문에 해결책도 못 찾고 최적의 경로도 찾지 못하는 깊이 우선 탐색을 쓰는 이유이기도 합니다. 

 

 

 

깊이 제한 탐색 은 깊이 우선 검색의 단점 현재 조사중인 경로가 무한대일 경우 무한 루프에 빠지게 되는 단점을 보완한 방식입니다. 깊이가 어느 정도일지 모르니깐 먼저 깊이에 제한을 두고 조사하자라는 개념이 추가되었습니다. 

 

하지만 깊이를 제한했는데 해결책이 이 제한된 공간 안에 존재한다면 아예 그곳을 가지 못하게 되어 해결책을 찾지 못하게 될 것입니다. 그리고 최적의 경로를 가는 길이 이 제한 때문에 막혀 버릴 것입니다. 그렇기 때문에 complete와 optimal 은 no입니다. 

 

마 친가지로 깊이 우선 검색을 바탕으로 하기 때문에 time 은 O(b^m) space는 O(bm)입니다. 이 탐색법은 깊이 우선 검색에서 깊이가 무한대가 되는 상황을 대비할 뿐입니다. 

 

 

 

반복적 깊이 증가 탐색 은 너비 우선 탐색의 장점 (complete 와 optimal)과 깊이 우선 탐색 (space)을 모두 취한 방식입니다. 깊이의 제한을 점차 증가시켜가는 방식으로 탐색을 하게 됩니다. 장점만을 택했기 때문에 complete와 optimal 도 yes이고 공간은 오직 O(bm)만 차지할 뿐입니다. 

 

 

 

양방향 탐색은 start 와 goal 양쪽에서 검색을 시작해 중간점에서 만나는 방식입니다. 그래서 경로에 대한 경우의 수는 2배로 늘지만 깊이는 반으로 줄어들게 됩니다. 그래서 time과 space는 O(b^m) 이 2b가 되고 m은 m/2 가 되어 O(2b^m/2)가 됩니다. complete와 optimal 역시 yes입니다. 하지만 양방향 탐색은 구현 자체가 어렵다는 장점이 있습니다.

 

이번 글에서는 각 탐색 알고리즘의 특징과 차이점에 대해 알아봤습니다. 아마 시험? 등에서 이들에 대한 특징과 차이점을 물어보는 문제들이 많이 나오는 것으로 알고 있는데 헷갈리지 않게 특성들을 잘 이해하기 바랍니다.