인공지능 2025년 1학기 방송통신대 중간과제물)A* 알고리즘의 탐색 방법의 개념 평가함수 특성 등에 대하여 설명하라 탐색트리를 구하고 각각의 노드에 평가함수의 계산식 및 노드 확장 순서 네 개의 연산자 추가 등

소개글

인공지능 2025년 1학기 방송통신대 중간과제물)A* 알고리즘의 탐색 방법의 개념 평가함수 특성 등에 대하여 설명하라 탐색트리를 구하고 각각의 노드에 평가함수의 계산식 및 노드 확장 순서 네 개의 연산자 추가 등에 대한 보고서 자료입니다.

목차

A* 알고리즘에 대한 다음의 내용을 작성하라.

(가) A* 알고리즘의 탐색 방법의 개념, 평가함수, 특성 등에 대하여 설명하라.

(나) <그림 1>의 8-퍼즐 문제를 A* 알고리즘으로 풀이하려고 한다. 탐색의 목표는 빈칸의 이동 횟수가 최소인 풀이를 찾는 것이다. 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 네 가지 연산자를 사용한다. 탐색트리를 구하고, 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라.

(다) (나)에서 사용한 네 개의 연산자와 함께 <그림 2>와 같이 빈칸을 상/하/좌/우로 두 칸 이동하여 두 개의 퍼즐 조각을 한꺼번에 밀어 움직이는 네 개의 연산자를 추가로 사용하려고 한다. 두 유형의 연산자 모두 1회의 이동으로 계산한다. 탐색트리를 구하고, 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라.

(라) (나)와 (다)의 풀이 방식이 이동 횟수가 최소인 해를 구할 수 있는지에 대해 고찰하라.

(마) 참고문헌

본문내용

가지 연산자를 사용한다. 탐색트리를 구하고, 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라.
<그림 1> 8-퍼즐 문제
<그림 2> 두 칸 상향이동 연산자
아래 탐색트리 노드에서 주황색 상자의 왼쪽 숫자가 확장 순서에 해당한다. 각 노드의 우측의 계산식이 비용함수을 나타낸다. 비용함수는 각 노드 상태에 도달하는 동안 이동한 칸 수와 목표상태와 다른 상태의 개수(각 노드에서 회색 칸 수)를 합한 것이다.
4
1
3
1
2
6
7
5
8
0+5=5
4
1
3
7
2
6
5
8
1+6=7
1
3
2
4
2
6
7
5
8
1+4=5
4
1
3
2
6
7
5
8
1+5=6
1
3
3
4
2
6
7
5
8
2+3=5
1
2
3
4
4
6
7
5
8
3+2=5
1
3
4
2
6
7
5
8
3+4=7
1
2
3
4
6
7
5
8
4+3=7
1
2
3
4
6
7
5
8
4+3=7
1
2
3
5
4
5
6
7
8
4+1=5
1
2
3
4
5
6
7
8
5+2=7
1
2
3
목표상태
6
4
5
6
7
8
5+0=5
(다) (나)에서 사용한 네 개의 연산자와 함께 <그림 2>와 같이 빈칸을 상/하/좌/우로 두 칸 이동하여 두 개의 퍼즐 조각을 한꺼번에 밀어 움직이는 네 개의 연산자를 추가로 사용하려고 한다. 두 유형의 연산자 모두 1회의 이동으로 계산한다. 탐색트리를 구하고, 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라.
2칸 이동 연산자를 추가함으로써 나의 탐색과정에 추가적인 노드가 생긴다. 결과적으로 나보다 1단계 더 빨리 목표상태에 도달하게 되고, 그 비용도 5에서 4로 감소하게 된다.
4
1
3
1
2
6
7
5
8
0+5=5
4
1
3
7
2
6
5
8
1+6=7
1
3
2
4
2
6
7
5
8
1+4=5
4
1
3
2
6
7
5
8
1+5=6
4
1
3
2
6
7
5
8
1+6=7
1
3
3
4
2
6
7
5
8
2+3=5
1
3
4
2
6
7
5
8
2+4=6
4
1
3
7
2
6
5
8
2+6=8
1
2
3
4
6
7
5
8
3+2=5
1
3
4
2
6
7
5
8
3+4=7
1
2
3
4
4
5
6
7
8
3+1=4
1
2
3
4
6
7
5
8
4+3=7
1
2
3
4
6
7
5
8
4+3=7
1
2
3
4
5
6
7
8
4+1=5
1
2
3
4
6
7
5
8
4+2=6
1
2
3
4
5
6
7
8
4+2=6
1
2
3
목표상태
5
4
4
6
7
8
4+0=4
(라) (나)와 (다)의 풀이 방식이 이동 횟수가 최소인 해를 구할 수 있는지에 대해 고찰하라.
임의의 노드에서 올바른 위치에 있지 않은 조각들을 지정된 위치로 옮기려면 대상조각의 수보다 많거나 최소한 동일한 수만큼 조각을 이동시켜야 하기 때문에, 은 보다 항상 작거나 같다고 할 수 있으므로 탐색결과는 최소비용 경로를 보장한다.
(마) 참고문헌
이광형, 이병래(2018), 인공지능, 한국방송통신대학교출판문화원.
멀티미디어 강의.
스튜어트 러셀 , 피터 노빅(2016), 인공지능. 1: 현대적 접근방식 3판, 제이펍.
과제 스트레스 싹~ 학점 쑥!

키워드

방송통신대인공지능,   방송대인공지능,   방통대인공지능