컴언

[인공지능] 무정보탐색(Uninformed Search)

Natural Language Processing

인공지능이 다루는 문제들은 대부분 탐색 알고리즘으로 해결할 수 있습니다. 오늘 다룰 탐색 알고리즘들은 모두 무정보탐색 (Uninformed Search) 의 분류 안에 있습니다. 무정보탐색이란, (1) 목표 상태공간 (goal state) 에 도달하기 위해 필요한 단계의 횟수나 비용을 모르지만 (2) 어떤 상태 공간이 목표 상태공간인지 구분(goal test)할 수 있을 때를 의미합니다. 그래서 blind search 라고 불리기도 해요. (1)을 좀 더 설명하자면, 목표에 도달하기 위한 과정에 대한 정보가 없기 때문에 어떤 상태 공간을 먼저 탐색하는 게 좋을지 결정할 수 없다는 것이죠. 어떤 상태를 먼저 탐색하는게 좋을지에 대한 정보가 주어지게 되면 informed search 가 됩니다.


무정보탐색 알고리즘의 종류에는 BFS (너비 우선 탐색), DFS (깊이 우선 탐색), Uniform Cost Search (단일 비용 탐색), Iterative Deepening (반복적 깊이 증가) 가 있습니다. 미리 말하자면 대부분의 무정보탐색의 경우에는 Iterative Deepening 이 가장 효율적인 것으로 알려져 있습니다.




BFS

너비 우선 탐색의 기본 원칙은 얕은 곳 부터 깊은 곳 까지, 모든 노드들을 깊이 별로 차례 차례 훑는 것입니다. 위 그림을 가지고 설명하자면,


(1) start 노드에서 1 깊이 만큼 떨어진 빨간색 노드들을 방문

(2) start 노드에서 2 깊이 만큼 떨어진 파란색 노드들을 방문

(3) ... 맨 마지막 깊이까지 반복 


실제 구현을 위해서는 큐 자료구조를 이용하고요, 의사 코드는 아래와 같이 짜볼 수 있겠습니다.


function BFS(start-state){

    queue.EN_QUEUE(start-state)

    while (queue is NOT empty){

        state = DE_QUEUE()

        if (state == goal) then SUCCESS

        for s in successors: s.prev=state // 나중에 경로 추적을 하기 위함

        queue.EN_QUEUE(succsessors of state)

    }

}


BFS 는 목표에 도달하기 직전까지 무작정 상태공간을 생성하다보니 성능은 그리 좋다고는 할 수 없습니다. 시간 복잡도는 O(b^d), 공간 복잡도도 O(b^d) 이기 때문이죠. (참고로 b 는 한 깊이 내려갈 때 마다 평균적으로 뻗어나가야 하는 줄기의 평군 갯수(branching factor), d 는 깊이를 의미합니다) 다른 탐색 알고리즘의 시간/공간 복잡도를 보시면 왜 BFS 가 대부분의 문제 해결에서 비효율적인지 알게 되실겁니다.



위 표를 보면, branching factor 가 10이라 가정했을 때 2 깊이 씩만 나아가는데도 8 깊이에서 벌써 31 시간이 소요되고 결국 14 깊이에서는 3500 년, 11111 테라바이트가 소요된다는 어마무시한 결과를 알 수 있습니다... 저도 솔직히 BFS가 이렇게 비효율적인지는 몰랐네요.


탐색의 좋고 나쁨을 평가하는 데에 네가지 요소가 있습니다. (1) 완결도(Completeness) (2) 시간복잡도 (3) 공간복잡도 (4) 최적도 (Optimality)


BFS 의 경우에는 최적도에 대한 분석이 좀 필요한데요, 먼저 최적도를 설명해야겠습니다. 최적도는 알고리즘이 찾아낸 solution path 가 다른 solution path 들과 비교했을 때 좀 더 적은 비용을 가지냐를 따집니다. 모든 edge 들의 비용이 1이라면 BFS 는 최적도를 만족한다 볼 수 있겠습니다. 하지만 edge 들이 각기 다른 비용을 가진다면? 예를 들어 깊이 1에 목표가 있는데 비용이 9999 입니다. 그런데 깊이 5에도 목표가 있고 비용이 5 인 경우를 생각해보세요. 5가 최소 비용인 경우가 존재하는데도 불쌍한 BFS 는 9999 비용의 경로를 반환할 것입니다. 이런 경우에는 최적도를 만족하지 않습니다.


다행히 이런 최적도 문제를 해결 할 수 있는 방법이 있습니다. 바로 아래 설명할 Uniform Cost Search입니다. 


Uniform Cost Search (단일 비용 탐색)


