8퍼즐 문제를 A스타 알고리즘으로 풀이하려고 한다.

과제정보

학과	컴퓨터과학과	학년	4학년
과목명	인공지능	자료	5건
공통	8퍼즐 문제를 A* 알고리즘으로 풀이하려고 한다. <그림 1>은 풀이할 문제이다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 것 외에 상/하/좌/우로 두 칸 이동하여 두 개의 퍼즐 조각을 한꺼번에 밀어 ... 더보기 8퍼즐 문제를 A* 알고리즘으로 풀이하려고 한다. <그림 1>은 풀이할 문제이다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 것 외에 상/하/좌/우로 두 칸 이동하여 두 개의 퍼즐 조각을 한꺼번에 밀어 움직이는 것을 포함한다. 예를 들어 <그림 2>는 빈 칸을 우측으로 두 칸 움직이는 연산자를 적용한 결과이다. 두 유형의 연산자 모두 1회의 이동으로 계산한다. (가) A* 알고리즘의 주요 개념을 설명하라. (나) 이동 횟수를 최소화하여 <그림 1>의 문제를 풀이하기 위해 문제를 표현하고, A* 알고리즘에 적용할 평가함수를 정의하라. (다) <그림 1>의 문제를 풀이하는 A* 알고리즘의 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라. 접기

소개글

인공지능 만점받은 중간 과제물입니다.
8퍼즐 문제를 A* 알고리즘으로 풀이 하는 문제이며,
평가함수정의, 문제표현, 연산자 등을 통해
초기상태 및 목표값 도달까지
이미지를 통해 쉽게 설명해 놓은 과제입니다.

목차

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

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

(다) <그림 1>의 문제를 풀이하는 A* 알고리즘의 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라.

본문내용

A* 알고리즘은 그래프 탐색 알고리즘의 하나로 출발점부터 도착점(목표점)까지 도달하는 데 최적(최단)의 경로를 찾아주는 탐색 알고리즘이다.
최적의 탐색 경로를 찾기 위해서는 출발노드에서 현재까지의 진행된 경로비용과 현재부터 경험적 지식을 토대로 도착점에 이르는 예측 경로 비용의 합을 평가값으로 최적의 노드를 선택 가능하며, 이를 위해서는 평가함수가 정의되어야 한다.

참고 자료

없음