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 :
                                  http://www.mediafire.com/?9tt7ld7frkjxwy4

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:
               http://www.mediafire.com/?hl2cvtp44xm981r

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
Note:
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

[code]
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;
            Fringe.Enqueue(Start);
            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);
                    break;
                }
                RepeatedNode.Add(Current);
                foreach (Node1 city in Current.Neghibors)
                {
                    if (RepeatedNode.Contains(city))
                    {
                        continue;
                    }
                    g_Cost = city.cost + Current.cost;
                    city.Fn = g_Cost + (double)h[city];
                    Fringe.Enqueue(city);
               
               
                }


           
           
           
           
           
           
            }
       
       
        }[/code]


 

Monday, May 30, 2011

Part VIII : Bidirectional Search

v      Bidirectional Search
public static void Bidirectional_Search(Node Start,Node Goal)
        {
            GetSucc x = new GetSucc();
            ArrayList Children_1 = new ArrayList();
            ArrayList Children_2 = new ArrayList();
            Queue Fringe_IN = new Queue();
            Queue Fringe_GO = new Queue();
            Fringe_IN.Enqueue(Start);
            Fringe_GO.Enqueue(Goal);
            while((Fringe_IN.Count !=0)&&(Fringe_GO.Count!=0))
            {
                Node Parent1 = (Node)Fringe_IN.Dequeue();
                Console.WriteLine("Node {0} Visited ", Parent1.State);
                //Console.ReadKey();
                if ((Parent1.State == Goal.State)||Contain(Fringe_GO,Parent1))
                {
                    Console.WriteLine();
                    Console.WriteLine("Find Goal   " + Parent1.State);
                    break;
                }//end if
                Children_1 = x.GetSussessor(Parent1.State);
                for (int i = 0; i < Children_1.Count; i++)
                {
                    int State = (int)Children_1[i];
                    Node Tem = new Node(State, Parent1);
                    Fringe_IN.Enqueue(Tem);
                }//end for
                Node Parent2 = (Node)Fringe_GO.Dequeue();
                Console.WriteLine("Node {0} Visited ", Parent2.State);
                //Console.ReadKey();
                if ((Parent2.State == Start.State) || Contain(Fringe_IN,Parent2))
                {
                    Console.WriteLine();
                    Console.WriteLine("Find Goal   " + Parent2.State);
                    break;
                }//end if
                Children_2 = x.GetSussessor_Reverse(Parent2.State);
                for (int i = 0; i < Children_2.Count; i++)
                {
                    int State = (int)Children_2[i];
                    Node Tem = new Node(State, Parent2);
                    Fringe_GO.Enqueue(Tem);
                }//end for
            
            
            }//end while
        
        }//End Method
public static bool Contain(Queue Fringe,Node Parent)
        {
            object[] S = new object[Fringe.Count];
            S = Fringe.ToArray();
            for (int i = 0; i < S.Length; i++)
            {
                Node Target = (Node)S[i];
                if (Target.State == Parent.State)
                {
                    return true;
                
                }
            
            }
            return false;
        
        }

Part VII : Iterative Deepening Search

v      Iterative Deepening Search
public static void Iterative_Deepening_Search(Node Start, Node Goal)
        {
            bool Cutt_off = false;
            int depth = 0;
            while(Cutt_off == false)
            {
                Console.WriteLine("Search Goal at Depth {0}",depth);
                Depth_Limited_Search(Start, Goal, depth,ref Cutt_off);
                Console.WriteLine("-----------------------------");
                depth++;
            }
        
        
        }//end method
public static void Depth_Limited_Search(Node Start, Node Goal,int depth_Limite,ref bool Cut_off)
        {
            GetSucc x = new GetSucc();
            ArrayList children = new ArrayList();
            Stack Fringe = new Stack();
            Fringe.Push(Start);
            while (Fringe.Count != 0)
            {
                Node Parent = (Node)Fringe.Pop();
                Console.WriteLine("Node {0} Visited ", Parent.State);
                // Console.ReadKey();
                if (Parent.State == Goal.State)
                {
                    Console.WriteLine();
                    Console.WriteLine("Find Goal   " + Parent.State);
                    Cut_off = true;
                    break;
                }//end if
                if (Parent.depth == depth_Limite)
                {
                    continue;
                }
                else
                {
                    children = x.GetSussessor(Parent.State);
                    for (int i = 0; i < children.Count; i++)
                    {
                        int State = (int)children[i];
                        Node Tem = new Node(State, Parent);
                        Fringe.Push(Tem);
                    }//end for
                }//end else
               
            }//end while
        }//end method

Part VI :Depth Limited Search

v      Depth Limited Search
public static void Depth_Limited_Search(Node Start, Node Goal, int depth_Limite)
        {
            GetSucc x = new GetSucc();
            ArrayList children = new ArrayList();
            Stack Fringe = new Stack();
            Fringe.Push(Start);
            while (Fringe.Count != 0)
            {
                Node Parent = (Node)Fringe.Pop();
                Console.WriteLine("Node {0} Visited ", Parent.State);
                // Console.ReadKey();
                if (Parent.State == Goal.State)
                {
                    Console.WriteLine();
                    Console.WriteLine("Find Goal   " + Parent.State);
                    break;
                }//end if
                if (Parent.depth == depth_Limite)
                {
                    continue;
                }
                else
                {
                    children = x.GetSussessor(Parent.State);
                    for (int i = 0; i < children.Count; i++)
                    {
                        int State = (int)children[i];
                        Node Tem = new Node(State, Parent);
                        Fringe.Push(Tem);
                    }//end for
                }//end else
            }//end while
        }//end method

Part V :Depth First Search

v      Depth First Search
public static void Depth_First_Search(Node Start, Node Goal)
        {
            GetSucc x = new GetSucc();
            ArrayList children = new ArrayList();
            Stack Fringe = new Stack();
            Fringe.Push(Start);
            while (Fringe.Count != 0)
            {
                Node Parent = (Node)Fringe.Pop();
                Console.WriteLine("Node {0} Visited ", Parent.State);
                Console.ReadKey();
                if (Parent.State == Goal.State)
                {
                    Console.WriteLine();
                    Console.WriteLine("Find Goal   " + Parent.State);
                    break;
                }//end if
                children = x.GetSussessor(Parent.State);
                for (int i = 0; i < children.Count; i++)
                {
                    int State = (int)children[i];
                    Node Tem = new Node(State, Parent);
                    Fringe.Push(Tem);
                }//end for
            }//end while
        }//end method