인공지능 과제(20년 2학기)

목차

없음

본문내용

(가) A* 알고리즘의 주요 개념을 설명하라.

A*알고리즘은 BFS(Breadth First Search), DFS(Depth First Search)같은 searching algorithm중에 하나이다.
A*알고리즘은 그 중에 heuristic한 방법을 이용해서 좀 더 빠르게 search를 진행하고자 하는 알고리즘이다.
A* 알고리즘은 현재까지 계산을 한 상태의 노드의 내력 함수와 목적점에 이르는 잔여 비용의 추정치를 향한 수치를 기준 삼아서 해당 노드의 선택 여부를 결정하는 알고리즘이라고도 정의할 수 있다.
A*알고리즘이 주로 작동하는 형태는 현재 언급하고자 하는 싸이클을 지니고 있다. 출발점(출발노드)에서 이동할 수 있는 노드를 탐색한 후 그 중 이동할 수 있는 노드의 평가함수 값을 구한 후 값이 가장 낮은 노드를 open 노드에 추가하고 탐색 대상으로는 선정되었지만 평가함수 값으로는 선정되지 않은 노드를 closed list에 추가한다.
이후 closed list에 추가된 노드들은 재확인할 필요성이 없고 다시 open노드에 추가된 노드를 기준으로 이동 가능한 노드를 위의 싸이클처럼 반복하여 최단경로를 구하면 된다.

(나) 이동 횟수를 최소화하여 <그림 1>의 문제를 풀이하기 위해 문제를 표현하고, A* 알고리즘에 적용할 평가함수를 정의하라.

A* 알고리즘에 적용할 평가함수는 휴리스틱(heuristic)이다. 휴리스틱(heuristic) 평가함수는 “현재 노드에서 목표 노드까지 가는 최단 경로의 비용을 추정하는 것”으로 정의한다. 여기서 평가함수 f(N)은 g(N)과 h(N)의 합계이며, g(N)은 초기 노드에서 현재 노드까지의 실제 최단거리로 비용을 의미한다. h(N)의 합계 이며, g(N)은 초기 노드에서 현재 노드까지의 실제 최단거리로 비용을 의미한다.
h(N)은 아직 탐색이 이루어지지 않아서 알 수 없는 상태이나 현재 노드에서부터 목표 노드까지로 가는 최단거리(비용)의 추정치이다.

참고 자료

없음