A* 알고리즘 코드(에러있음)

일정 거리 이상이면 에러 발생하는 버전.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include "Puzzle_Structure.c"

#define null '\0'

#define CAPACITY 100000

#define row 4

#define col 4

#define true 1

#define false 0

int TRY = 0;

int Element_Count = 0;

//int Closeded_Count = 0;

int save = 0;

int mn = 0;

state* root;

Tr* TrRoot;

void Push_OPEN(state* OPen[], state*);

state* Pop_OPEN(state* Open[]);

int Compute_Hh(state*); //골

state* Best_First_In_OPEN(state* Open[]);

void Successors_Expand(state* Open[], state* curr); //골

void Insert_Tree(Tr* tree,state* curr);

void Print_Direction(int cases); ////1:move right, 2: move left, 3:move up, 4:move down

void m_init(state* Open[], state* m, state* curr, int DirectionFromParent);

int test1(state* Open[], state* m);

void test2(state* Open[], state* m);

int main()

{

FILE* fp = fopen("output.txt","w");

//start state

int Puzzle_4x4[row][col] = { {0,1,2,3}, {4,5,6,7}, {8,9,10,11}, {12,13,14,15} }; //0은 빈 타일

//goal state   test1 : 정답은 오른쪽 세칸

int Goal[row][col]  = { {1,2,3,0}, {4,5,6,7}, {8,9,10,11} ,{12,13,14,15} };

//우선순위큐방식. stack방식으로 처리 //memset(Open,null,sizeof(state)*CAPACITY);

state* Open[CAPACITY] = {null}; 

state* StartState;

state* curr;

//잡다

int input=0;

int i,j;

int pathflag = false;

int printflag = false;

int oldpath = 0;

StartState = (state*)malloc(sizeof(state));

root = (state*)malloc(sizeof(state));

while(1){

pathflag = false;

save = 0;

memset(Open,null,sizeof(Open));

//입력

printf("탐색을 원하시나요? (yes:1 / no:0)\n");

scanf("%d",&input);

if(input == 1)

{

printf("시작노드 = ");

for(i=0;i<row;i++)

for(j=0;j<col;j++)

scanf("%d",&Puzzle_4x4[i][j]);

printf("목표노드 = ");

for(i=0;i<row;i++)

for(j=0;j<col;j++)

scanf("%d",&Goal[i][j]);

printf("\n");

//state 초기화

for(i=0;i<row;i++)

for(j=0;j<col;j++)

{

StartState->Number[i][j] = Puzzle_4x4[i][j];

root->Number[i][j] = Goal[i][j];

}

StartState->Parent = null;

StartState->Gh = 0;

StartState->Hh = Compute_Hh(StartState);

StartState->Fh = StartState->Gh + StartState->Hh;

StartState->closed = false;

//필요한가? 그냥 스테이트들마다 parent 정보 가지고있으니까

TrRoot = (Tr*)malloc(sizeof(Tr));

TrRoot->Node = StartState;

TrRoot->StateTr = null;

Push_OPEN(&Open[Element_Count], StartState);

curr = null;

do

{

TRY++;

if(TRY>40000){

printf("탐색실패\n");return 0;}

if(curr && Element_Count == 0)

printf("탐색실패\n"); //while 조건문에 걸리기때문에 실행될일은 없음.  제일 처음에 한번 검사함

curr = Best_First_In_OPEN(&Open[0]);

curr->closed = true;

//Open[save] = null;

//Element_Count--; //이걸 할게 아니라 save에 있는걸 지워야지

//Push_Closed(&Closed[0], curr);

Insert_Tree(TrRoot, curr);

//정답 테스트

if(Compute_Hh(curr) == 0)

{

//printf("정답 찾음\n"); //경로 반환해야함

//경로 반환

while(TrRoot !=null)

{

if(TrRoot->Node==StartState && pathflag == false)

{ //한번 밀기위해

pathflag = true;

TrRoot = TrRoot->StateTr;

printf("This is the start state\n");

fprintf(fp,"This is the start state\n");

}

else{

for(i=0;i<row;i++)

{

for(j=0;j<col;j++)

{

printf("%2d ",TrRoot->Node->Number[i][j]);

fprintf(fp,"%3d",TrRoot->Node->Number[i][j]);

}

printf("\n");

fprintf(fp,"\n");

}

oldpath = TrRoot->Node->Fh;

//여기에 방향 출력

Print_Direction(TrRoot->Node->DirectionFromParent);

TrRoot = TrRoot->StateTr;//이거 테스트 어디다 해야하나

printf("\n");

fprintf(fp,"\n");

}

}

printf("%d\n",oldpath);

TrRoot = null;

oldpath = 0;

Element_Count =0;

//Closeded_Count = 0;

break;

}

//석세서들을 오픈에 넣고 다음 스탭에서 제일 좋은애를 curr로 뽑아야함. 

//open closed 고려해야함.

Successors_Expand(&Open[0],curr);

}while(Element_Count != 0);

fflush(fp);

}

else if(input == 0)

{

printf("Program Complete!\n");

fclose(fp);

return 0;

}

else

{

printf("잘못된 입력\n");

fflush(fp);

}

}

return 1; //비정상종료

}

