탐색 - 직접적 기법(무작위 탐색, 깊이우선탐색, 너비우선탐색)

인공 지능적 문제해결에서 탐색은 주요한 수단임.

문제 해결 기법에는 크게 2가지가 존재. (직접적, 경험적)

1. 직접적 기법 

- 문제의 해를 찾기위한 순차적 수행 프로그램 / 알고리즘 프로그램

- 프로그래머가 문제 해결을 위한 알고리즘이 고안함.

- ex) 하노이탑 문제

---

**인공지능적 해법 : 문제 상태와 요구하는 목표 상태만으로 컴퓨터가 문제해결 할 수 있도록 하는 해법 

- ex) 경로 발견 문제(8-puzzle), 게임 문제(chess/바둑), 제약조건 만족 문제(8-queen)

//선택의 갈림길에서 지능적 판단이 필요한 해법!
//지능적 기계보다 인간의 지능이 어느정도 개입하는 시스템 개발이 인공지능에 보다 현실적임! 

즉, 인공지능은 컴퓨터가 스스로 '탐색'을 진행하지만, 탐색의 방식은 프로그래머가 결정!

**인공지능 탐색이 필요한 문제상황 : 1. 문제가 복잡해서 알고리즘이 없는 경우  2. 알고리즘은 있지만 시간복잡도가 너무 높은 경우(TSP)

---

탐색기법에서 경로 선택의 고려사항 

1. 해의 경로는 짧아야 한다.

2. 탐색의 소요 경비는 적어야 한다.

3. 해가 있다면 탐색으로 반드시 찾아야 한다.

---

탐색기법 

1. 무작위탐색(random search)

- 무작위로 경로 선택한다.

- 최악인 것 같지만, 탐색 영역이 작은 문제일 경우 유용하게 사용될 수 있다.
(ex. 이미 답이 많이 나온 문제의 경우, 무작위로 선정해도 괜찮음. 어렵게 탐색하지 않고, 빨리 다른  탐색 시도하면 되니까)

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

- 시작 노드부터 수직방향으로 점차 깊은 곳까지 목표노드를 찾아 탐색하는 기법

- 단말 노드까지 갔다가 목표노드가 아닐 경우 다시 위로 올라와서 다른 노드로 감(backtracking이 존재)

장점

- 저장공간의 수요가 비교적 적다. (큐에 넣을 경우) 

- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수도 있다. (너비탐색보다는) 

단점

- 해가 없는 경로에 깊이 빠질 우려가 있음. (수직방향으로만 내려다가보니까 해가 없지만 깊이 빠질 수도 있음.) 

- 해에 이르는 경로가 다수인 경우, 얻어진 해가 최단 경로가 된다는 보장이 없음. //최단경로보장X

평균 탐색 노드 수(가지 b개, 목표노드 깊이 d개)

- 목표노드가 최좌측 : d+1  //(1)
- 목표가 최우측 : 1+b+b^2+...+b^d = (b^d+1 - 1)/(b-1)  //(2)
- 평균 노드수 : { (1) + (2) } / 2

2. 너비우선탐색(BFS : Breadth-First-Search)

- 탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 가로방향으로 탐색을 진행하는 기법

장점

- 해에 이르는 경로가 다수인 경우에도 최단경로를 보장.

- 해가 존재하면 반드시 찾을 수 있음.

- 노드의 수가 적고 얕은 깊이일 수록 유리.

단점

- 노드의 수가 늘어나면 탐색시간이 비현실적임.

- 기억공간에 대한 요구가 과중됨. (노드가 많아지면 큐에 대기 노드들을 넣어줘야하니까)

평균 탐색 노드 수(가지 b개, 목표노드 깊이 d개)

- d 깊이 목표를 위한 평균 노드 수 = (1) + (2)
- (1) d-1깊이까지 총 노드수 :  1+b+b^2+...+b^d = (b^d - 1)/(b-1)
- (2) d 깊이에서의 노드 평균수 : (1 + b^d) / 2         //(최선+최악)/2

---

탐색의 방향

1. 전향추론 : 초기상태 -> 목표상태로 탐색

2. 후향추론 : 목표상태 -> 초기상태로 탐색

** 탐색의 방향은 복잡도에 따라 정할 수 있음.