인공지능 3. 맹목적 탐색 알고리즘
깊이, 넓이 우선 탐색이 무엇인가?
그 전에, 그래프 탐색을 어떻게 하면 좋을까? 우선, 시작 노드가 있어야 한다. 시작 노드와 연결된 주변 노드들을 하나씩 확인해가면서 목표 노드를 만났는지 체크한다. 주변 노드를 탐색하는데 한 depth씩 넓게 보면 넓이 우선 탐색, 일단 한 경로를 끝까지 파고 들면 깊이 우선 탐색이다.
알고리즘으로 만들려면, 위 방법을 일반화해야 한다. open 공간과 close 공간 두개를 정의하자. open 공간에는 앞으로 탐색해야 할 노드를 넣고, close 공간엔 탐색이 완료된 노드를 넣는다. 다음단계가 그래프 탐색을 일반화한 과정이다.
- 시작 노드를 open 공간에 넣는다.
- 다음 과정을 open 공간이 empty 될 때까지 반복한다.
- open 공간에서 노드를 하나 꺼낸다. 이를 \(p\)라고 하자.
- \(p\)가 목표 노드라면 종료한다.
- 목표 노드가 아니라면, \(p\)를 close 공간에 넣는다.
- 이후 \(p\) 노드가 (인접한 노드 \(\cap\) close 공간에 없는 노드) 조건을 만족하는 모든 노드를 open 공간에 추가한다.
위 단계에서 정하지 않은 것이 있다. open 공간에서 노드를 어떤 순서대로 꺼내는가? 마지막에 넣은 노드를 가장 빨리 꺼내면 깊이 우선 탐색이 된다. 이는 Stack과 같다. 마지막에 넣은 노드를 가장 마지막에 꺼내면 넓이 우선 탐색이 된다. 이는 Queue와 같다. open 공간의 자료구조만 다르게 하면, 다른 알고리즘이 된다. 그렇다면, DFS를 쓰기 좋은 상황과 BFS를 쓰기 좋은 상황은 어떤게 있을까?
DFS는 메모리 효율이 BFS보다 좋다. 한 깊이씩 모두 들여다봤을 때 탐색이 실패했다면, 그 경로는 기억하지 않아도 되기 때문이다. 다만 DFS가 찾은 경로가 최단 경로라는 보장은 없다.
BFS는 메모리 효율이 DFS보다 떨어진다. 한 깊이의 모든 노드를 전부 기억해야 하기 때문이다. 하지만 BFS가 찾은 경로는 최단 경로임이 보장된다. 같은 depth에서 모든 노드를 차근차근 확인하기 때문에, 가장 최초에 찾은 답이 가장 작은 depth가 될 수 밖에 없다.
\[\text{메모리 효율: ~~DFS > BFS}\] \[\text{최단 경로 보장: ~ DFS < BFS}\]균일 비용 탐색은 무엇인가?
만약 노드와 노드 사이 경로의 비용이 추가된다면? open 공간에서 노드를 꺼낼 때 경로 비용이 가장 작은 노드부터 꺼내는게 합리적이다. 경로 비용을 어떻게 기억하는가? 최단 Distance Table을 하나 만들어 사용한다. 즉, 과정은 다음과 같다.
- 시작 노드를 open 공간에 넣는다.
- 다음 과정을 open 공간이 empty 될 때까지 반복한다.
- open 공간에서 최단 거리가 가장 짧은 노드를 꺼낸다. 이를 \(p\)라고 하자.
- \(p\)를 close 공간에 넣는다.
- \(p\)와 인접한 노드 \(i\)에 대해 다음 과정을 수행한다.
- \(i\)가 close 노드에 있거나, \(p = i\)면 무시한다.
- 최단 거리 Table을 \(T\), \(p\to i\) 엣지 Weight를 \(e\)라고 하자. \(T[i]\)를 업데이트한다.
- \(T[i] = \text{min}(T[i], T[p]+e)\)
새롭게 꺼낸 노드를 거쳐서 가는 길이 더 짧다면 그 경로를 취하는 것.
- open 공간에 추가한다.
균일 비용 탐색은 답을 잘 찾아주지만, 문제가 존재한다.
- 시작 노드로부터 모든 노드에 대한 답을 찾는다. 이것은 장점이 될 수도, 단점이 될 수도 있다.
- 만약 비용이 같다면, 어떤 노드를 선택하는게 더 좋은 결과를 낼 수 있을까?
반복적 깊이 심화 탐색은 무엇인가?
DFS는 메모리 효율은 좋지만, 최적해를 찾아주지 못한다. BFS는 메모리 효율이 좋지 않지만, 최적해를 찾아준다. 이를 합쳐서 장점만 취할 수 있을까?
반복적 깊이 심화 탐색의 아이디어는, 깊이 제한을 1씩 늘려가면서 DFS를 반복하는 것이다. 예를들어, 처음엔 (깊이 = 1)에서 DFS를 돌려본다. 해를 못찾으면, 다음엔 (깊이 = 2)에서 DFS를 돌려본다. 이 과정을 해를 찾을 때까지 반복한다. DFS를 사용하니 메모리 공간은 절약되고, 낮은 깊이부터 모든 노드를 탐색하니 최적해까지 찾을 수 있다.
단점으론, DFS를 여러번 반복하므로 깊이 제한이 얕은 곳은 계속 중복으로 탐색하게 되는 문제점이 있다. 따라서 BFS보다 시간 효율은 더 떨어진다. 얼마나 차이날까? 시뮬레이션을 돌려봤더니 BFS 대비 11%정도 더 걸린다고 한다.
양방향 탐색은 무엇인가?
아이디어는, 시작 노드와 목표 노드에서 동시에 BFS를 탐색해서 중간에 만나면 탐색을 종료하는 것이다. 각각 따로 탐색하면 되니 병렬 프로그래밍을 적용할 수 있어 시간 절약이 가능하다. 또, BFS는 깊이가 깊어질 수록 기억할 노드가 기하급수적으로 늘어나는데, 깊이를 절반만 확장해도 목표를 찾을 수 있으니 메모리도 절약된다.
그러면, BFS 안써도 항상 양방향 탐색 쓰는게 좋지 않냐? 그렇진 않다. 양방향 탐색을 사용하기 위한 조건이 존재한다. 일단 목표 노드가 명확히 한 지점이어야 한다. 만약 목표가 100점 이상인 상태 찾기와 같다면, 목표 상태는 하나가 아니라 무수히 많을 수 있다. 또, 중간에 만났는지 체크하기 위해 동기화 과정이 필요하다. 구현도 복잡하고 오버헤드도 존재한다. 또, 연산자 역변환이 정의 가능해야 한다.
그냥 반복적 깊이 심화 탐색 쓰자 ㅋㅋ 조건에 맞고, 속도를 챙겨야 한다면 양방향 탐색이 더 좋을 수 있음! \(O(b^d) ~~\text{vs}~~ O(b^{d/2})\)
만약 깊이 또는 비용이 같다면, 어떤 노드를 선택하는게 더 좋은 결과인가?
어떤 상태를 선택하는게 더 좋은지 판단하기 위해서 평가 함수 (evaluation function) 를 도입한다. 가중치는 100% 정확하지 않고, 인간의 구현에 의존한다. 따라서 heuristic하다. 평가 함수를 사용하는 탐색을 경험적 탐색 (Informed Search) 으로 분류한다.
예를들어, 위와 같은 상황에서 어느 쪽을 선택하는게 더 좋을 것 같은가? 오른쪽을 선택하도록 하는게 더 좋을 것 같다. 판단 기준이 무엇인가? 목적지와의 거리가 더 가깝기 때문이다. 즉, 미로에서 평가 함수를 현재 위치와 목적지 까지의 맨해튼 거리로 선택하면 꽤 괜찮을 것 같다.
다른 예시로 8-Puzzle의 경우, 목표 상태와 현재 상태를 비교해서 맞는 퍼즐의 개수를 평가 함수로 사용하면 꽤 괜찮을 것 같다.
이렇듯, 평가 함수는 누구나 납득할만한 것 (admissible) 이어야 하고, 일관성이 있어야 한다. 납득 가능하다는 것은, 휴리스틱을 실제 비용보다 과대평가 하면 안된다는 뜻이다.
맨해튼 거리가 무엇인가?
맨해튼 거리는 두 점 \((x_{1}, y_{1})\)와 \((x_{2}, y_{2})\)가 있을 때 다음과 같이 정의한다.
\[d=\lvert x_{2}-x_{1} \rvert + \lvert y_{2}-y_{1} \rvert\]기존의 거리 계산법
\(d=\sqrt{ (x_{2}-x_{1})^2 + (y_{2}-y_{1})^2 }\) 은 계산 비용이 높다. 따라서 정확한 거리가 필요 없다면, 맨해튼 거리를 사용하는게 꿀팁이다.