void Push_OPEN(state* Open[], state* m)

{

int count = 0;

int i = 0;

int flag=false;

//이게 없으면 포인터로 연결되어 open에 잘못들어감!!

state* newstate = (state*)malloc(sizeof(state));

memcpy(newstate,m,sizeof(state));

if(++Element_Count >= CAPACITY-1)

{

printf("CAPACITY IS FULL\n");

return;

}

while(i<CAPACITY)

{

if(Open[i] == null)

{

Open[i] = newstate;

break;

}

i++;

}

//주의!!! Element_Count 한개 증가함!!!!

}

int Compute_Hh(state* state)

{

int i,j;

int Unmatched_Count = 0;

for(i=0;i<row;i++)

for(j=0;j<col;j++)\

{

if(state->Number[i][j] != root->Number[i][j])

Unmatched_Count++;

}

return Unmatched_Count;

}

state* Best_First_In_OPEN(state* Open[])

{

int i,j;

state* curr = Open[0];

//printf("%d\n", Element_Count);

for(i =0;i<Element_Count-1; i++)

{

for(j=i+1;j<Element_Count; j++)

if(Open[i]->Fh > Open[j]->Fh)

{

if(Open[j]->closed == true)

{}

else{

curr = Open[j];

save = j;

}

}

}

return curr;

}

void Successors_Expand(state* Open[], state* curr)

