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