Sara El-Sayed El-Metwally: May 2011

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

Part IV: Uniform Cost Search

v Uniform Cost Search

public static void Uniform_Cost_Search(Node Start,Node Goal)

            GetSucc x = new GetSucc();

            ArrayList children = new ArrayList();

            PriorityQueue Fringe = new PriorityQueue();

            Fringe.Enqueue(Start);

            while (Fringe.Count != 0)

                Node Parent = (Node)Fringe.Dequeue();

                Console.WriteLine("Node {0} Visited with Cost {1} ", Parent.State,Parent.Cost);

                if (Parent.State == Goal.State)

                    Console.WriteLine();

                    Console.WriteLine("Find Goal   " + Parent.State);

                    break;

                }//end if

                children = x.GetSussessor(Parent.State,Parent);

                for (int i = 0; i < children.Count; i++)

                    Fringe.Enqueue((Node)children[i]);

                }//end for

            }//end while

        }// end method

Part III: Breadth First Search

Lets from here begin to code the uninformed Search Strategies:

v Breadth First Search

public static void Breadth_First_Search(Node Start, Node Goal)

            GetSucc x = new GetSucc();

            ArrayList children = new ArrayList();

            Queue Fringe = new Queue();

            Fringe.Enqueue(Start);

            while (Fringe.Count != 0)

                Node Parent = (Node)Fringe.Dequeue();

                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.Enqueue(Tem);

                }//end for

            }//end while

        }//end method

AI- Simple Implementation of Uninformed Search Strategies- PartII

My code search for a number in the range from 0, 1, 2, .N. so, the initial state is 0 and the goal state is the number specified by the user. Each step of number generation costs random number or 1. Class GetSucc.cs define GetSussessor() function which inculdes the possible set of actions that are required for positive number generation inorder. The input of GetSussessor () is the current state of the problem (i.e. initial State 0) and the output is the ArrayList of next states that are reached from current state(i.e. from 0 the next states 1,2 assuming that our tree is the binary tree).

class GetSucc

       //if search go forward from 0 to number n

        public ArrayList GetSussessor(int State)

            ArrayList Result = new ArrayList();

            Result.Add(2 * State + 1);

            Result.Add(2 * State + 2);

            return Result;

       //if search go backward from n to number 0

        public ArrayList GetSussessor_Reverse(int State)

            ArrayList Result = new ArrayList();

            if (State % 2 == 0)

                int P = State / 2 - 1;

                Result.Add(P);

                Result.Add(State - 1);

            else

                int Sib = State + 1;

                Result.Add(Sib / 2 - 1);

                Result.Add(Sib);

            return Result;

        //if the cost of each node must be determined

 public ArrayList GetSussessor(int State,Node Parent)

            ArrayList Result = new ArrayList();

            Random n = new Random();

            Test s = new Test();

 Result.Add(new Node(2* State + 1,Parent,n.Next(1,100)+Parent.Cost));

 Result.Add(new Node(2* State + 2, Parent,n.Next(1,100) + Parent.Cost));

            Result.Sort(s);

            return Result;

}//end class

//implement the interface IComparer to compare objects in ArrayList

    public class Test : IComparer

        public int Compare(object x, object y)

            int val1 = ((Node)x).Cost;

            int val2 = ((Node)y).Cost;

            if (val1 <= val2)

                return 1;

            else

                return 0;

    }//end class Test

Sunday, May 29, 2011

AI- Simple Implementation of Uninformed Search Strategies - Part I

The first class in my code is Node.cs which represents the node as a data structure in the state space. Each node has some attributes such as depth, cost, state, and parent node. The state attribute is defined according to a physical configuration within the problem state space. My code is simply search for a number in the state space of positive numbers so the state here is defined simply as an integer number.

Lets explore the Node class by the following snippet:

// class Node.cs

class Node

      public  int depth;

      public  int State;

      public  int Cost;

      public  Node Parent;

 // Parent Node  which has depth =0 and parent = null;

      public Node (int State)

              this.State = State;

              this.Parent = null;

              this.depth = 0;

// another form of Node Costructor which accepts only the State;

      public Node(int State)

            this.State = State;

            // this form of Generalization of Node Constructor which accept any node root or ordinary node;

      public Node(int State,Node Parent)

            this.State = State;

            this.Parent = Parent;

            if (Parent == null)

                this.depth = 0;

              else

                this.depth = Parent.depth + 1;

     // this form of Generalization of Node Constructor which accept any node root or ordinary node and  accept the cost of each node;

      public Node(int State, Node Parent, int Cost)

            this.State = State;

            this.Parent = Parent;

            this.Cost = Cost;

            if (Parent == null)

               this.depth = 0;

              else

               this.depth = Parent.depth + 1;