인공지능 AI- 2주차 (Search Part 2)

먼저 Breadth First Search에 대해서 알아보자. 

First Out First In

핵심은  Open List에 있는 젤 왼쪽꺼를 remove하고 remove한 children을 젤 오른쪽에 있다. 예로 들면 A를 remove 하면 A의 children인 D,E,G가 OpenList에 써진다. 

혹시나 ChildRen이 겹치면  G  G’ G’’ 이렇게 써진다

BFS 는 모든 연산자가 같은 cost일때 optimal하다. 

Time/Space complexity — size of tree 이다. Tree의 깊이 이다.

이고  d는 Tree의 깊이다. b는 leaf node이다.

그래서 Breadth First Search는 얇은 문제에 좋다.

8-puzzle 에 BFS를 도입하면 이런 flow가 생긴다 . Breadth 답게 너비위주로 간다.

Depth First Search는 Last in First Out

BFS와 차이는 children들이 다 왼쪽에 나오는 것이다.

Depth First Search는 장점으로는 더 적은 메모리, 더 적은 search space가 쓰인다. 그러나 depth bound(depth cutoff) 없이는 infinite하게 search 할수있다.

depth bound는 뭐 알아서 정해야한다.

DFS는 깊이처럼 아래로 쭉쭉 내려갔다. 없으면 다시 one level로 올라가서 찾고 한 단계식 올라가서 찾는다.

지금까지 본  

     Basic Search의 Blind Search이다.

이제부터 볼껀 Heuristically Informed Search이다.  -> 스스로 발견하게 하는 Search라고 생각하면 된다.

Heuristics이 쓰이는 경우는 2가지이다.  

1. 정확한 해답이 없는 경우

2. State Space Growth가 엄청 커질때

Heuristically Informed Methods은 식으로 나타낼수있다. heuristic function이라고 할수있따.

h(n) -  estimated cost of minimal cost path fro n to goal state   - cost of the future search

g(n) - past search g 는 무얼 의미할까 -> goal 인거같다.

그래서 function은 f(n)=g(n)  이 경우는 Branch and Bound

                            f(n)=h(n)  greedy algorithm, Hillclimbing, Best First가 있따.

                            f(n)=g(n)+h(n)  A*  여기서 볼수 있듯이 이게 젤 좋다

이건 f(n) = h(n)에 관한  문제이다

원리는 간단하다 . sort the first’s children 이다.

 

단점은 may stuck at local maximum Does not guarantee shortest path

8-puzzle에서보자면 일단 h(n) 미래를 예측하는 함수는 여기서는 number of tiles out of place. 순서가 맞지 않는 타일의 개수로 보면 된다.

문제는 local optimal로만 될수 있다는 것이다.

다른 Heuristic Search로는 Best first search가 있다.

Hill Climbing 은 current level에 있는 것끼리 sort를 하지만 Best Fit Search는 전체 node끼리 한다.

이제 Branch and Bound를 봐보자 이건 g(n) 으로 본다고 하면 된다.

제일 좋은 Algorithm이다 h(n)+g(n) 를 더하기 떄문이다.

중요한건 under estimated이어야 한다고 한다.

과거 기록인 h(n)만 고려하면 위에서 보듯이 D 가 C보다 좋지만 C로 이어질수있다.   h(n)만 따지면 안된다

overestimated도 좋지 않다.  

젤 아래꺼는 f(N) 이 증가하지 않는다 그래서 오른쪽 그림처럼 한 level 더 올라가서 다시 시작한다.

허용성이다.

간단하게 under estimated되야한다.

h(n)=0 이면 g(n) 만 있으므로 BFS이다.

h*=h optimal path 이다.

h(goal state)= 0 이다.

over estimated 되면 path가 되지않는다.

그래서 actual g(n)* 보다 g(n)이 더 크다고 한다.

g(n)> *g(n)

h2 is more accurate than h1 라서 h2를 고른다. 

f(n) 은 줄어들지 알고 증가하게 생각해야한다고 한다.

h(S1) <= cost(S1,Sg):

이런 문제를 보면 b에 갈 경우의 h(n) history는 보면서 생각해야한다. f(n)=g(n)+h(n)이기 때문이다.   왼쪽이 g(n) 이고 오른쪽이 h(n)이다.

게임 Search Algorithm은 이걸 쓴다고 한다.

아래서부터 시작하는데 leaf n허용성이다ode에서 먼저 제일 작은걸 찾는다

거기서 젤 큰걸 찾는다

위는 max

아래는 min

오른쪽 그림도 보면 -5까지만 찾고 올라가는 이유는 결국 -5보다 작아도 3이더 크기 때문이고 -5 보다 커도 올라가는건 minimizing 하는 -5이기 때문이다.