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

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

Thêm vào BST

Báo xấu

102
lượt xem 34
download

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

Tìm kiếm chiếu sâu. trong tìm kiếm theo chiều sâu, tại trạng thái ( đỉnh) hiện hành , ta chọn một trạng thái kế tiếp ( trong tập các trạng thái có thể biến đổi thành trạng thái hiện tại) làm trạng thái hiện hành cho đến lúc trạng thái hiện hành là trạng thái đích.trong trường hợp trạng thái hiện hành

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 2

III.2.1. Tìm ki m chi u sâu (Depth-First Search) Trong tìm ki m theo chi u sâu, t i tr ng thái ( nh) hi n hành, ta ch n m t tr ng thái k ti p (trong t p các tr ng thái có th bi n i thành t tr ng thái hi n t i) làm tr ng thái hi n hành cho n lúc tr ng thái hi n hành là tr ng thái ích. Trong trư ng h p t i tr ng thái hi n hành, ta không th bi n i thành tr ng thái k ti p thì ta s quay lui (back-tracking) l i tr ng thái trư c tr ng thái hi n hành (tr ng thái bi n i thành tr ng thái hi n hành) ch n ư ng khác. N u tr ng thái trư c này mà cũng không th bi n i ư c n a thì ta quay lui l i tr ng thái trư c n a và c th . N u ã quay lui n tr ng thái kh i u mà v n th t b i thì k t lu n là không có l i gi i. Hình nh sau minh h a ho t ng c a tìm ki m theo chi u sâu. Hình : Hình nh c a tìm ki m chi u sâu. Nó ch lưu ý "m r ng" tr ng thái ư c ch n mà không "m r ng" các tr ng thái khác (nút màu tr ng trong hình v ). III.2.2. Tìm ki m chi u r ng (Breath-First Search) Ngư c l i v i tìm ki m theo ki u chi u sâu, tìm ki m chi u r ng mang hình nh c a v t d u loang. T tr ng thái ban u, ta xây d ng t p h p S bao g m các tr ng thái k ti p (mà t tr ng thái ban u có th bi n i thành). Sau ó, ng v i m i tr ng thái Tk trong t p S, ta xây d ng t p Sk bao g m các tr ng thái k ti p c a Tk r i l n lư t b sung các Sk vào S. Quá trình này c l p l i cho n lúc S có ch a tr ng thái k t thúc ho c S không thay i sau khi ã b sung t t c Sk. 8 Sưu t m b i: www.daihoc.com.vn
Hình : Hình nh c a tìm ki m chi u r ng. T i m t bư c, m i tr ng thái u ư cm r ng, không b sót tr ng thái nào. Chi u sâu Chi u r ng Tính hi u qu Hi u qu khi l i gi i n m Hi u qu khi l i gi i sâu trong cây tìm ki m và n m g n g c c a cây có m t phương án ch n tìm ki m. Hi u qu hư ng i chính xác. Hi u c a chi n lư c ph qu c a chi n lư c ph thu c vào sâu c a thu c vào phương án ch n l i gi i. L i gi i càng hư ng i. Phương án càng xa g c thì hi u qu kém hi u qu thì hi u qu c a chi n lư c càng c a chi n lư c càng gi m. gi m. Thu n l i khi Thu n l i khi mu n tìm ch mu n tìm nhi u l i m t l i gi i. gi i. Lư ng b nh s Ch lưu l i các tr ng thái Ph i lưu toàn b các d ng lưu tr các chưa xét n. tr ng thái. tr ng thái Trư ng h p x u Vét c n toàn b Vét c n toàn b . nh t Trư ng h p t t nh t Phương án ch n hư ng i Vét c n toàn b . tuy t i chính xác. L i gi i ư c xác nh m t cách tr c ti p. Tìm ki m chi u sâu và tìm ki m chi u r ng u là các phương pháp tìm ki m có h th ng và ch c ch n tìm ra l i gi i. Tuy nhiên, do b n ch t là vét c n nên v i nh ng bài toán có không gian l n thì ta không th dùng hai chi n lư c này ư c. Hơn n a, 9 Sưu t m b i: www.daihoc.com.vn
hai chi n lư c này u có tính ch t "mù quáng" vì chúng không chú ý n nh ng thông tin (tri th c) tr ng thái hi n th i và thông tin v ích c n t t i cùng m i quan h gi a chúng. Các tri th c này vô cùng quan tr ng và r t có ý nghĩa thi t k các thu t gi i hi u qu hơn mà ta s p s a bàn n. III.3. Tìm ki m leo i III.3.1. Leo i ơn gi n Tìm ki m leo i theo úng nghĩa, nói chung, th c ch t ch là m t trư ng h p c bi t c a tìm ki m theo chi u sâu nhưng không th quay lui. Trong tìm ki m leo i, vi c l a ch n tr ng thái ti p theo ư c quy t nh d a trên m t hàm Heuristic. Hàm Heuristic là gì ? Thu t ng "hàm Heuristic" mu n nói lên i u gì? Ch ng có gì ghê g m. B n ã quen v i nó r i! ó ơn gi n ch là m t ư c lư ng v kh năng d n n l i gi i tính t tr ng thái ó (kho ng cách gi a tr ng thái hi n t i và tr ng thái ích). Ta s quy ư c g i hàm này là h trong su t giáo trình này. ôi lúc ta cũng c p n chi phí t i ưu th c s t m t tr ng thái d n n l i gi i. Thông thư ng, giá tr này là không th tính toán ư c (vì tính ư c ng nghĩa là ã bi t con ư ng n l i gi i !) mà ta ch dùng nó như m t cơ s suy lu n v m t lý thuy t mà thôi ! Hàm h, ta quy ư c r ng, luôn tr ra k t qu là m t s không âm. b n c th c s n m ư c ý nghĩa c a hai hàm này, hãy quan sát hình sau trong ó minh h a chi phí t i ưu th c s và chi phí ư c lư ng. Hình Chi phí ư c lư ng h’ = 6 và chi phí t i ưu th c s h = 4+5 = 9 ( i theo ư ng 1-3-7) B n ang trong m t thành ph xa l mà không có b n trong tay và ta mu n i vào khu trung tâm? M t cách suy nghĩ ơn gi n, chúng ta s nh m vào hư ng nh ng tòa cao c c a khu trung tâm! Tư tư ng 1) N u tr ng thái b t u cũng là tr ng thái ích thì thoát và báo là ã tìm ư c l i gi i. Ngư c l i, t tr ng thái hi n hành (Ti) là tr ng thái kh i u (T0) 10 Sưu t m b i: www.daihoc.com.vn
2) L p l i cho n khi t n tr ng thái k t thúc ho c cho n khi không t n t i m t tr ng thái ti p theo h p l (Tk) c a tr ng thái hi n hành : a. t Tk là m t tr ng thái ti p theo h p l c a tr ng thái hi n hành Ti. b. ánh giá tr ng thái Tk m i : b.1. N u là tr ng thái k t thúc thì tr v tr này và thoát. b.2. N u không ph i là tr ng thái k t thúc nhưng t t hơn tr ng thái hi n hành thì c p nh t nó thành tr ng thái hi n hành. b.3. N u nó không t t hơn tr ng thái hi n hành thì ti p t c vòng l p. Mã gi Ti := T0; Stop :=FALSE; WHILE Stop=FALSE DO BEGIN IF Ti  TG THEN BEGIN ; Stop:=TRUE; END; ELSE BEGIN Better:=FALSE; WHILE (Better=FALSE) AND (STOP=FALSE) DO BEGIN IF THEN BEGIN ; Stop:=TRUE; END; ELSE BEGIN Tk := ; IF THEN BEGIN Ti :=Tk; Better:=TRUE; 11 Sưu t m b i: www.daihoc.com.vn
END; END; END; {WHILE} END; {ELSE} END;{WHILE} M nh "h’(Tk) t t hơn h’(Ti)" nghĩa là gì? ây là m t khái ni m chung chung. Khi cài t thu t gi i, ta ph i cung c p m t nh nghĩa tư ng minh v t t hơn. Trong m t s trư ng h p, t t hơn là nh hơn : h’(Tk) < h’(Ti); m t s trư ng h p khác t t hơn là l n hơn h’(Tk) > h’(Ti)...Ch ng h n, i v i bài toán tìm ư ng i ng n nh t gi a hai i m. N u dùng hàm h’ là hàm cho ra kho ng cách theo ư ng chim bay gi a v trí hi n t i (tr ng thái hi n t i) và ích n (tr ng thái ích) thì t t hơn nghĩa là nh hơn. V n c n làm rõ k ti p là th nào là ? M t tr ng thái k ti p h p l là tr ng thái chưa ư c xét n. Gi s h c a tr ng thái hi n t i Ti có giá tr là h(Ti) = 1.23 và t Ti ta có th bi n i sang m t trong 3 tr ng thái k ti p l n lư t là Tk1, Tk2, Tk3 v i giá tr các hàm h tương ng là h(Tk1) = 1.67, h(Tk2) = 2.52, h’(Tk3) = 1.04. u tiên, Tk s ư c gán b ng Tk1, nhưng vì h’(Tk) = h’(Tk1) > h’(Ti) nên Tk không ư c ch n. K ti p là Tk s ư c gán b ng Tk2 và cũng không ư c ch n. Cu i cùng thì Tk3 ư c ch n. Nhưng gi s h’(Tk3) = 1.3 thì c Tk3 cũng không ư c ch n và m nh s có giá tr TRUE. Gi i thích này có v hi n nhiên nhưng có l c n thi t tránh nh m l n cho b n c. th y rõ ho t ng c a thu t gi i leo i. Ta hãy xét m t bài toán minh h a sau. Cho 4 kh i l p phương gi ng nhau A, B, C, D. Trong ó các m t (M1), (M2), (M3), (M4), (M5), (M6) có th ư c tô b ng 1 trong 6 màu (1), (2), (3), (4), (5), (6). Ban u các kh i l p phương ư c x p vào m t hàng. M i m t bư c, ta ch ư c xoay m t kh i l p phương quanh m t tr c (X,Y,Z) 900 theo chi u b t kỳ (nghĩa là ngư c chi u hay thu n chi u kim ng h cũng ư c). Hãy xác nh s bư c quay ít nh t sao cho t t c các m t c a kh i l p phương trên 4 m t c a hàng là có cùng màu như hình v . 12 Sưu t m b i: www.daihoc.com.vn
Hình : Bài toán 4 kh i l p phương gi i quy t v n , trư c h t ta c n nh nghĩa m t hàm G dùng ánh giá m t tình tr ng c th có ph i là l i gi i hay không? B n c có th d dàng ưa ra m t cài t c a hàm G như sau : IF (Gtrái + Gph i + Gtrên + Gdư i + Gtrư c + Gsau) = 16 THEN G:=TRUE ELSE G:=FALSE; Trong ó, Gph i là s lư ng các m t có cùng màu c a m t bên ph i c a hàng. Tương t cho Gtrái, Gtrên, Ggi a, Gtrư c, Gsau. Tuy nhiên, do các kh i l p phương A,B,C,D là hoàn toàn tương t nhau nên tương quan gi a các m t c a m i kh i là gi ng nhau. Do ó, n u có 2 m t không i nhau trên hàng ng màu thì 4 m t còn l i c a hàng cũng ng màu. T ó ta ch c n hàm G ư c nh nghĩa như sau là : IF Gph i + Gdư i = 8 THEN G:=TRUE ELSE G:=FALSE; Hàm h (ư c lư ng kh năng d n n l i gi i c a m t tr ng thái) s ư c nh nghĩa như sau : h = Gtrái + Gph i + Gtrên + Gdư i Bài toán này ơn gi n thu t gi i leo i có th ho t ng t t. Tuy nhiên, không ph i lúc nào ta cũng may m n như th ! n ây, có th chúng ta s n y sinh m t ý tư ng. N u ã ch n tr ng thái t t hơn làm tr ng thái hi n t i thì t i sao không ch n tr ng thái t t nh t ? Như v y, có l ta s nhanh chóng d n nl i gi i hơn! Ta s bàn lu n v v n : "li u c i ti n này có th c s giúp chúng ta d n n l i gi i nhanh hơn hay không?" ngay sau khi trình bày xong thu t gi i leo id c ng. III.3.2. Leo id c ng V cơ b n, leo id c ng cũng gi ng như leo i, ch khác i m là leo id 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 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). 13 Sưu t m b i: www.daihoc.com.vn
Tư tư ng 1) N u tr ng thái b t u cũng là tr ng thái ích thì thoát và báo là ã tìm ư c l i gi i. Ngư c l i, t tr ng thái hi n hành (Ti) là tr ng thái kh i u (T0) 2) L p l i cho n khi t n tr ng thái k t thúc ho c cho n khi (Ti) không t n t i m t tr ng thái k ti p (Tk) nào t t hơn tr ng thái hi n t i (Ti) a) t S b ng t p t t c tr ng thái k ti p có th có c a Ti và t t hơn Ti. b) Xác nh Tkmax là tr ng thái t t nh t trong t p S t Ti = Tkmax Mã gi Ti := T0; Stop :=FALSE; WHILE Stop=FALSE DO BEGIN IF Ti  TG THEN BEGIN ; STOP :=TRUE; END; ELSE BEGIN Best:=h’(Ti); Tmax := Ti; WHILE DO BEGIN Tk := ; IF THEN BEGIN Best :=h’(Tk); Tmax := Tk; END; 14 Sưu t m b i: www.daihoc.com.vn
END; IF (Best>Ti) THEN Ti := Tmax; ELSE BEGIN ; STOP:=TRUE; END; END; {ELSE IF} END;{WHILE STOP}