Hi everyone, I haven't been around in a while, but I'm REALLY stuck on this one problem. I am taking an AI class and we have to write an A* search to answer the TOH problem. Really inefficient, but we just have to know how to implement an A* search algorithm. I know how to do it on paper, but I have no idea how to do it in code. I know I have to first start with setting up the correct data types (Linked lists), which to be honest I haven't used too often since I'm more of an array kind of person.
Here's what I have so far:
.h file->
If you notice, I have other functions for the recursive version, I tried searching and didn't find anything on A* so I got fed up and put it in there because I'm making a menu-based version and a mini version.
And here's my .c file->
As you can see I'm REALLY stuck, but I want to make sure that I have a full understanding of linked list. I could just Google it, but I'd rather learn from the experts here, hoping they can explain it clearly.
Any ideas would be greatly appreciated.
Here's what I have so far:
.h file->
Code:
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
/* Functions and class declaration */
void recursive(int x,char from,char to,char aux);
typedef struct State
{
//LOCKED
int ID;
int fvalue;
int gvalue;
int hvalue;
int d1;
int d2;
int d3;
//DO NOT ADD OR CHANGE
} State;
//*******************************************************************
/* Functions and class implementation */
State setState(int ID2,int fvalue2,int gvalue2,int hvalue2,int pega,int pegb,int pegc )
{
State temp;
temp.ID=ID2;
temp.fvalue=fvalue2;
temp.gvalue=gvalue2;
temp.hvalue=hvalue2;
temp.d1=pega;
temp.d2=pegb;
temp.d3=pegc;
return temp;
}
int check(State a,State b)
{
int drub=0;
if(a.d1==b.d1 && a.d2==b.d3 && a.d3==b.d3) drub=1;
return drub;
}
void insert(State a,State *list)
{
int i=(sizeof(list)-1);
while(i>0)
{
int j=i-1;
list[i]=list[j];
i--;
}
list[1]=list[0];
list[0]=a;
}
void graphState(State a)
{
printf("\n\nGraph-\n\n");
if(a.d1==1)printf("%d",1);
printf("\t");
if(a.d1==2)printf("%d",1);
printf("\t");
if(a.d1==3)printf("%d",1);
printf("\n");
if(a.d2==1)printf("%d",2);
printf("\t");
if(a.d2==2)printf("%d",2);
printf("\t");
if(a.d2==3)printf("%d",2);
printf("\n");
if(a.d3==1)printf("%d",3);
printf("\t");
if(a.d3==2)printf("%d",3);
printf("\t");
if(a.d3==3)printf("%d",3);
printf("\n");
printf("___\t___\t___");
}
void printState(State a)
{
if(a.ID==0 || a.ID==1)
{
printf("State F G H Disk1 Disk2 Disk3");
printf("\n-----------------------------------------------------------------\n");
}
printf("%d",a.ID);
printf("%12d",a.fvalue);
printf("%8d",a.gvalue);
printf("%8d",a.hvalue);
printf("%10d",a.d1);
printf("%12d",a.d2);
printf("%12d\n",a.d3);
//graphState(a);
printf("\n\n");
}
int stateSize(State a[])
{
int size=0,i=0;
State default2=setState(0,0,0,0,0,0,0);
while((check(a[i],default2)))
{
size++;
i++;
}
return ("%d",size);
}
void aStarTest()
{
State temp[8];
temp[0] = setState(1,6,0,6,1,1,1);
temp[1] = setState(2,6,1,5,3,1,1);
temp[2] = setState(3,8,3,5,3,2,1);
temp[3] = setState(4,10,4,6,2,2,1);
temp[4] = setState(5,10,7,3,2,2,3);
temp[5] = setState(6,11,8,3,1,2,3);
temp[6] = setState(7,11,10,1,1,3,3);
temp[7] = setState(8,11,11,0,3,3,3);
system("clear");
printf("Test~Hard coded-\n\n");
int i=0;
while(i<8)
{
printState(temp[i]);
i++;
}
}
//Functions used to calculate A* data
int calcF(int g,int h)
{
return (g+h);
}
int calcG(int oldG, int newG)
{
return (oldG + newG);
}
int calcH(int total)
{
return (6-total);
}
//**************************************************
void runRecursive()
{
char from='A',aux='B',to='C';
int n=3;
system("clear");
printf("Recursive-\n\n");
recursive(n,'A','C','B');
}
//Recursive
void recursive(int x, char from,char to,char aux)
{
if(x==1)
{
printf("Move Disk %d From %c to %c\n",x,from,to);
}
else
{
recursive(x-1,from,aux,to);
printf("Move Disk %d From %c to %c\n",x,from,to);
recursive(x-1,aux,to,from);
}
}
//*********************************************************************************************************************
//Double linked list
typedef struct List
{
//LOCKED
State data;
struct List *head;
struct List *tail;
//DO NOT ADD OR CHANGE
}List;
void resetState(List a)
{
a.data=setState(0,0,0,0,0,0,0);
a.head=NULL;
a.tail=NULL;
}
int calcTotal(List states)
{
List temp=states;
int total=0;
if(temp.head)
{
while(temp.tail)
{
temp=temp.tail;
total+=temp.data.d3;
}
}
return total;
}
//*********************************************************************************************************************
And here's my .c file->
Code:
List open; //List to hold open queue
List closed; //List to hold closed queue
List *head,*tail; //Used for linked list
void initial(); //Initial state
int isComplete(State a); //Check if complete
void hero(); //Actual search function
void neighbors(); //
void generate(); //Used to generate list of states
int isGoal(State a); //Checks to see if goal to print list
int main()
{
printf("\n\n");
banner();
resetState(open);
resetState(closed); //Reset lists
printf("\nTower of Hannoi-\n\n");
initial();
hero();
generate();
complete();
return 0;
}
//A* functions
void initial()
{
State first=setState(1,6,0,6,1,1,1); //ID,f,g,h,d1,d2,d3
open.data=first;
open.head=head;
open.tail=NULL;
}
int isComplete(State a)
{
int checker=0;
if(a.hvalue==0) checker=1;
return checker;
}
void hero()
{
}
void generate()
{
State default2=setState(0,0,0,0,0,0,0);
printState(open.data);
}
Any ideas would be greatly appreciated.
Comment