[인공지능]A* 알고리즘을 이용한 8-퍼즐 프로그램

소개

인공지능에서 많이 나오는 A* 알고리즘을 이용한 8-퍼즐 프로그램입니다.

목차

1. 주제

2. A* 알고리즘
2.1 A* 알고리즘
2.2 A* 알고리즘의 특징
2.3 평가함수의 사용

3. 8-퍼즐 프로그램

4. 자료구조
4.1 퍼즐 board 표현
4.2 Goal 표현

5. 설계
5.1 8-퍼즐의 움직임의 규칙
5.2 문제 해결과정

6. 프로그래밍

7. 실험
7.1 테스트환경
7.2 실험결과

8. 결과 및 고찰

9. 참고문헌

본문내용

2.1 A* 알고리즘
- 초기 노드에서 목표 노드까지의 경로를 찾는 그래프 탐색 알고리즘이다. 목표 노드까지의 가장 좋은 경로를 추정 (estimate of the best route) 하기 위해 각 노드에 랭킹을 부여하는 "heuristic estimate"를 사용하고 그 순서대로 노드를 방문한다. 따라서 A* algorithm 은 best-first search 의 한 예이다. A* algorithm 은 그래프에서 최단경로를 찾는 것을 보장하며 최소의 계산 (minimum computation) 으로 수행한다.

2.2 A* 알고리즘의 특징
① A*는 존재한다면, 시작으로부터 목표에 이르는 하나의 경로를 찾는다.
② A*는 최적의 경로를 찾는다.
③ A*는 heuristic을 가장 효율적으로 사용한다.

2.3 평가함수의 사용
- : 노드 n과 목표 노드 사이의 최단 경로의 실제 값
: 시작 노드 n0에서 노드 n까지의 최단 경로의 값
: n0에서 목표 노드까지 노드 n을 통하여 갈 수 있는 모든 가능한 경로 중에서 최단 경로의 값
- 의 값에 따라 정렬하면 가장 이상적
(은 실질적으로 계산 불가능 : 근사치 (추정치) 가 필요함)


3. 8-퍼즐 프로그램
- puzzle 문제는 3x3배열에 1에서 8까지의 블록이 있어서 한 칸의 빈칸을 이용하여 블록을 1부터 8까지 순서대로 배열 하는 문제이다.

참고자료

· 없음