Local search, Hill-climbing search

Local search

오직 현재 state 만을 저장하여 검색하는 탐색법입니다. 과거나 미래의 state sequence 를 저장하지 않기 때문에 메모리를 적게 사용합니다.

Loacl search 는 goal 까지의 path 를 알아내는 것이 불가능합니다. 따라서 8-puzzle 처럼 답은 쉽지만 과정을 알아내는 문제에는 적합하지 않고, N-queen 문제처럼 과정은 몰라도 되고 답 자체를 알아내는 것에 집중되는 문제나 최적화 문제에 적합합니다.

 

Hill-climbing search

function HILL-CLIMBING(problem) returns a state that is a local maximum

current ← MAKE-NODE(problem.INITIAL-STATE)

loop do

neighbor ← a highest-valued successor of current // successor 중 가장 좋은 것을 neighbor 로 지정

if neighbor.VALUE <= current.VALUE then return current.STATE // 현재 내가 neighbor 보다 좋으면 그것이 정답

current ← neighbor // 현재 나보다 neighbor 가 더 좋으면 neighbor 로 이동

 

8-queen 문제

각 컬럼의 임의의 위치에 미리 퀸을 배치하고 시작하는 방식인 Complete state formulation 으로 진행합니다.

따라서 총 가능한 successor의 수는 56개 입니다.

 

heuristic cost function h는 해당 위치로 퀸을 옮겼을 때 공격가능한 퀸의 수 입니다.