[2022년 2학기 방송통신대 인공지능 과제] 상태공간 탐색에 의한 문제풀이 방식에 대한 다음 질문에 답하라. (가) 맹목적 탐색과 경험적 탐색의 개념을 설명하라. A star 알고리즘을 이용하여 다음 미로의 입구((0, 0) 위치)에서 출발하여 출구((4, 4) 위치)로 나오는 이동 거리가 가장 짧은 경로를 탐색하려고 한다.

과제정보

학과	컴퓨터과학과	학년	4학년
과목명	인공지능	자료	6건
공통	(1) (10점) 상태공간 탐색에 의한 문제풀이 방식에 대한 다음 질문에 답하라. (가) 맹목적 탐색과 경험적 탐색의 개념을 설명하라. (나) 탐색 알고리즘에서 고려할 수 있는 경로의 비용 및 평가함수에 대하여 설명하라. (2) (20점)... 더보기 (1) (10점) 상태공간 탐색에 의한 문제풀이 방식에 대한 다음 질문에 답하라. (가) 맹목적 탐색과 경험적 탐색의 개념을 설명하라. (나) 탐색 알고리즘에서 고려할 수 있는 경로의 비용 및 평가함수에 대하여 설명하라. (2) (20점) A* 알고리즘을 이용하여 다음 미로의 입구(●, (0, 0) 위치)에서 출발하여 출구(▲, (4, 4) 위치)로 나오는 이동 거리가 가장 짧은 경로를 탐색하려고 한다. 이동은 상, 하, 좌, 우의 방향으로 1칸씩 할 수 있다고 가정한다. (가) 이 문제를 해결하기 위한 평가함수를 정의하라. (나) 이 문제에 대한 탐색트리 및 그 결과에 해당되는 이동 경로를 구하라. 탐색 트리의 각 노드에는 확장되는 순번과 평가함수 값을 표시하라(강의자료 32쪽 참고). 접기

소개글

직접 작성한 내용으로 그대로 사용하셔도 됩니다.

목차

(1) 상태공간 탐색에 의한 문제풀이 방식에 대한 다음 질문에 답하라. (10점)
(가) 맹목적 탐색과 경험적 탐색의 개념을 설명하라.
(나) 탐색 알고리즘에서 고려할 수 있는 경로의 비용 및 평가함수에 대하여 설명하라.

2) A* 알고리즘을 이용하여 다음 미로의 입구(●, (0, 0) 위치)에서 출발하여 출구(▲, (4, 4) 위치)로 나오는 이동 거리가 가장 짧은 경로를 탐색하려고 한다. 이동은 상, 하, 좌, 우의 방향으로 1칸씩 할 수 있다고 가정한다. (20점)
(가) 이 문제를 해결하기 위한 평가함수를 정의하라.
(나) 이 문제에 대한 탐색트리 및 그 결과에 해당되는 이동 경로를 구하라. 탐색 트리의 각 노드에는 확장되는 순번과 평가함수 값을 표시하라(강의자료 32쪽 참고).

본문내용

(2) (20점)
A* 알고리즘을 이용하여 다음 미로의 입구(●, (0, 0) 위치)에서 출발하여 출구(▲, (4, 4) 위치)로 나오는 이동 거리가 가장 짧은 경로를 탐색하려고 한다. 이동은 상, 하, 좌, 우의 방향으로 1칸씩 할 수 있다고 가정한다.

(가) 이 문제를 해결하기 위한 평가함수를 정의하라.
이 문제를 해결하기 위한 탐색 알고리즘으로 A* 알고리즘을 이용할 것이다. A* 알고리즘은 휴리스틱(h) 값을 이용해 최적경로를 추정해나가는 방식이다. 휴리스틱이란 현재 노드에서 목표까지 가는 최적경로의 비용을 추정하는 것이다.

A* 알고리즘의 평가함수는 다음과 같다.
f(N) = g(N) + h(N)
g(N) : 초기 노드로부터 현재 노드까지의 경로비용
h(N) : 현재 노드로부터 목표 노드까지의 경로비용(추정)
f(N) : g(N)과 h(N)의 합(초기 노드로부터 목표 노드까지의 추정 경로비용)

미로를 2차원의 좌표평면으로 취급하여 노드를 좌표로 표현할 것이다. 즉 초기 노드는 (0,0), 목표 노드는 (4,4)이다.
휴리스틱 값인 h(N)은 통상 목표 노드까지의 직선거리를 많이 적용하지만, 이 문제에서는 맨해튼 거리를 사용할 것이다. 예를 들어 현재 노드가 (2,1)이라면 g(N)은 3이며 h(N)은 5이다. 즉 평가함수 f(N)은 3+5인 8이 된다. 이런 식으로 단계를 거듭하며 평가함수가 최소인 노드를 선택해나간다. 평가함수의 값이 같으면 임의로 선택할 수 있다.

참고 자료

정병두, & 유영근. (2015). A* 알고리즘 평가함수의 추정 부하량 변경에 관한 연구. 한국 ITS 학회 논문지, 14(3), 1-8.
이수진, 이기정, 황보택근, & 정원용. (2002). 최적경로 탐색을 위한 개선된 양방향 A* 알고리즘. 한국인터넷정보학회 학술발표대회 논문집, 3(1), 42-45.