[컴퓨터과학과] 2019년 2학기 인공지능 중간시험과제물 공통(상태공간 탐색, A* 알고리즘)

목차

A 지점에서 출발하여 H 지점으로 가는 경로를 찾는 문제를 해결하려고 한다. 각 지점 사이의 거리(단위는 km)와 그 구간의 주행속도(단위는 km/h, 양 방향이 동일하다고 가정함)는 [그림1]과 같고, 각 지점으로부터 H까지의 직선거리는 [그림2]와 같다.

(가) 상태공간 탐색으로 이 문제를 풀이하는 방법의 개념을 설명하라.
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하려고 한다. [그림2]를 예측 비용을 구하는데 활용하여 평가함수를 정의하고, 이에 따른 탐색 트리를 보여라. 각 탐색 트리의 각각의 노드에는 확장 순번과 평가함수 값을 표시하라.
(다) A* 알고리즘을 이용하여 최소시간 경로를 구하려고 한다. 예측 비용은 평균시속 17km/h를 가정하여 [그림2]를 바탕으로 정하고, 이에 따라 평가함수를 정의하라. 이에 따른 탐색 트리를 (나)와 동일한 방법으로 보여라.



- 목 차 -

Ⅰ. 상태공간 탐색으로 이 문제를 풀이하는 방법의 개념을 설명하라.
1. 상태 공간 탐색의 개념
2. 에이 스타 알고리즘 문제 풀이를 위한 개념

Ⅱ. A* 알고리즘을 이용하여 최단길이 경로를 구하려고 한다. [그림2]를 예측 비용을 구하는데 활용하여 평가함수를 정의하고, 이에 따른 탐색 트리를 보여라. 각 탐색 트리의 각각의 노드에는 확장 순번과 평가함수 값을 표시하라.

Ⅲ. A* 알고리즘을 이용하여 최소시간 경로를 구하려고 한다. 예측 비용은 평균시속 17km/h를 가정하여 [그림2]를 바탕으로 정하고, 이에 따라 평가함수를 정의하라. 이에 따른 탐색 트리를 (나)와 동일한 방법으로 보여라.

참고문헌

본문내용

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

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

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




- 중략 -

참고자료

· 없음