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

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
Nội dung trích xuất từ tài liệu:
Thuật toán và giải thuật - Hoàng Kiếm Part 2III.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 ngthá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àmtr 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. Trongtrư 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 pthì 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áibi 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àymà 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à cth . 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 av 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áik ti p (mà t tr ng thái ban u có th bi n i thành). Sau ó, ng v i m i tr ngthá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 nlư 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áik 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.vnHì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ó hth 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 ngbà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.vnhai chi n lư c này u có tính ch t mù quáng vì chúng không chú ý n nh ngthô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 iquan 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 tk 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 iIII.3.1. Leo i ơn gi nTìm ki m leo i theo úng nghĩa, nói chung, th c ch t ch là m t trư ng h p cbi 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 ã quenv 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 ttr 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 ư cg 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ôngth tính toán ư c (vì tính ư c ng nghĩa là ã bi t con ư ng n l i gi i !) mà tach 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 ư cr ng, luôn tr ra k t qu là m t s không âm. ...