Implementation of A* Algorithm
#include<iostream>
using namespace std;
struct node
{
bool visited;
int hue,num;
char value;
int dist[10];
struct node *child[10];
};
struct node *l[20],*open[20];
int oindex=0,kids;
node *search(char c)
{
for(int i=0;i<kids;i++)
{
if(l[i]->value==c)
return l[i];
}
}
bool allvisited()
{
for(int i=0;i<kids;i++)
{
if(l[i]->visited==false)
return false;
}
return true;
}
void astar(node *root,char c)
{
node *temp,*current;
int total=0,oindex=0,dist;
open[oindex]=root;
oindex++;
cout<<"Path : "<<root->value<<" ";
root->visited=true;
if(c==root->value)
#include<iostream>
using namespace std;
struct node
{
bool visited;
int hue,num;
char value;
int dist[10];
struct node *child[10];
};
struct node *l[20],*open[20];
int oindex=0,kids;
node *search(char c)
{
for(int i=0;i<kids;i++)
{
if(l[i]->value==c)
return l[i];
}
}
bool allvisited()
{
for(int i=0;i<kids;i++)
{
if(l[i]->visited==false)
return false;
}
return true;
}
void astar(node *root,char c)
{
node *temp,*current;
int total=0,oindex=0,dist;
open[oindex]=root;
oindex++;
cout<<"Path : "<<root->value<<" ";
root->visited=true;
if(c==root->value)
cout<<"Goal reached.";
cout<<"Cost = "<<total<<endl;
return;
}
for(int j=0;j<root->num;j++)
{
if(root->child[j]->visited==false)
{
open[oindex]=root->child[j];
oindex++;
}
}
current=root;
while(!allvisited())
{
int smallest=100;
if(current->num==0)
{
for(int i=0;i<oindex;i++)
{
if(open[i]->visited==false)
{
temp=open[i];
break;
}
}
}
else
for(int i=0;i<current->num;i++)
{
int childcost=(current->child[i])->hue+current->dist[i];
if(((childcost)<smallest)&&(current->child[i]->visited==false))
{
dist=current->dist[i];
temp=current->child[i];
smallest=childcost;
}
}
current=temp;
current->visited=true;
total=total+dist;
cout<<current->value<<"";
if(c==current->value)
{
c='y';
cout<<"Goal Reached.";
break;
}
for(int j=0;j<temp->num;j++)
{
if(current->child[j]->visited==false)
{
open[oindex]=current->child[j];
oindex++;
}
}
}
if(c!='y')
cout<<"Goal not reached.";
total=total+current->hue;
cout<<"cost="<<total;
}
int main()
{
char x,g;
cout<<"Enter the Number of nodes : ";
cin>>kids;
for(int i=0;i<kids;i++)
{
node *temp= new node;
l[i]=temp;
cout<<"Enter the new node details"<<endl;
cout<<"Name : ";
cin>>temp->value;
cout<<"Heuristic value : ";
cin>>temp->hue;
cout<<"How many nodes connected to "<<temp->value<<" : ";
cin>>temp->num;
temp->visited=false;
}
for(int i=0;i<kids;i++)
{
if(l[i]->num>0)
{
cout<<"Enter the nodes and its distance to "<<l[i]->value<<" : ";
for(int j=0;j<l[i]->num;j++)
{
char c,y;
int x;
cout<<"Name : ";
cin>>c;
cout<<"Cost : ";
cin>>x;
l[i]->child[j]=search(c);
l[i]->dist[j]=x;
}
}
}
cout<<"Enter the goal node : ";
cin>>g;
astar(l[0],g);
return 0;
}
OUTPUT
Enter the Number of nodes : 5
Enter the new node details
Name : S
Heuristic value : 7
How many nodes connected to S : 2
Enter the new node details
Name : A
Heuristic value : 6
How many nodes connected to A : 3
Enter the new node details
Name : B
Heuristic value : 2
How many nodes connected to B : 1
Enter the new node details
Name : C
Heuristic value : 1
How many nodes connected to C : 1
Enter the new node details
Name : G
Heuristic value : 0
How many nodes connected to G : 0
Enter the nodes and its distance to S : Name : A
Cost : 1
Name : B
Cost : 4
Enter the nodes and its distance to A : Name : B
Cost : 2
Name : C
Cost : 5
Name : G
Cost : 12
Enter the nodes and its distance to B : Name : C
Cost : 2
Enter the nodes and its distance to C : Name : G
Cost : 3
Enter the goal node : G
Path : SBCG
Goal Reached.
Cost=9