[방통대][방송대][인공지능] 1) A 알고리즘의 주요 개념을 설명하라 2) 이동 횟수를 최소화하여 그림1 의 문제를 풀이하기 위해 문제를 표현하고 알고리즘에 적용할 평가함수를 정의하라 3) 그림1 의 문제를 풀이하는 알고리즘의 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라

과제정보

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

소개글

방통대 방송대 과제물 자료입니다.

과제점수 만점 자료만 공유합니다.

목차

1) A* 알고리즘의 주요 개념을 설명하라
2) 이동 횟수를 최소화하여 그림1 의 문제를 풀이하기 위해 문제를 표현하고 알고리즘에 적용할 평가함수를 정의하라
3) 그림1 의 문제를 풀이하는 알고리즘의 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라

본문내용

A* 알고리즘은 목표노드까지 도달하기 위한 최단 경로를 탐색하는 알고리즘이다. A* 알고리즘의 평가함수는 출발노드부터 목표노드까지 도달하는 데 소비한 비용으로 표현되며 아직 도달하지 못한 노드까지 필요한 경로비용은 예측치를 사용하게 된다. 이렇게 A* 알고리즘을 통해 얻은 결과는 목표까지 도달하기 위해 사용하였던 예측 경로비용의 정확도에 따라 정말로 최단 경로인지가 판별될 수 있으며, 예측한 경로비용이 항상 실제 비용 이하라는 것이 성립한다면 A* 알고리즘은 최소비용 경로를 탐색하는 것을 보장하게 된다.

참고 자료

없음