기본적으로 탐색 원리는 BFS 와 정말 같습니다. 그런데 큐에서 어떤 상태 공간을 dequeue 하는지가 달라요. UCS 는 큐에 있는 상태공간 중에 가장 적은 비용의 것을 dequeue 합니다. 구현할 때는 priority queue를 사용하고요. 결국 도달하는데 가장 적은 비용이 드는 목표 지점을 찾아주겠죠.


BFS 와 같은 원리로 탐색하기 때문에 완결도를 만족하고요, 애초에 BFS 의 최적도 문제를 해결하기 위해 고안 된 알고리즘이기 때문에 최적도도 만족합니다. 시간 복잡도는 O(b^C/e) 로 표현하는데요, 경로의 비용에 초점을 맞추다보니 표현 방법이 좀 독특하죠. C는 목표 지점에 도달하기 위한 최소 비용, e는 edge 가 가질 수 있는 최소 비용입니다. 공간 복잡도도 동일합니다. 


예제를 보시려면 클릭하세요


DFS

이제 깊이 우선 탐색을 알아봅니다. 미리 말하자면, 위에서 설명한 알고리즘과 비교했을 때 DFS가 우위에 있는 것은 공간 복잡도입니다.


먼저 깊이 우선 탐색의 개념을 되짚어봅시다. 


"들어왔을 때는 마음대로였겠지만, 나갈 때는 아니란다." 제가 DFS 를 설명할 때 항상 인용하는 구절입니다. DFS 는 한 곳에 들어가면 그 곳만을 계속 파야합니다. 위 그림을 가지고 설명하면, 파란색 줄기를 쭉쭉쭉 파고 들어갑니다. 그러다가 그 줄기 안에 있는 모든 노드가 탐색 완료 되었으면 다시 집으로 돌아가다가 다른 줄기 (빨간색) 을 발견하고 거기를 또 다시 팝니다. 빨간색 줄기도 완료되면 집으로 돌아가다가 다시 초록색 줄기를 발견해서 계속 파고... 이게 무한 반복됩니다. 


스택 자료 구조를 이용해서 구현이 가능하고요, 아래 의사 코드를 보겠습니다. 


function DFS(start-state){

    stack.push(start-state)

    while (stack is NOT empty){

        state = stack.pop()

        if (state == goal) then SUCCESS

        for s in successors: s.prev = state

        stack.push(successors of state)

    }



DFS 의 공간 복잡도는 O(bm) 입니다. (m 은 그래프의 깊이를 의미) 시작 노드로 부터 가장자리 노드까지의 만큼의 공간만 스택에 머무른다는 것을 생각해보세요. 


하지만 불행하게도 DFS에는 치명적인 단점이 하나 있습니다. 조건이 붙는데요, 바로 트리가 무한할 때 입니다. DFS 는 한 줄기 끝까지 파기 전에는 다른 줄기로 이동할 수 없는데... 그 "끝"이 없으니 무한정 탐색을 하는 거죠. 결국 이런 경우에는 완결도를 충족하지 못하게 됩니다. 대신 무한한 트리가 아니라 끝이 있는 트리에서는 O(b^m) 의 시간 복잡도를 가집니다.


Iterative Deepening


Iterative Deepening 은 한국말로 반복적 깊이증가라고 하는데요, 이름이 알고리즘의 원리를 대략 설명해줍니다. DFS 에 깊이 제한을 둔다는 생각에서 출발합니다. 첫번째 단계에서는 깊이 1까지만 DFS, 두번째 단계에서는 깊이 2까지 DFS, 세번째 단계는 깊이 3까지, ... 무한 반복한다는 원리죠. 결국 반복적으로 DFS 를 하긴 하는데, 탐색하는 깊이 제한을 두고, 깊이를 계속 증가시키는 겁니다. 



BFS 와 DFS 를 짬뽕시켰다고 할까요? 탐색은 BFS 인데 메모리 구조는 DFS 의 스택을 이용하는 거죠. 덕분에 완결도도 충족하면서 (BFS 장점), 공간복잡도도 괜찮은 성능(DFS 장점)을 보여줍니다. 시간 복잡도는 O(b^d), 공간 복잡도는 O(bd) 입니다. 이 때문에 무정보탐색에서 주로 Iterative Deepening 을 이용하는 게 좋습니다.


예제를 보시려면 클릭하세요.



** 시험 공부하면서 끄적여본 학부생의 부족한 설명 읽어주셔서 감사합니다. feedback 이나 질문 댓글 환영합니다! 

** 참고 자료: Artificial Intelligence: A Modern Approach (3rd Edition) 3rd Edition (Russell & Norvig) / (강의) CS540: Uninformed Search (Zhu)