Admissible Heuristics from Subproblems, Pattern Databases

Admissible Heuristics from Subproblems

- 8-puzzle 문제의 subproblem 이다.

- 1~8까지 모두 고려하는 게 아니라, 1~4까지만 고려하면 되는 문제로 원래 문제의 subproblem 이다.

- 기존의 h1, h2 는 계산이 쉬웠다. 그러나 Subproblem 은 그에 비해 바로 찾는 것이 어렵다.

- Subproblem 의 optimal solution 비용은 항상 original problem 보다 작으므로, admissible heuristic 하다.

 

 

 

Pattern Databases

- 모든 가능한 subproblem 의 state 에 대한 cost 를 저장해두는 방식이다.

• Goal state 에서부터 무작위로 start 하여, 만나는 node들의 cost 들을 저장해둔다. -> b^(2/d)

- 여러 subproblem 을 사용하는 것도 가능하다.

- 예를 들어, 1~4 문제와 5~8 문제로 쪼개어 두 개의 subproblem 으로 만들고, 

두 heuristic 중 더 큰 값을 이용하여 정답을 찾아나가는 방식을 사용할 수 있다.

• 15-puzzle 문제의 subproblem heuristic 은 맨해튼 거리 heuristic (h2) 보다 1000배나 효율적이고 빠르다.

- 두 heuristic 의 h(n) 값을 단순 덧셈한다면 어떨까?

• 안된다. 왜냐하면, 각 heuristic 은 중복된 움직임이 있을 것이다. 
• 따라서, 더한다면 admissibility 를 잃게 된다.
• 그렇다면, 1~4문제에서는 1~4번 타일이 움직인 횟수만 count 하고, 5~8 문제에서는 5~8번 타일이 움직인 횟수만 count 한다면, 그 두 subproblem h(n) 값을 더했을 때는 admissible 할 것이다.

 

 

Learning Heuristics from Experience

- 많은 n-puzzle 문제를 풀어봄으로써 예측하는 함수 h(n) 을 학습시킨다. 

- 즉, Learning 은 실제 cost 가 아닌 적절한 cost 를 예측하는 것이다.

 

- Pattern DB 와 다른 점

• Pattern DB 는 Subproblem 을 사용하지만, Learning 은 Complete problem 을 쓴다.
• Pattern DB 는 실제 cost 를 모두 저장하여 활용하지만, Learning 은 함수 f 에 의해 생성된 예측값 을 활용한다.

- 함수

• argument : state 의 feature 를 인자로 받는다.
  • ex ) 잘못된 위치에 있는 타일의 수 , goal 에 인접하지 않은 것들 중 인접한 타일 쌍의 수
• value : 예측한 path cost 를 출력할 것이다.