Lời Hay Ý Đẹp
Latest topics
» Tự học lập trình IOS trong vòng 24h
by kenanh 27/1/2014, 22:28

» xin tài liệu một số môn học
by nguyentvvan 21/8/2013, 21:34

» [Thảo luận] Bài toán đong nước
by giathinh9x 9/1/2013, 22:39

» Học Marketing Online, Học Chuyên viên Internet Marketing Online tại iNET
by NIIT-iNET 19/6/2012, 14:23

» Học PHP nâng cao, Học lập trình web với PHP nâng cao tại học viện iNET
by NIIT-iNET 19/6/2012, 14:22

» Học PHP, học lập trình web với PHP tại iNET vào ngày 19/07/2012
by NIIT-iNET 19/6/2012, 14:20

» PHIÊN BẢN MỚI CHO THIÊN ĐƯỜNG CÁ Ô LA LA !!!
by todaytv 13/3/2012, 15:35

» [hot] game khu vườn địa đàng phiên bản mobile của KVTM
by trantinh1713 3/1/2012, 15:20

» Đề tham khảo (update phút 90)
by ndc_2209 29/12/2011, 10:26

» Học bổng Lời Dịch tuần này.
by tienganh123 1/11/2011, 13:13

» [Thảo luận] Quản lý phân công giảng dạy PTTH
by huyquang0510 5/10/2011, 09:52

» Học tiếng Nhật - Top Globis
by tuquynh 21/9/2011, 10:35

» Học tiếng Nhật - Top Globis
by tuquynh 8/8/2011, 11:19

» Order Imitrex Online
by Khách viếng thăm 4/8/2011, 18:46

» Speeds Caffeine Metabolism Up
by Khách viếng thăm 4/8/2011, 18:12

» Skin For Good Caffeine
by Khách viếng thăm 3/8/2011, 14:54

» Cheap Pvc Figures
by Khách viếng thăm 1/8/2011, 19:32

» Action Rapid Onset Zolpidem Of
by Khách viếng thăm 31/7/2011, 01:13

» TUYỂN NHÂN VIÊN KINH DOANH ( làm việc tại văn phòng )
by canhkientp 5/7/2011, 14:59

» Demo + Vài điểm thảo luận về LINQ - Nhóm 7
by ChuongTienPhat 3/7/2011, 12:19


Thuật toán A*

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Thuật toán A*

Bài gửi by TranNgocSang on 6/12/2009, 10:25

Code:

