휴리스틱(A*) 알고리즘- 8퍼즐

소개

제가 인공지능 레포트로 직접 코딩한 소스입니다.
도움이 되었으면 하네요..^^*

컴파일 실행환경

비주얼 C

본문내용

휴리스틱(A*) 알고리즘을 이용한 8퍼즐입니다.
처음 경로(예: 4 1 2 7 5 3 8 0 6)와 결과(1 2 3 4 5 6 7 8 0)을 입력하면 휴리스틱 알고리즘에 의해 중간 경로를 찾아서 화일에 뿌려줍니다.

참고) 출력을 화일에 뿌려주었습니다.
- N = 100,200,300... 일때 그때의 N의 state값과 그때 open에 남아 있는 노드 갯수를 화일에 출력해주었습니다.
- N = Goal 일때까지의 count값을 화일에 뿌려주었습니다.

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct nodedef* nodeptr;
typedef int by_3_3[3][3];
typedef struct nodedef{
by_3_3 state;
double g,h,f;
by_3_3 prestate;
nodeptr link;
}node;

nodeptr open=NULL, closed=NULL, successed=NULL;
nodeptr N=NULL;
by_3_3 start = {0,}; // 초기화
by_3_3 goal = {0,};

void create_successed(); // successed 의 node 생성
int compare(by_3_3 goal, by_3_3 curr); // state 의 비교
nodeptr cmp_node(nodeptr p1, nodeptr p2); // successed 의 data 가 유효한 값인가..
nodeptr nail(nodeptr pnode); // 마지막 node return
void print_closed(int count,FILE *fp); // display
void free_heap(); // deallocate heap

void main()
{
nodeptr start_value, temp, min, pre, pre_temp;
int count=0, nodecnt=0;
FILE *fp;
fp=fopen("print.txt","w");
///////////////////////////// input state /////////////////////////////////////////////
printf("Start state = ");
scanf("%d%d%d%d%d%d%d%d%d",&start[0][0],&start[0][1],&start[0][2],
&start[1][0],&start[1][1],&start[1][2],&start[2][0],&start[2][1],&start[2][2]);

printf("Goal state = ");
scanf("%d%d%d%d%d%d%d%d%d",&goal[0][0],&goal[0][1],&goal[0][2],
&goal[1][0],&goal[1][1],&goal[1][2],&goal[2][0],&goal[2][1],&goal[2][2]);

참고자료

· 없음