Thuật toán A*

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