Implementation of Best First Search
#include<iostream>
#include<cstdlib>
using namespace std;
char goal;
void create();
void dfs();
void bfs();
struct node
{
bool visited;
int h;
char value;
int num;
struct node *child[10];
};
int oindex=0,kids;void display()
{
for(int i=0;i<kids;i++)
if(open[i]->visited == true)
cout<<endl<<open[i]->value;
}
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 BestFirstSearch(node *root,char c)
{
node *temp;
int total=0,oindex=0;
open[oindex]=root;
oindex++;
cout<<endl<<"PATH: ";
while(!allvisited())
{
int smallest=100;
for(int i=0;i<oindex;i++)
if(((open[i]->h)<smallest) && ((open[i]->visited) == false))
{
temp = open[i];
smallest = open[i]->h;
}
total += temp->h;
cout<<temp->value<<" "; //display current node
if(c==temp->value) //check if current node is equal to goal
{
c='y';
cout<<endl<<"Goal Reached";
break;
}
temp->visited = true;
for(int j=0;j<temp->num;j++) //current node to open[] iff not visted
{
if(temp->child[j]->visited == false)
{
open[oindex] = temp->child[j];
oindex++;
}
}
}
if(c != 'y')
cout<<"Goal Not Reached.";
cout<<endl<<"Cost = "<<total<<endl; //display total cost
}
int main()
{
char x;
cout<<"Enter the number of nodes : ";
cin>>kids;
for(int i=0;i<kids;i++)
{
node *temp = new node;
L[i] = temp;
cout<<"Enter Node "<<i+1<<" : ";
cin>>temp->value;
cout<<"Enter Node "<<i+1<<" Heuristic : ";
cin>>temp->h;
cout<<"Enter Number of Children of Node "<<i+1<<" : ";
cin>>temp->num;
temp->visited = false;
}
for(int i=0;i<kids;i++)
{
if(L[i]->num > 0)
{
cout<<"Enter the Nodes connected to "<<L[i]->value<<" : ";
for(int j=0;j<L[i]->num;j++)
{
char c;
cin>>c;
L[i]->child[j] = search(c);
}
}
}
cout<<"Enter the element to be searched : ";
cin>>x;
BestFirstSearch(L[0],x);
return 0;
}
OUTPUT:
Enter the number of nodes: 7
Enter Node 1: A
Enter Node 1 Heuristic: 10
Enter Number of Children of Node 1: 2
Enter Node 2: B
Enter Node 2 Heuristic: 2
Enter Number of Children of Node 2: 2
Enter Node 3: C
Enter Node 3 Heuristic : 3
Enter Number of Children of Node 3: 2
Enter Node 4 : D
Enter Node 4 Heuristic: 1
Enter Number of Children of Node 4 : 0
Enter Node 5: E
Enter Node 5 Heuristic: 4
Enter Number of Children of Node 5 : 0
Enter Node 6: F
Enter Node 6 Heuristic: 4
Enter Number of Children of Node 6 : 0
Enter Node 7: G
Enter Node 7 Heuristic : 0
Enter Number of Children of Node 7 : 0
Enter the Nodes connected to A: B
C
Enter the Nodes connected to B : D
E
Enter the Nodes connected to C: F
G
Enter the element to be searched: G
PATH: A B D C G
Goal Reached
Cost = 16