Thuật toán và giải thuật - Hoàng Kiếm Part 4

Chia sẻ: Mr Yukogaru | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

126
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật giải AT là một phương pháp tìm kiếm theo kiểu BFS với độ tốt của nút là giá trị hàm g - tổng chiều dài con đường đã đi từ trạng thái bắt đầu đến trạng thái hiện tại.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán và giải thuật - Hoàng Kiếm Part 4

Thu t gi i AT là m t phương pháp tìm ki m theo ki u BFS v i t t c a nút là giá tr hàm g – t ng chi u dài con ư ng ã i t tr ng thái b t u n tr ng thái hi n t i. Thu t gi i AT 1. t OPEN ch a tr ng thái kh i u. 2. Cho n khi tìm ư c tr ng thái ích ho c không còn nút nào trong OPEN, th c hi n : 2.a. Ch n tr ng thái (Tmax) có giá tr g nh nh t trong OPEN (và xóa Tmax kh i OPEN) 2.b. N u Tmax là tr ng thái k t thúc thì thoát. 2.c. Ngư c l i, t o ra các tr ng thái k ti p Tk có th có t tr ng thái Tmax. i v i m i tr ng thái k ti p Tk th c hi n : 22 Sưu t m b i: www.daihoc.com.vn
g(Tk) = g(Tmax) + cost(Tmax, Tk); Thêm Tk vào OPEN. * Vì ch s d ng hàm g (mà không dùng hàm ư c lư ng h’) fs ánh giá t tc a m t tr ng thái nên ta cũng có th xem AT ch là m t thu t toán. III.6. Thu t gi i AKT (Algorithm for Knowlegeable Tree Search) Thu t gi i AKT m r ng AT b ng cách s d ng thêm thông tin ư c lư ng h’. t t c a m t tr ng thái f là t ng c a hai hàm g và h’. Thu t gi i AKT 1. t OPEN ch a tr ng thái kh i u. 2. Cho n khi tìm ư c tr ng thái ích ho c không còn nút nào trong OPEN, th c hi n : 2.a. Ch n tr ng thái (Tmax) có giá tr f nh nh t trong OPEN (và xóa Tmax kh i OPEN) 2.b. N u Tmax là tr ng thái k t thúc thì thoát. 2.c. Ngư c l i, t o ra các tr ng thái k ti p Tk có th có t tr ng thái Tmax. i v i m i tr ng thái k ti p Tk th c hi n : g(Tk) = g(Tmax) + cost(Tmax, Tk); Tính h’(Tk) f(Tk) = g(Tk) + h’(Tk); Thêm Tk vào OPEN. III.7. Thu t gi i A* A* là m t phiên b n c bi t c a AKT áp d ng cho trư ng h p th . Thu t gi i A* có s d ng thêm t p h p CLOSE lưu tr nh ng trư ng h p ã ư c xét n. A* m r ng AKT b ng cách b sung cách gi i quy t trư ng h p khi "m " m t nút mà nút này ã có s n trong OPEN ho c CLOSE. Khi xét n m t tr ng thái Ti bên c nh vi c lưu tr 3 giá tr cơ b n g,h’, f’ ph n ánh t t c a tr ng thái ó, A* còn lưu tr thêm hai thông s sau : 1. Tr ng thái cha c a tr ng thái Ti (ký hi u là Cha(Ti) : cho bi t tr ng thái d n n tr ng thái Ti. Trong trư ng h p có nhi u tr ng thái d n n Ti thì ch n Cha(Ti) sao cho chi phí i t tr ng thái kh i u n Ti là th p nh t, nghĩa là : 23 Sưu t m b i: www.daihoc.com.vn
g(Ti) = g(Tcha) + cost(Tcha, Ti) là th p nh t. 2. Danh sách các tr ng thái k ti p c a Ti : danh sách này lưu tr các tr ng thái k ti p Tk c a Ti sao cho chi phí n Tk thông qua Ti t tr ng thái ban u là th p nh t. Th c ch t thì danh sách này có th ư c tính ra t thu c tính Cha c a các tr ng thái ư c lưu tr . Tuy nhiên, vi c tính toán này có th m t nhi u th i gian (khi t p OPEN, CLOSE ư c m r ng) nên ngư i ta thư ng lưu tr ra m t danh sách riêng. Trong thu t toán sau ây, chúng ta s không c p n vi c lưu tr danh sách này. Sau khi hi u rõ thu t toán, b n c có th d dàng i u ch nh l i thu t toán lưu tr thêm thu c tính này. 1. t OPEN ch ch a T0. t g(T0) = 0, h’(T0) = 0 và f’(T0) = 0. t CLOSE là t p h p r ng. 2. L p l i các bư c sau cho n khi g p i u ki n d ng. 2.a. N u OPEN r ng : bài toán vô nghi m, thoát. 2.b. Ngư c l i, ch n Tmax trong OPEN sao cho f’(Tmax) là nh nh t 2.b.1. L y Tmax ra kh i OPEN và ưa Tmax vào CLOSE. 2.b.2. N u Tmax chính là TG thì thoát và thông báo l i gi i là Tmax. 2.b.3. N u Tmax không ph i là TG. T o ra danh sách t t c các tr ng thái k ti p c a Tmax. G i m t tr ng thái này là Tk. V i m i Tk, làm các bư c sau : 2.b.3.1. Tính g(Tk) = g(Tmax) + cost(Tmax, Tk). 2.b.3.2. N u t n t i Tk’ trong OPEN trùng v i Tk. N u g(Tk) < g(Tk’) thì t g(Tk’) = g(Tk) Tính l i f’(Tk’) t Cha(Tk’) = Tmax 2.b.3.3. N u t n t i Tk’ trong CLOSE trùng v i Tk. N u g(Tk) < g(Tk’) thì t g(Tk’) = g(Tk) Tính l i f’(Tk’) 24 Sưu t m b i: www.daihoc.com.vn
t Cha(Tk’) = Tmax Lan truy n s thay i giá tr g, f’ cho t t c các tr ng thái k ti p c a Ti ( t t c các c p) ã ư c lưu tr trong CLOSE và OPEN. 2.b.3.4. N u Tk chưa xu t hi n trong c OPEN l n CLOSE thì : Thêm Tk vào OPEN Tính : f' (Tk) = g(Tk)+h’(Tk). Có m t s i m c n gi i thích trong thu t gi i này. u tiên là vi c sau khi ã tìm th y tr ng thái ích TG, làm sao xây d ng l i ư c "con ư ng" t T0 n TG. R t ơn gi n, b n ch c n l n ngư c theo thu c tính Cha c a các tr ng thái ã ư c lưu tr trong CLOSE cho n khi t n T0. ó chính là "con ư ng" t i ưu i t TG n T0 (hay nói cách khác là t T0 n TG). i m th hai là thao tác c p nh t l i g(Tk’) , f’(Tk’) và Cha(Tk’) trong bư c 2.b.3.2 và 2.b.3.3. Các thao tác này th hi n tư tư ng : "luôn ch n con ư ng t i ưu nh t". Như chúng ta ã bi t, giá tr g(Tk’) nh m lưu tr chi phí t i ưu th c s tính t T0 n Tk’. Do ó, n u chúng ta phát hi n th y m t "con ư ng" khác t t hơn thông qua Tk (có chi phí nh hơn) con ư ng hi n t i ư c lưu tr thì ta ph i ch n "con ư ng" m i t t hơn này. Trư ng h p 2.b.3.3 ph c t p hơn. Vì t Tk’ n m trong t p CLOSE nên t Tk’ ta ã lưu tr các tr ng thái con k ti p xu t phát t Tk’. Nhưng g(Tk’) thay id n n giá tr g c a các tr ng thái con này cũng ph i thay i theo. Và n lư t các tr ng thái con này l i có th có các các tr ng thái con ti p theo c a chúng và c th cho n khi m i nhánh k t thúc v i m t tr ng thái trong OPEN (nghĩa là không có tr ng thái con nào n a). th c hi n quá trình c p nh t này, ta hãy th c hi n quá trình duy t theo chi u sâu v i i m kh i u là Tk’. Duy t n âu, ta c p nh t l i g c a các tr ng thái n ó ( dùng công th c g(T) = g(Cha(T)) +cost(Cha(T), T) ) và vì th giá tr f’ c a các tr ng thái này cũng thay i theo. M t l n n a, xin nh c l i r ng, b n có th cho r ng t p OPEN lưu tr các tr ng thái "s ư c xem xét n sau" còn t p CLOSE lưu tr các tr ng thái " ã ư c xét n r i". Có th b n s c m th y khá lúng túng trư c m t thu t gi i dài như th . V n có l s tr nên sáng s a hơn khi b n quan sát các bư c gi i bài toán tìm ư ng i ng n nh t trên th b ng thu t gi i A* sau ây. III.8. Ví d minh h a ho t ng c a thu t gi i A* Chúng ta s minh h a ho t ng c a thu t gi i A* trong vi c tìm ki m ư ng i ng n nh t t thành ph Arad n thành ph Bucharest c a Romania. B n các thành ph c a Romania ư c cho trong th sau. Trong ó m i nh c a th c a là m t thành ph , gi a hai nh có cung n i nghĩa là có ư ng i gi a hai thành ph tương ng. Tr ng s c a cung chính là chi u dài (tính b ng km) c a ư ng i n i hai thành 25 Sưu t m b i: www.daihoc.com.vn
ph tương ng, chi u dài theo ư ng chim bay m t thành ph n Bucharest ư c cho trong b ng kèm theo. Hình : B ng c a Romania v i kho ng cách ư ng tính theo km B ng : Kho ng cách ư ng chim bay t m t thành ph n Bucharest. Chúng ta s ch n hàm h’ chính là kho ng cách ư ng chim bay cho trong b ng trên và hàm chi phí cost(Ti, Ti+1) chính là chi u dài con ư ng n i t thành ph Ti và Ti+1. Sau ây là t ng bư c ho t ng c a thu t toán A* trong vi c tìm ư ng i ng n nh t t Arad n Bucharest. Ban u: OPEN  {(Arad,g 0,h’ 0,f’ 0)} 26 Sưu t m b i: www.daihoc.com.vn
CLOSE  {} Do trong OPEN ch ch a m t thành ph duy nh t nên thành ph này s là thành ph t t nh t. Nghĩa là Tmax  Arad.Ta l y Arad ra kh i OPEN và ưa vào CLOSE. OPEN  {} CLOSE  {(Arad,g 0,h’ 0,f’ 0)} T Arad có th i n ư c 3 thành ph là Sibiu, Timisoara và Zerind. Ta l n lư t tính giá tr f’, g và h’ c a 3 thành ph này. Do c 3 nút m i t o ra này chưa có nút cha nên ban u nút cha c a chúng u là Arad. h’(Sibiu)  253 g(Sibiu)  g(Arad)+cost(Arad,Sibiu)  0+140 140 f’(Sibiu)  g(Sibiu)+h’(Sibiu)  140+253  393 Cha(Sibiu)  Arad h’(Timisoara)  329 g(Timisoara)  g(Arad)+cost(Arad, Timisoara)  0+118 118 f’(Timisoara)  g(Timisoara)+ h’(Timisoara)  118+329  447 Cha(Timisoara)  Arad h’(Zerind)  374 g(Zerind)  g(Arad)+cost(Arad, Zerind)  0+75 75 f’(Zerind)  g(Zerind)+h’(Zerind)  75+374  449 Cha(Zerind)  Arad 27 Sưu t m b i: www.daihoc.com.vn
Do c 3 nút Sibiu, Timisoara, Zerind u không có trong c OPEN và CLOSE nên ta b sung 3 nút này vào OPEN. OPEN  {(Sibiu,g 140,h’ 253,f’ 393,Cha Arad) (Timisoara,g 118,h’ 329,f’ 447,Cha Arad) (Zerind,g 75,h’ 374,f’ 449,Cha Arad)} CLOSE  {(Arad,g 0,h’ 0,f’ 0)} Hình : Bư c 1, nút ư c óng ngo c vuông (như [Arad]) là nút trong t p CLOSE, ngư c l i là trong t p OPEN. Trong t p OPEN, nút Sibiu là nút có giá tr f’ nh nh t nên ta s ch n Tmax  Sibiu. Ta l y Sibiu ra kh i OPEN và ưa vào CLOSE. OPEN  {(Timisoara,g 118,h’ 329,f’ 447,Cha Arad) (Zerind,g 75,h’ 374,f’ 449,Cha Arad)} CLOSE  {(Arad,g 0,h’ 0,f’ 0) (Sibiu,g 140,h’ 253,f’ 393,Cha Arad)} T Sibiu có th i n ư c 4 thành ph là : Arad, Fagaras, Oradea, Rimnicu. Ta l n lư t tính các giá tr g, h’, f’ cho các nút này. h’(Arad)  366 g(Arad)  g(Sibiu)+cost(Sibiu,Arad)  140+140 280 f’(Arad)  g(Arad)+h’(Arad)  280+366  646 h’(Fagaras)  178 g(Fagaras)  g(Sibiu)+cost(Sibiu, Fagaras)  140+99 239 28 Sưu t m b i: www.daihoc.com.vn