[C언어]8퍼즐소스입니다. A* 알고리즘 이용 (C언어)

소개

A* 알고리즘을 이용하여 작성한 8퍼즐 소스입니다.

소스에서 주석 처리로 초기 값을 랜덤으로도 가능하게 해 놓았습니다.

랜덤으로 생성시 해가 없는 숫자가 배열될 수 있습니다.
ex) {(2,1,3),(4,5,6),(7,8,0)} 이런 경우 모든 경우를 검색해 보아야지만 검색에 실패했음을 알수 있습니다.

모든경우의 수는 30만 이상으로 시간이 너무 오래 걸릴경우 open, close, 확장노드의 출력 부를 지워주시면 실행 결과 시간을 단축 시킬수 있습니다.

open과 close의 값들은 그냥 간단히 평가 점수를 넣어 주었습니다.
(단지 open,close에 값들이 잘 들어가나 확인용으로 구현한것임.)

동봉된 파일은 소프파일, 연산자코드, 알고리즘이 들어있습니다.

컴파일 실행환경

비주얼스튜디어6.0에서 구현 실행 했습니다.

본문내용

typedef struct _8X_PUZZLE{ // 8퍼즐 구조체 선언
int state[3][3]; // 상태 표시
int fn; // 평가 점수( f`(n) = g(n) + h`(n) )
struct _8X_PUZZLE* next; // 다음 노드
struct _8X_PUZZLE* parent; // 부모 노드
// struct _CHILD_TREE* tree; // 자식 노드 위한 child_tree 가르키는
}Puzzle, Child, Open, Close;

//typedef struct _CHILD_TREE{
// struct _CHILD_TREE* next; // 다음 노드
// struct _8X_PUZZLE* child; // 자식 노드
//}Child_tree;

//------------------------------------------------------------------

void initial_node_create(); // 초기 노드 생성
void append_open(); // open에 원소르 추가
void append_close(); // close에 원소를 추가
void delete_open_node(); // open에서 원소 제거
bool give_expansible(); // 확장한 노드의 원소를 가져옴
bool is_goal(); // 목표값인가 확인
bool is_expansible(); // 확장가능한가?
bool exist_open(); // 확장노드가 open에 존재하는가?
bool exist_close(); // 확장노드가 close에 존재하는가?
void print_path(); // 경로 출력
void free_memory(); // 메모리 반환
void SWAP(int& x, int& y); // 위치 변경

void main(){ // main()
initial_node_create(); // 초기 노드 생성
while(1){
Open* op = start_op;
if(start_op){ // open에 원소가 남았나 확인
printf("nopen :");
while(op){ // open의 원소의 평가점수 출력
printf("%d ",op->fn);
op = op->next;
}
//-----------------------------------------------------------------
void free_memory(){ // 전체 활당된 메모리 반환
_8X_PUZZLE* del = NULL;

Puzzle* ptr = start_ptr;
while(ptr){ // ptr 메모리 반환
del = ptr;
ptr = ptr->next;
free(del);
//-----------------

참고자료

· 없음