정답
노드 n에 대해 g(n)=2, h(n)=0이며, 목표노드에서 h=0, f=2이다.
출제 의도
이 문제는 A* 알고리즘의 탐색 절차를 3-퍼즐 문제에 적용하여, 경로 비용 g(n), 휴리스틱 함수 h(n), 평가함수 f(n)=g(n)+h(n)의 의미를 정확히 이해하고 계산할 수 있는지를 평가한다.
풀이 과정
문제의 3-퍼즐은 2×2 격자에서 빈 공간으로 숫자 조각을 상·하·좌·우로 이동시켜 시작노드에서 목표노드로 도달하는 문제이다. A* 알고리즘에서는 시작노드로부터의 실제 이동 횟수를 g(n), 목표노드까지의 추정 비용을 h(n)으로 정의한다.
제시된 노드 n의 상태는 목표노드와 동일한 상태이다. 따라서 이 노드에서 목표노드까지 추가로 필요한 이동 횟수는 없다.
$$ h(n) = 0 $$
시작노드에서 노드 n(목표 상태)에 도달하기까지 필요한 최소 이동 횟수는 두 번이다. 즉, 한 번의 이동마다 비용이 1이므로
$$ g(n) = 2 $$
평가함수는
$$ f(n) = g(n) + h(n) $$
이므로 목표노드에서의 값은
$$ f(\text{목표노드}) = 2 + 0 = 2 $$
따라서 요구한 값은 g(n)=2, h(n)=0이며, 목표노드의 h 값은 0, f 값은 2이다.