void A(TrangThai xp,int dich,int b1,int b2,bool &flag,int &sl)
{
   //kiem tra coi diem xuat phat co trung voi diem dich chua?
   if(xp.b1 == dich || xp.b2 == dich)
   {
      flag = true;
      return;
   }
   
   //gan lai flag = 0 khi chua tim thay dich
   flag = false;
   
   //tao hang doi
   KhaiBaoHangDoi (Q);
   
   //tao mot bien trang thai de luu trang thai
   TrangThai a = xp;
   
   //Dua trang thai xuat phat vao hang doi
   DuaVaoHangDoi(Q,a);
   
   int i = 1;
      
   //Khi hang doi co phan tu thi chay
   while(Q.n > 0)
   {
      
      //lay phan tu co do uu tien nho nhat ra khoi hang doi
      TrangThai Min = LayRaKhoiHangDoi (Q) ;
      
      //So sanh phan tu moi duoc lay ra co trung voi dich hay khong?
      if(Min.b1 == dich || Min.b2 == dich)
      {
         //neu trung gan flag = true de bao hieu da tim thay dich roi
         flag = true;
         
         //luu gia tri dich do vao hang doi
         danhsachduyetroi[k] = Min ;
         k++;
         
         //tra ve khong chay nua
         return;
      }
      
      //nguoc lai van luu gia tri cua node vua lay ra vao hang doi
      danhsachduyetroi[k++] = Min  ;
      
      TrangThai Tam = Min ;

      //kiem tra truong hop 1
      if(Min.b1 < b1 )
      {
         Tam.b1 = b1 ;
         Tam.giatri = H(Tam) ;
         Tam.dinh = Tam.dinh * 10 + i ;
         i++;
         bool co = true;
         for(int j = 0 ; j < k ; j++)
         {
            //neu trang thai da duyet roi thi khong duyet nua nhe !
            if(danhsachduyetroi[j].b1 == Tam.b1 && danhsachduyetroi[j].b2 == Tam.b2 )
            {
               co = false ;
               break;
            }
         }
         if(co)
         {
         
            //kiem tra coi co trong hang doi chua?
            for(int i = 0 ; i < Q.n ; i++)
            {
               if(Q.mang[i].b1 == Tam.b1 && Q.mang[i].b2 == Tam.b2)
               {
                  co = false ;
                  break;
               }
            }
            //neu chua thi moi them zo
            if(co)
            {
               DuaVaoHangDoi(Q,Tam) ;
            }
         }
      }
      
      Tam  = Min;
      //kiem tra truong hop 2
      if(Min.b2 < b2 )
      {
         Tam.b2 = b2 ;
         Tam.giatri = H(Tam) ;
         Tam.dinh = Tam.dinh * 10 + i ;
         i++;
         bool co = true ;
         for(int j = 0 ; j < k ; j++)
         {
            //neu trang thai da duyet roi thi khong duyet nua nhe !
            if(danhsachduyetroi[j].b1 == Tam.b1 && danhsachduyetroi[j].b2 == Tam.b2 )
            {
               co = false ;
               break;
            }
            
         }
         if(co)
         {
      
            //kiem tra coi co trong hang doi chua?
            for(int i = 0 ; i < Q.n ; i++)
            {
               if(Q.mang[i].b1 == Tam.b1 && Q.mang[i].b2 == Tam.b2)
               {
                  co = false ;
                  break;
               }
            }
            //neu chua thi moi them zo
            if(co)
            {
               DuaVaoHangDoi(Q,Tam) ;
            }
         }
      }
      
      Tam  = Min;
      //kiem tra truong hop 3
      if(Min.b1 != 0 )
      {
         Tam.b1 = 0 ;
         Tam.giatri = H(Tam) ;
         Tam.dinh = Tam.dinh * 10 + i ;
         i++;
         bool co = true ;
         for(int j = 0 ; j < k ; j++)
         {
            //neu trang thai da duyet roi thi khong duyet nua nhe !
            if(danhsachduyetroi[j].b1 == Tam.b1 && danhsachduyetroi[j].b2 == Tam.b2 )
            {
               co = false ;
               break;
            }
         }
         if(co)
         {
         
            //kiem tra coi co trong hang doi chua?
            for(int i = 0 ; i < Q.n ; i++)
            {
               if(Q.mang[i].b1 == Tam.b1 && Q.mang[i].b2 == Tam.b2)
               {
                  co = false ;
                  break;
               }
            }
            //neu chua thi moi them zo
            if(co)
            {
               DuaVaoHangDoi(Q,Tam) ;
            }
         }
      }
      
      Tam  = Min;
      //kiem tra truong hop 4
      if(Min.b2 != 0 )
      {
         Tam.b2 = 0 ;
         Tam.giatri = H(Tam) ;
         Tam.dinh = Tam.dinh * 10 + i ;
         i++;
         bool co  = true ;
         for(int j = 0 ; j < k ; j++)
         {
            //neu trang thai da duyet roi thi khong duyet nua nhe !
            if(danhsachduyetroi[j].b1 == Tam.b1 && danhsachduyetroi[j].b2 == Tam.b2 )
            {
               co = false ;
               break;
            }
         }
         if(co)
         {
         
            //kiem tra coi co trong hang doi chua?
            for(int i = 0 ; i < Q.n ; i++)
            {
               if(Q.mang[i].b1 == Tam.b1 && Q.mang[i].b2 == Tam.b2)
               {
                  co = false ;
                  break;
               }
            }
            //neu chua thi moi them zo
            if(co)
            {
               DuaVaoHangDoi(Q,Tam) ;
            }
         }
      }
      
      Tam  = Min;
      //kiem tra truong hop 5
      if(Min.b1 > 0 && Min.b2 < b2 && Min.b1 > b2 - Min.b2 )
      {
         Tam.b1 = Tam.b1 - (b2 - Tam.b2);
         Tam.b2 = b2 ;
         Tam.giatri = H(Tam) ;
         Tam.dinh = Tam.dinh * 10 + i ;
         i++;
         bool co  = true;
         for(int j = 0 ; j < k ; j++)
         {
            //neu trang thai da duyet roi thi khong duyet nua nhe !
            if(danhsachduyetroi[j].b1 == Tam.b1 && danhsachduyetroi[j].b2 == Tam.b2 )
            {
               co = false ;
               break;
            }
         }
         if(co)
         {
         
            //kiem tra coi co trong hang doi chua?
            for(int i = 0 ; i < Q.n ; i++)
            {
               if(Q.mang[i].b1 == Tam.b1 && Q.mang[i].b2 == Tam.b2)
               {
                  co = false ;
                  break;
               }
            }
            //neu chua thi moi them zo
            if(co)
            {
               DuaVaoHangDoi(Q,Tam) ;
            }
         }
      }
      
      Tam  = Min;
      //kiem tra truong hop 6
      if(Min.b2 > 0 && Min.b1 < b1 && Min.b2 > b1 - Min.b1)
      {
         Tam.b2 = Tam.b2 - (b1 - Tam.b1) ;
         Tam.b1 = b1 ;
         Tam.giatri = H(Tam) ;
         Tam.dinh = Tam.dinh * 10 + i ;
         i++;
         bool co = true ;
         for(int j = 0 ; j < k ; j++)
         {
            //neu trang thai da duyet roi thi khong duyet nua nhe !
            if(danhsachduyetroi[j].b1 == Tam.b1 && danhsachduyetroi[j].b2 == Tam.b2 )
            {
               co = false ;
               break;
            }
         }
         if(co)
         {
         
            //kiem tra coi co trong hang doi chua?
            for(int i = 0 ; i < Q.n ; i++)
            {
               if(Q.mang[i].b1 == Tam.b1 && Q.mang[i].b2 == Tam.b2)
               {
                  co = false ;
                  break;
               }
            }
            //neu chua thi moi them zo
            if(co)
            {
               DuaVaoHangDoi(Q,Tam) ;
            }
         }
      }
      
      Tam  = Min;
      //kiem tra truong hop 7
      if(Min.b1 > 0 && Min.b2 < b2 && Min.b1 < b2 - Min.b2 )
      {
         Tam.b2 = Tam.b1 + Tam.b2 ;
         Tam.b1 = 0 ;
         Tam.giatri = H(Tam) ;
         Tam.dinh = Tam.dinh * 10 + i ;
         i++;
         bool co  = true ;
         for(int j = 0 ; j < k ; j++)
         {
            //neu trang thai da duyet roi thi khong duyet nua nhe !
            if(danhsachduyetroi[j].b1 == Tam.b1 && danhsachduyetroi[j].b2 == Tam.b2 )
            {
               co = false ;
               break;
            }
         }
         if(co)
         {
         
            //kiem tra coi co trong hang doi chua?
            for(int i = 0 ; i < Q.n ; i++)
            {
               if(Q.mang[i].b1 == Tam.b1 && Q.mang[i].b2 == Tam.b2)
               {
                  co = false ;
                  break;
               }
            }
            //neu chua thi moi them zo
            if(co)
            {
               DuaVaoHangDoi(Q,Tam) ;
            }
         }
      }
      
      Tam  = Min;
      //kiem tra truong hop 8
      if(Min.b2 > 0 && Min.b1 < b1 && Min.b2 < b1 - Min.b1 )
      {
         Tam.b1 = Tam.b2 + Tam.b1;
         Tam.b2 = 0 ;
         Tam.giatri = H(Tam) ;
         Tam.dinh = Tam.dinh * 10 + i ;
         i++;
         bool co = true ;
         for(int j = 0 ; j < k ; j++)
         {
            //neu trang thai da duyet roi thi khong duyet nua nhe !
            if(danhsachduyetroi[j].b1 == Tam.b1 && danhsachduyetroi[j].b2 == Tam.b2 )
            {
               co = false ;
               break;
            }
         }
         if(co)
         {
         
            //kiem tra coi co trong hang doi chua?
            for(int i = 0 ; i < Q.n ; i++)
            {
               if(Q.mang[i].b1 == Tam.b1 && Q.mang[i].b2 == Tam.b2)
               {
                  co = false ;
                  break;
               }
            }
            //neu chua thi moi them zo
            if(co)
            {
               DuaVaoHangDoi(Q,Tam) ;
            }
         }
      }
      sl = k;
   
   }
}
avatar
TranNgocSang

Nam
Tổng số bài gửi : 17
Age : 28
Registration date : 11/05/2009

Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết