Heuristic 과 Relaxed problem

Heuristic

 

8-퍼즐을 푸는데 보통 22 step 정도가 필요하며 branching factor 는 평균 3이 됩니다. 가운데에 있을 때는 상하좌우 다 갈 수 있지만 구석에 있을 때는 Action 의 방향에 제약이 생기기 때문입니다. tree search 의 경우 3 ^ 22 개의 노드를 방문해야하며 이는 10 ^ 10에 달하는 큰 수입니다.

그래프 서치에도 170,000개 정도 되며 15퍼즐만 되어도 10^13 개가 됩니다.

 

두 개의 Admissible heuristics 를 제시합니다.

• h1 = 잘못 위치된 타일의 수

• h2 = 잘못 위치된 타일의 위치와 정상 위치와의  맨해튼 거리의 합

위 사진에서 start state 의 h1 = 8, h2 = 18 입니다.

 

비교

IDS와 A*(h1), A*(h2) 를 비교해보겠습니다.

 

공정한 비교를 위해 solution depth 가 2, 4, 6, …, 24 인 문제를 각 100개씩 만들어 시뮬레이션하고, 그 평균값을 비교합니다.

 

IDS 탐색법은 depth 가 12 이상인 문제들부터는 시간이 너무 오래걸려 풀기 어려운 모습을 보입니다.

A* 끼리도 h2 휴리스틱을 쓴 탐색이 h1 보다 더 효율적인 모습을 보입니다.

 

h2 는 언제나 h1 보다 더 좋은 결과를 내놓으며 이를 h2가 h1을 dominate (지배)했다. 라고 말합니다.

즉, h2 는 절대 h1이 expand 한 노드 수보다 많은 노드 수를 expand 할 수 없다는 것을 말합니다.

 

증명

f(n) < C* 인 모든 노드는 expand 됩니다.

f(n) = g(n) + h(n) < C*

h(n) < C* - g(n)

h1 을 이용한 A* 는 h2 를 이용한 A*가 만들어낸 모든 노드를 만들어냅니다.

왜냐하면 h1(n) <= h2(n) < C* - g(n) 이기 때문입니다.

 

Relaxed(simplified) problem

위에서 정의했던 h1과 h2 는 heuristic 이지만 이것 자체가 원래 문제를 변형한 문제에서는 정답이 될 수 있습니다.

그러한 변형 문제를 Relaxed problem 이라고 합니다.

 

예를 들면

• h1  : 8 퍼즐 문제에서 타일을 뜯고, 겹치는 식으로 해서 아무데나로 바로바로 옮길 수 있는 변형문제

• h2 : 어느 방향으로나 빈칸인지 아닌지에 상관 없이 옮길 수 있는 변형문제

에서의 정답이 될 것입니다.

 

Relaxed problem 은 원래 문제의 state space 에 edge를 추가합니다. 여기서 edge 는 action을 의미합니다.

당연하게도 원래 문제는 Relaxed problem 보다 풀기 어렵기에 원래 문제의 정답은 Relaxed problem 의 정답이기도 합니다.

하지만 변형 문제는 좋은 action을 갖고 있기 때문에 더 좋은 solution 을 갖고 있으며 이는 원래 문제의 heuristic 으로 쓰일 수 있습니다.

 

이를 위해서는 문제 정의를 위한 formal language 언어가 필요합니다.

 

n-puzzle 문제의 경우

• 아래 조건을 만족시킨다면 타일은 위치 A에서 위치 B로 이동할 수 있습니다.

• A와 B는 가로나 세로로 인접해있습니다.

• B는 빈칸입니다.

• 3가지 relaxed problem 파생 가능

• B가 빈칸이 아니여도 인접하기만 하면 이동할 수 있습니다.   : h2

• B가 인접하지 않더라도 빈칸이기만 하면 이동할 수 있습니다. : h3

• B가 어떻든간에 무조건 이동할 수 있습니다.  : h1

 

단 Relaxed problem 이 원래 문제의 heuristic 이 되려면 그 문제가 굉장히 쉽고 빠르게 풀릴 수 있는 Relaxed problem 이여야합니다.

왜냐하면 heuristic 으로 쓰려고 푸는 문제가 오래걸려버리면 배 보다 배꼽이 더 커질 수 있기 때문입니다.