2023년 1학기 방송통신대 인공지능 중간과제물)균일비용 탐색, 언덕오르기 탐색, A* 알고리즘을 설명하고, 각 기법의 특성을 서로 비교하라 A* 알고리즘을 이용하여 8퍼즐 문제를 풀이하려고 한다

소개글

2023년 1학기 방송통신대 인공지능 중간과제물)균일비용 탐색, 언덕오르기 탐색, A* 알고리즘을 설명하고, 각 기법의 특성을 서로 비교하라 A* 알고리즘을 이용하여 8퍼즐 문제를 풀이하려고 한다에 대한 보고서 자료입니다.

목차

1. 균일비용 탐색, 언덕오르기 탐색, A* 알고리즘을 설명하고, 각 기법의 특성을 서로 비교하라.

1) 균일비용 탐색 2) 언덕오르기 탐색 3) A* 알고리즘

2. A* 알고리즘을 이용하여 8퍼즐 문제를 풀이하려고 한다. 초기상태와 목표상태는 다음 그림과 같다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 네 개의 연산자를 사용하며, 어떠한 상태의 비용 역시 교재 및 강의에서처럼 목표상태와 비교하였을 때 지정된 위치에 존재하지 않는 조각의 수로 정의한다. 조각의 이동 횟수를 최소화하여 문제를 해결하기 위해 A* 알고리즘에 의해 탐색을 하는 과정을 나타내는 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라.

3. 참고문헌

본문내용

경로를 반환하는 것을 보장한다. 또한 함수 을 사용함으로써 균일비용 탐색을 한 경우보다 탐색과정이 효율적이다.
2. A* 알고리즘을 이용하여 8퍼즐 문제를 풀이하려고 한다. 초기상태와 목표상태는 다음 그림과 같다. 연산자는 교재 및 강의에서 정의한 빈칸을 상/하/좌/우로 한 칸씩 이동하는 네 개의 연산자를 사용하며, 어떠한 상태의 비용 역시 교재 및 강의에서처럼 목표상태와 비교하였을 때 지정된 위치에 존재하지 않는 조각의 수로 정의한다. 조각의 이동 횟수를 최소화하여 문제를 해결하기 위해 A* 알고리즘에 의해 탐색을 하는 과정을 나타내는 탐색트리를 구하라. 각각의 노드에 평가함수의 계산식 및 노드 확장 순서를 표시하라(강의 3강 30번 슬라이드 참고).
출발노드
1
1
5
2
4
3
7
8
6
=0+5=5
5
2
1
4
3
7
8
6
=1+6=7
1
5
2
7
4
3
8
6
=1+6=7
2
1
5
2
4
3
7
8
6
=1+4=5
3
1
2
4
5
3
7
8
6
=2+3=5
1
5
2
4
8
3
7
6
=2+5=7
1
5
2
4
3
7
8
6
=2+5=7
1
5
2
4
3
7
8
6
=2+4=6
1
5
2
4
3
7
8
6
=3+4=7
1
2
4
5
3
7
8
6
=3+4=7
4
1
2
4
5
3
7
8
6
=3+2=5
5
1
2
3
4
5
7
8
6
=4+1=5
1
2
4
5
3
7
8
6
=4+3=7
1
2
4
5
3
7
8
6
=5+2=7
목표노드
1
2
3
4
5
6
7
8
=5+0=5
1
2
3
4
5
7
8
6
=5+2=7
각 노드의 평가함수 으로 계산한다. 조각 한 개를 이동시키는 비용을 1로 하면, 은 출발노드를 0으로 시작하여 노드 확장 시마다 1씩 증가하는 값이 된다. 은 목표상태와 비교하였을 때 지정된 위치에 존재하지 않는 조각의 수로 정의한다. 이 문제의 경우 임의의 노드에서 올바른 위치에 있지 않은 조각들을 지정된 위치로 옮기려면 대상조각의 수보다 많거나 최소한 동일한 수만큼 조각을 이동시켜야 하므로 는 는 항상 작거나 같으므로, 탐색결과는 최소비용 경로를 보장한다.
위 탐색트리에서 확장순서는 1 → 2 → 3 → 4 → 5 이다.
3. 참고문헌
이광형, 이병래(2018), 인공지능, 한국방송통신대학교출판문화원.
천인국(2020), 인공지능 : 파이썬으로 배우는 머신러닝과 딥러닝, 인피니티북스.
스튜어트 러셀 , 피터 노빅(2016), 인공지능. 1: 현대적 접근방식 3판, 제이펍.

키워드

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