Tuesday, March 27, 2012

A* vs Greedy Algorithms

A* visited Nodes on the above Figure in order start>a>b>d>e>Goal

Greedy visited Nodes on the above Figure in order start>a>b>c>Goal

I coded A* and Greedy Algorithms to show the order of visited Nodes on the above figure

Downloaded Link :

Uninformed Search Algorithms (Code Implementation)

v      Breadth First Search (BFS)
v      Uniform Cost Search (UCS)
v      Depth First Search (DFS)
v      Depth Limited Search (DLS)
v      Iterative Deepening Search (IDS)
v      Bidirectional Search (BS)
I implemented all of these algorithms to my students during AI sections through 2011,2012
I uploaded my code to help any person wants to learn AI algorithms and to share knowlege among people in the world
Downloaded Link:

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];