{

//0을 찾아서 인접셀과 이동한거를 오픈에 넣음

int i,j,k,l,temp;

int RowOfEmpty;

int ColOfEmpty;

int Number_Copy[row][col];

state* m = (state*)malloc(sizeof(state));

//m = curr;

memcpy(m,curr,sizeof(state));

for(k=0;k<row;k++)

for(l=0;l<col;l++)

Number_Copy[k][l] = curr->Number[k][l];

for(i=0;i<row;i++)

for(j=0;j<col;j++)

if(curr->Number[i][j] == 0 )

{

RowOfEmpty = i;

ColOfEmpty = j;

//i,j주변과 바꿔줘야 함.   m을 구해야돼!!!

if(i-1 > 0)

{

temp = Number_Copy[RowOfEmpty - 1][ColOfEmpty];

Number_Copy[RowOfEmpty - 1][ColOfEmpty] = 0;

Number_Copy[RowOfEmpty][ColOfEmpty] = temp;

memcpy(m->Number,Number_Copy,sizeof(m->Number));

memcpy(Number_Copy,curr->Number,sizeof(Number_Copy));

m_init(&Open[0], m, curr,3);

if(test1(&Open[0],m)){test2(&Open[0],m);}

else

Push_OPEN(&Open[0], m);

memcpy(m,curr,sizeof(state));

}

if(i+1 < row)

{

temp = Number_Copy[RowOfEmpty + 1][ColOfEmpty];

Number_Copy[RowOfEmpty + 1][ColOfEmpty] = 0;

Number_Copy[RowOfEmpty][ColOfEmpty] = temp;

memcpy(m->Number,Number_Copy,sizeof(m->Number));

memcpy(Number_Copy,curr->Number,sizeof(Number_Copy));

m_init(&Open[0], m, curr,4);

/*

if(test1(&Open[0],m)){}

else

Push_OPEN(&Open[0], m);

memcpy(m,curr,sizeof(state));

*/

if(test1(&Open[0],m)){test2(&Open[0],m);}

else

Push_OPEN(&Open[0], m);

memcpy(m,curr,sizeof(state));

}

if(j-1 > 0)

{

temp = Number_Copy[RowOfEmpty][ColOfEmpty-1];

Number_Copy[RowOfEmpty][ColOfEmpty-1] = 0;

Number_Copy[RowOfEmpty][ColOfEmpty] = temp;

memcpy(m->Number,Number_Copy,sizeof(m->Number));

memcpy(Number_Copy,curr->Number,sizeof(Number_Copy));

m_init(&Open[0], m, curr,2);

if(test1(&Open[0],m)){test2(&Open[0],m);}

else

Push_OPEN(&Open[0], m);

memcpy(m,curr,sizeof(state));

}

if(j+1 < col)

{

temp = Number_Copy[RowOfEmpty][ColOfEmpty+1];

Number_Copy[RowOfEmpty][ColOfEmpty+1] = 0;

Number_Copy[RowOfEmpty][ColOfEmpty] = temp;

memcpy(m->Number,Number_Copy,sizeof(m->Number));

memcpy(Number_Copy,curr->Number,sizeof(Number_Copy));

m_init(&Open[0], m, curr,1);

if(test1(&Open[0],m)){test2(&Open[0],m);}

else

Push_OPEN(&Open[0], m);

memcpy(m,curr,sizeof(state));

}

return;

}

}

void test2(state* Open[], state* m)

{

int i,j,n;

int count = 0;

int flag = false;

//open에서 찾어

for(n=0;n<Element_Count;n++)

{

for(i=0;i<row;i++)

for(j=0;j<col;j++)

if(Open[n]->Number[i][j] == m->Number[i][j])

count++;

if(count == row*col)

{

//flag = true;

if((Open[n]->Fh) > (m->Fh))

{

Open[n]->Gh = m->Gh;

Open[n]->Fh = m->Fh;

Open[n]->Parent = m->Parent;

if(Open[n]->closed == true)

Open[n]->closed = false;

}

break;

}

count= 0;

}

/*

if(flag == true)

return Open[n]->closed;

else//없는경우

return Open[--n]->closed;*/

}

int test1(state* Open[], state* m)

{

int i,j,n;

int count = 0;

int flag= 0;

//open에서 비교해

for(n=0;n<Element_Count;n++)

{

for(i=0;i<row;i++)

for(j=0;j<col;j++)

if(Open[n]->Number[i][j] == m->Number[i][j])

count++;

if(count == row*col)

{

flag = 1;

break;

}

count = 0;

}

if(flag == 0)

return 0;

return 1;

}

//나중에 open지울것

void m_init(state* Open[], state* m, state* curr, int DirectionFromParent)

{

m->closed = false;

m->Parent = curr;

m->Gh = (m->Gh) + 1;

m->Hh = Compute_Hh(m);

m->Fh =(m->Gh) + (m->Hh);

m->DirectionFromParent = DirectionFromParent;

}

void Insert_Tree(Tr* TrRoot, state* curr)

{

Tr* cursor = TrRoot;

Tr* newcurr = (Tr*)malloc(sizeof(Tr));

newcurr->Node = curr;

newcurr->StateTr = null;

while(cursor->StateTr != null)

cursor = cursor->StateTr;

cursor->StateTr = newcurr;

}

void Print_Direction(int cases) ////1:move right, 2: move left, 3:move up, 4:move down

{

//fflush(fp);

if(cases <1 || cases>4){}

else if(cases ==1)printf("==> move right\n");

else if(cases ==2)printf("==> move left\n");

else if(cases==3) printf("==> move up\n");  

else if(cases==4) printf("==> move down\n"); 

else

printf("direction print test\n");

}