Thuật giải AT, AKT

Giống như leo đồi đơn giản, chỉ khác ở điểm là leo đồi dốc đứng sẽ duyệt tất cả các hướng đi có thể và chọn đi theo trạng thái tốt nhất trong số các trạng thái kế tiếp có thể có (trong khi đó leo đồi đơn giản chỉ chọn đi theo trạng thái kế tiếp đầu tiên tốt hơn trạng thái hiện hành mà nó tìm thấy).
Nội dung trích xuất từ tài liệu:
Thuật giải AT, AKT ThuậtgiảiAT,AKT ThuậtgiảiAT(AlgorithmforTree): Mỗiđỉnhntươngứngvớimộtsốg(n):giáthànhcủađườngđitừđỉnhbanđầuđếnđỉnhn. Đỉnh: +Đỉnhđóng(Closed):lànhữngđỉnhđãđượcxemxét. +Đỉnhmở(Open) :lànhữngđỉnhgiảthiếtsẽđượcxemxétởbướcsau. +Đỉnhẩn(Hiden) :lànhữngđỉnhmàtạiđóhàmg(n)chưađượcxácđịnh. ThuậtgiảiATBước1:+Mọiđỉnhn,mọigiátrịg(n)đềulàẩn.+MởđỉnhđầutiênvàgọiđólàđỉnhS.Đặtg(S)=0.Bước2:ChọnđỉnhmởvớigiáthànhgtươngứnglànhỏnhấtvàgọiđólàđỉnhN.+NếuNlàmụctiêu:đườngđitừđỉnhbanđầuđếnNlàđườngđingắnnhấtvàbằng g(N).Dừng(Success).+Nếukhôngtồntạimộtđỉnhmởnàonữa:câybiểudiễnvấnđềkhôngcóđườngđitới mụctiêu.Dừng(Fail).+Nếutồntạinhiềuhơn1đỉnhN(nghĩalàcó2đỉnhNtrởlên)màcócùnggiáthành g(N)nhỏnhất.Kiểmtraxemtrongsốđócóđỉnhnàolàđíchhaykhông.Nếucó:đườngđitừđỉnhbanđầuđếnđỉnhNlàngắnnhấtvàbằngg(N),dừng (Success).Nếukhôngcó:ChọnngẫunhiênmộttrongcácđỉnhđóvàgọilàđỉnhN.Bước3:ĐóngđỉnhNvàmởcácđỉnhsauN(lànhữngđỉnhcócunghướngtừNtới).Tại mọiđỉnhSsauNtính:g(S)=g(N)+cost(N→S)Bước4:Quaylạibước2 ThuậtgiảiATVídụ 100 1 17 1 D B C A 1 10 20 12 1 1 G H I J E F 1 1 1 1 K N L M 1 1 O P 1 1 Q R 1 1S T 1 T r a ïn g t h a ù ñ í c h i U 1 V ThuậtgiảiATVídụMọiđỉnhn,g(n)chưabiết.B1:MởS,đặtg(S)=0. 100 1B2:ĐóngS;mởA,B,C,D 17 1 D B C Ag(A)=g(S)+gt(S→A)=0+100=100 1 10 20 12 1 1 G H I J Eg(B)=0+17=17 F 1 1 1 1 K Ng(C)=g(D)=0+1=1(min) L M 1 1 O PChọnngẫunhiêngiữaC,D:chọnC 1 1 Q RB3:ĐóngC,mởG,H: 1 1 S Tg(A)=100 1 T r a ïn g t h a ù ñ í c h i Ug(B)=17 1 Vg(D)=1(min)g(G)=11g(H)=21 ThuậtgiảiATVídụB4:ĐóngD,mởI,J: 100 1g(A)=100 17 1 Dg(B)=17 B C A ...