Local Search, Hill-Climbing Search

In this Chapter 

- 이전까지는, fully observable, deterministic, known 한 문제들을 다루었다.

- 그리고 solution 은 action 의 연속으로 이루어졌다.

 

이번 chapter 에서 배울 것은 다음과 같다.

 

- Local Search

• initial state 부터 경로를 탐색하는 것이 아니라, 현재 states 를 평가하고 수정하는 것이다.
• 즉, 과정이 존재하는 것이 아니라 현재 state 만 존재한다.
• path cost 가 아니라, goal state 를 찾는 것이 중요하다.

- Nondeterministic and partially observable worlds

• Nondeterministic 이란 action 을 취했을 때 다음 state 가 하나로 정해지지 않는다는 것이다.
• patially observable 이란 현재 나의 state 를 정확히 알지 못한다는 것이다. 또한 다음 state 도 마찬가지다.
• solution 은 더 이상 action sequences 가 아니다.
• contingency plans (위기 대응 계획) 이 필요하다.

 

 

Local Search

- 오직 현재 state 만을 저장하여 검색하는 탐색법이다.

- 과거나 미래의 state quence 를 저장하지 않기 때문에 메모리를 적게 사용한다.

- goal 까지의 path 를 아는 데는 관심이 없다.

- goal 을 찾는 것이 매우 어렵기 때문에, 8-puzzle 처럼 goal 을 찾기 쉬운 문제가 아니라 n-queen 처럼 답 자체를 알아내는 것이 중요한 문제나 최적화 문제에 적합하다.

 

 

 

Hill-Climbing Search

- successor 중 가장 좋은 것을 neighbor 로 지정한다.

- 만약 현재 내 state 가 neighbor 보다 좋다면, 현재 state 가 goal 이 될 것이다.

- 나보다 neighbor 이 좋다면, 그곳으로 이동한다.

- 위 과정을 반복하는 것으로, 주변에서 제일 좋은 곳으로 이동하고 더 좋은 곳이 없다면 종료되는 알고리즘이다.

 

A Hill-Climbing Search Example

- 8-queen 문제

- Complete state formulation 으로 시작한다. -> 미리 8개의 퀸을 다 배치하고 시작하는 방식

- 각 state 는 8 x 7 = 56 개의 successor 를 가진다.

- 하나의 퀸이 갈 수 있는 곳은 같은 column 내의 7칸이고, 총 8개의 퀸이 있으므로 56개의 successor 이 존재한다.

- heuristic cost function h 는 해당 위치로 퀸을 옮겼을 때 공격가능한 퀸의 수이다. -> GOAL 에선 0이다.

위의 (a) 상태에서 hill-climbing search 를 진행해주면 오른쪽 사진 h = 1에 도달한다.

이는 아주 빠르게 효과적인 해에 도달할 수 있지만,

h = 0 이 아니기 때문에 완전히 최적화된 해 ( GOAL) 은 아니라는 뜻이다.