깊이 우선 탐색 Depth-First Search(DFS)

Depth-First Search

---

Strategy: 더 밑으로 갈 수 없을때까지 혹장한다.

Implementation: Fringe는 Stack(LIFO-Last in Last Out)로 구현한다.

처음 시작하면 S를 확장시켜 d, e, p 순으로 프린지에 넣는다.

다시 d를 확장시켜 b, c, e를 프린지에 넣고 b를 확장시켜 a를 프린지에 넣는다. a를 확장시키려 하였으나 더 이상 확장시킬 수 없다.

이때 길이 막혔으므로 부모노드로 돌아가는 백트래킹(Backtracking) 과정을 밟는다. 그럼 b로 올라가며 b에서도 확장시킬 자식 노드가 없어 다시 백트래킹 과정을 밟는다. d까지 올라와서 보니 c, e가 있으므로 c를 확장시켜 다시 탐색을 시도한다. 

S->d->b->a->Backtracking->c->a 순이다.

이러한 과정을 Goal에 들어갈때까지 반복한다.

Depth-First Search Properties

---

- 전체 트리를 탐색할 수 있다.

- 탐색시간: [각주:1]

- 프린지 용량은 얼만큼 필요한가: O(bm)

- complete 한가? 사이클이 없는 경우에 해를 찾는다.

- optimal 한가? 가장 먼저 찾은 것이 해 이므로 optimal은 아니다. 위 그림같은 상황에서는 중간쯤에 있는 Red goal이 가장 짧은 거리이나, DFS로 검색시에는 중간쯤의 Red goal보다 왼쪽아래에 있는 Red goal을 해로 얻게된다. 해는 찾았으나 최적의 해는 아닌 것이다.

1. Big O 표기법 [본문으로]