탐색 - 경험적기법(언덕등반기법, 최고우선탐색, 빔탐색, A알고리즘, A*알고리즘)

2. 휴리스틱 기법(경험적 기법) //인공지능 탐색 기법

- 논리적으로 혹은 수학적으로 증명할 수 없으나 경험이나 직관에 의해 해를 얻을 수 있으리라는 기대를 갖게 하는 어떤 근거에 의한 방법
// 즉, 증명 가능한 알고리즘이 아닌 직관에 의한

- 정의하기 힘든 문제 or 맹목적인 기법으로 풀기에는 비현실적인 문제

- 인간의 사고형태는 대부분 휴리스틱이다. 해법이 유일하지 않으며, 최적의 해를 보장할 수 없다.
//알고리즘이 아니기 때문에. 해를 구할 수 없으므로 해의 결정에 허용치를 부과하는 방법을 이용.

**평가함수 : 평가하고자 하는 노드에 대해 그의 유망성을 수치로 표현할 수 있게끔 하는 함수
//현재 노드가 가장 좋은 해결경로 상에 놓여있을 확률 or 현재노드 - 목표노드 사이의 거리 등 여러가지 개념의 의존하여 설정된다. 
ex. 8-puzzle에서 현재 판의 상황이 목표 상태 판과의 얼마나 유사한가를 나타내는 정도를 평가하는 수치를 설정하는 것 

1) 언덕등반기법 (hill-climbing)

- 평가함수를 사용하여 평가함수 값을 증가(감소)시키는 방향으로 나가는 탐색 전략.

- 깊이우선탐색기법(DFS)에 평가함수를 활용한 형태이다.

- 최단 경로의 대한 보장이 없고, 국부최대가 존재할 수 있다. 
//전체 탐색 공간에 대하여 다른 곳에 더 좋은 경로가 있는데, 한 곳에서만 최대인 곳을 찾는.. 극대값. 

- 과정 회복이 불가능하다.(backtracking하니까)

**저작권을 위해 참고한 수업 교재 첨부**

- 만약, 선택한 가지에서 점수가 모두 동점일 경우에는 선택할 경로가 없음. 랜덤 선택을 해야 함. 
=> 이를 보완하기 위해 최고우선탐색이 등장.

2) 최고우선탐색

- 모든 말단 노드를 대상으로 평가함 수값을 비교하는 방법

- 국부최대를 만나도 탐색이 계속된다. 

- 최적의 경로를 보장할 수 없으나 선택 안된 노드를 확장하여 더 나은 해를 발견할 수 있다.

- 너비우선탐색기법에 비해 탐색 비용이 절감된다.

**저작권을 위해 참고한 수업 교재 첨부**

- 고려해야 할 말단 노드 수가 증가한다는 단점이 생김
=> 이를 보완하기 위해 빔탐색 등장.

3) 빔탐색

- 최고우선기법에서 기억노드의 수를 제한하는 방법

- 기억공간이 축소되지만 너무 빠른 가지치기를 초래할 수 있음. (정답인데 가지 쳐버리는)

- 무작위로 생성한 상태들에서 자손 노드를 생성. 자손 노드 중 어느 하나가 목표 노드인 경우 해를 찾았다고 생각. 그렇지 않으면 k의 최선의 자손 노드를 선택하고 반복함. 가치없는 노드들은 빠르게 제거하여 가장 그럴싸한 노드로 이동하게 함.

4) A알고리즘

- 초기 노드에서 목표노 드까지의 최단경로. 임의의 노드 N의 평가함수를 정의한 것.

평가함수f(n) = g(N) + h*(N)
- g(N) : 초기 노드 ~ N 노드까지의 최단거리
- h(N) : N 노드 ~ 목표노드까지의 최단 거리
** h(N)은 해가 주어지지 않으면 알 수 없으므로, 추정치 h*(N)을 사용한다.

**저작권을 위해 참고한 수업 교재 첨부**

- 루트 노드를 초기 노드라고 가정할 때, 3가지의 경로 중 가장 큰 수(타일 수가 일치한 수)인 6을 선택.

- 가운데 노드를 N노드라 가정할 때, g(N) = 1. 

- 목표 노드와 똑같이 맞는 타일 수 8. h*(N) = 8 - 6 = 2.

- f(N) = 1 + 2 = 3. //가지 수 3. 

//***정확히 이해한 것인진 모르겠지만,,,,,,,,

A 알고리즘의 평가함수는 f(n) = g(n) + h(n)이다.
초기 노드 ~ n노드 까지를 g(n)
n노드 ~ 목표노드 까지를 h(n)으로 둘건데 목표노드까지 몇인지 모르니 낙관적으로 추정해보자! h*(n)이라하자. 
그래서 f(n) = g(n) + h*(n)

5) A*알고리즘

- A 알고리즘에서 모든 N에 대하여 h*(N) <= h(N)이 성립되도록 하면 최적의 경로를 보장한다.

- f(N) = g(N)으로 두면 (h*(N) = 0이 됨) 평가함수로 초기노드와의 거리만을 고려하여 낮은 깊이 노드를 우선 탐색함. 

- 너비우선탐색(BFS)가 최단 경로를 발견한다는 것을 입증함. //A*알고리즘 == BFS

- 평가함수 : BFS를 해나가는데 있어 각 노드에서 목표에 이르는 경로가 얼마나 짧은 것인가의 추정치를 이용한다.

- f(N) = g(N) + w(N) //w(N)은 목표상태와 틀린 위치의 타일의 개수

//***정확히 이해한 것인진 모르겠지만,,,,,,,,

A알고리즘과 A*알고리즘의 차이가 무엇이냐.

초기노드(g) / n노드 / 목표노드(h)가 있을 때,
g(n) = 1이고, h(n) = 3인 그림에 대하여 예시를 들자. 

그렇게 할 때! 

A 알고리즘은 낙관적으로 n노드부터 목표노드까지의 거리를 추정을 하는거지.  //"낙관적으로 목표타일의 개수 - 현재 개수만큼을 h*(n)으로 해보자 ~ "

A* 알고리즘은 내가 n~노드부터 목표노드까지 추정한 거리(h*(n)) <= 실제 n노드~목표노드 가 성립하도록 하면 최적의 경로를 갖을 수 있지.
y? 예를 들어 위에서 h(n) =3이니까 h*(n)은 1, 2, 3 중 1개로 추정하니 경우의 수를 좁힐 수 있고, 최적의 경로를 보장할 수 있음! 
                  A알고리즘처럼하면 1, 2, 3, 4, 5, 6 등등 낙관적으로 추정하게 되니까 최적의 경로는 보장을 못하지! 
그래서, f(n) = g(n) 평가함수를 초기노드와의 거리만 고려한다고 보면, 1이니까 낮은 깊이의 노드만 우선적으로 탐색하게 되어 너비탐색(BFS) 형태로 탐색함을 알 수 있음.

**이해가 틀린거라면.. 댓글로.. 정확한 설명을 부탁드립니다.. ㅎㅎ.....