A* 알고리즘을 이용한 8-Puzzle(8퍼즐) 프로그램 소스 및 설명

소개글

개발 환경 : Microsoft visual studio 2005, C#
C#프로그램 완전 소스와 자세한 주석으로 알아보기 쉽습니다.

컴파일 실행환경

Microsoft visual studio 2005 C#

본문내용

A* 알고리즘을 구현하기 위해 퍼즐의 상태를 알 수 있는 구조체를 만들어 주고 처음 상태에서 목표 상태로 가기 위한 최단 거리를 탐색한다.
구조체 {
public int[,] arr; //목표퍼즐상태와비교하기위한현재퍼즐상태를나타내는배열
public int Depth; //트리에서 얼마나깊게들어갔는지깊이목표상태까지의최소깊
public int Value; //Unmaching 값
public int Direction; //왔던길로 되돌아가지 않기 위한 방향 변수
public int Parent; //부모확인을 위한 변수
public int Child; //자기자신
}
각 구조체는 현재 퍼즐의 배열상태, 깊이 값 h*(n), 매칭 값 g(n), 이동 방향, 부모 번호, 자신 번호를 가진다. 여기서 매칭 값은 목표상태의 퍼즐 상태와 비교하여 매칭되지 않는 값은 저장한다. 매칭 되지 않는 값을 저장하는 이유는 깊이 값 h*(n)은 증가할수록 좋지 않은데 매칭 값 g(n)은 많이 매칭 될수록 좋은 상황이기 때문이다. 따라서 Unmaching값을 더해 주므로써 Unmaching 값 + 깊이 값이 적은 노드를 우선순위로 주어서 최단탐색경로로 검색을 하게 된다. 하지만 검색 시간이 오래 걸린 다는 단점이 있다.
탐색하면서 열린 노드들은 Queue에 저장이 되고 탐색이 끝날 때마다 삽입정렬을 이용하여 다시 우선순위대로 정렬을 시킨다. 우선순위 값이 같은 노드는 먼저 들어온 노드를 우선으로 처리해준다.

압축파일 내 파일목록

8-Puzzle.cs
8-Puzzle.csproj
8-Puzzle.Designer.cs
8-Puzzle.resx
8-Puzzle.sln
8-Puzzle.suo
Program.cs
bin/Debug/8-Puzzle.exe
bin/Debug/8-Puzzle.pdb
bin/Debug/8-Puzzle.vshost.exe
bin/Release/8-Puzzle.exe
bin/Release/8-Puzzle.pdb
obj/8-Puzzle.csproj.FileList.txt
obj/8-Puzzle.csproj.FileListAbsolute.txt
obj/Debug/8-Puzzle.csproj.GenerateResource.Cache
obj/Debug/8-Puzzle.exe
obj/Debug/8-Puzzle.pdb
obj/Debug/Refactor/
obj/Debug/TempPE/
obj/Debug/__Puzzle.Form1.resources
obj/Debug/__Puzzle.Properties.Resources.resources
obj/Release/8-Puzzle.csproj.GenerateResource.Cache
obj/Release/8-Puzzle.exe
obj/Release/8-Puzzle.pdb
obj/Release/TempPE/
obj/Release/__Puzzle.Form1.resources
obj/Release/__Puzzle.Properties.Resources.resources
Properties/AssemblyInfo.cs
Properties/Resources.Designer.cs
Properties/Resources.resx
Properties/Settings.Designer.cs
Properties/Settings.settings

전체 목록 보기

참고 자료

없음