Ⅰ. 상태공간 탐색으로 이 문제를 풀이하는 방법의 개념을 설명하라.

1. 상태 공간 탐색의 개념
상태 공간 탐색은 최적 목표를 달성하기 위한 중간 과정을 하나의 상태로 보고 각각 상태에서 최적의 선택을 하여 최종적으로 최소 비용으로 목표를 달성하는 일련의 연산자를 찾는 과정을 의미한다. 상태 공간 탐색 방식에 다익스트라 알고리즘, 에이스타 알고리즘 등 여러 알고리즘이 있다. 이 글에서 에이 스타 알고리즘을 토대로 방대한 상태 공간을 효율적으로 축소하여 문제를 해결한다.
에이스타 알고리즘은 탐색하지 않은 노드들 중에서 사전에 정해 놓은 함수의 값이 가장 최적인 정점을 선택하는 Best-First-Search 방식을 활용하고 있다. 각각의 노드에 대한 평가함수는 출발 노드에서 노드 k까지 도달하는데 드는 비용과 노드 K에서 목표 노드에 도달하는데 드는 비용의 합으로 나타낸다. 출발 노드에서 이동 가능한 노드들의 평가함수 값을 비교해 최소 비용으로 갈 수 있는 노드를 선택하고 탐색했으나 선택되지 않은 노드는 평가 대상에서 제외하는 탐색 과정을 목표 노드에 도달할 때까지 반복한다. 에이스타 알고리즘이 다른 상태 공간 알고리즘과 다르게 추정잔여거리를 사용하여 탐색을 하기 때문에 여타 알고리즘보다 탐색 단계가 줄어들어 탐색 시간이 현저히 줄어든다.

2. 에이 스타 알고리즘 문제 풀이를 위한 개념
에이스타 알고리즘의 노드에 대한 평가함수를 정의하면 다음과 같다. ‘출발노드로부터 목표 노드까지의 경로비용’을 f(k)이라고 하고 ‘출발노드로부터 노드 k까지의 경로비용’을 g(k)라고 하고 ‘노드 k로부터 목표노드까지의 예측 경로비용’을 h(k)라고 한다.




- 중략 -