Sunday, March 25, 2012

Informed Search Strategies

Informed Search (Heuristic Search ) use problem specific knowledge beyond the definition of the problem itself
Best First Search use Evaluation Function F(n) for each node as an estimate of desirability
expand most desirable unexpanded node
the node with lowest evaluation is selected for expansion 
measure is based on F(n) function
h(n)=estimated the cheapest cost from n to goal
g(n)=cost from initial start node to reach n
F(n)=eatimated total cost of path through n to goal
Best First Search can be recognized in two types:
Greedy search (F(n)=h(n))
A* search  (F(n)=g(n)+h(n))

I developed the following code to explain the concept of Best First Search Algorithms

public static void A_Star(Node1 Start, Node1 Goal, Hashtable h)
            PriorityQueue Fringe = new PriorityQueue();
            List<Node1> RepeatedNode = new List<Node1>();
            double g_Cost = 0.0;
            //double F_Cost = 0.0;
            Start.Fn= 0.0;
            while(Fringe.Count !=0)
                Node1 Current = (Node1)Fringe.Dequeue();
                Console.WriteLine("Node {0} Visited ", Current.Name);
                if (Current.Name == Goal.Name)
                    Console.WriteLine("Find Goal {0} Path Completed ", Current.Name);
                foreach (Node1 city in Current.Neghibors)
                    if (RepeatedNode.Contains(city))
                    g_Cost = city.cost + Current.cost;
                    city.Fn = g_Cost + (double)h[city];



No comments:

Post a Comment