tailieunhanh - Tri tuệ nhân tạo part 2

Tham khảo tài liệu 'tri tuệ nhân tạo part 2', kỹ thuật - công nghệ, tự động hoá phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Phán Ị. GIẢI QUYẾT VẤN ĐẾ BANG ĨÌM KIẾM 31 Kỹ thuật lìm kiếm sâu lạp kêt hộp du cic các ưu diểm eúa tìm kiêm theo bồ rộng và lìm kiêm theo iộ sàu. hung ta có một sô nhận xéĩ sau Cũng nhu tìm kiêm th 0 bế cộng lìm kiêm sáu lặp luôn luôn tìm ra nghiệm Ini ll bài toán có nghiệm miễn 1 1 ta chọn dộ sâu max hi lớn. Tìm kiêm nâu lạp chi cán không gian nhớ nhu tìm kiêm thno độ sâu. Trong tìm kiêm sâu lụp. In phái phát trien lạp lại nhiều lan cùng mội trạng thái. Điều dó làm cho la có cam giác rang lun kiem sáu lạp lăng phí n hl cu thbi gian. Thục ra thòi gian Liêu tôn cho phát triên lặp ạI các Irạng thái là khùng dáng kè so VÓI ihói gian lìm kiêm theo bố rộng. Thật vậy. mồi lan gọi thú tục tìm kiêm sâu hạn chê lói mức í nêu cày tim kiêm có nhân lô nhánh là b. thì sô dinh c ìn phát Irion lù 1 -1 h b -Ì-. t ó l Xêu iiLÙiiộm ó dộ sáu ị. tro. tìm- kiêm sâiì lặp. la phai gọi thu Lục tìm kièm sau hạn che VÓI độ sáu lan lúọt là 0. 1. 2. d. Do do các đình ó mức 1 phai phát tricii ạp d lần. cac dính ó mức 2 lạp í -l lan. các dinh ơ mức d lặp 1 iin. Xhư vậy tòng sô đinh can phát trien trong tìm kiêm sâu lặp là UM Dl db d- D - 1 . 2b 1D l i dó thòi gian tìm kiêm sâu ãp là OpT . Tóm lại. lìm kiêm sâu ạp ó dọ phúc tạp till d gian là O b lỊ í 11 hư tìm kiêm theo bề rộng và ó dộ phức tạp không gian 1 à i bd inhu kiêm theo dộ sâu . Xói chung chúng ta nén áp dụng tìm tíiêm sàu lạp cho các van dề có khùng gian trạng thái lớn và dộ sáu cúa nghiệm không biét triíóc. . QUY VẤN ĐỂ VỂ CÁC VẤN ĐÊ con. tìm kiếm trên Đổ THỊ VÀ HOẶC . Quy vân đế về các vân đế con Trotậ mục . chúng m dã nghiên cửu việc bleu diễn vãn dế thòng qua các trạng thai và các toán tủ. Khi dó VIộc tìm nghiệm cua v m dề dưọc quv về việc tun dường trong không gian trạng thái. Trong mục này chúng ta sẽ nghiên CUU một phiíong pháp luận khác de giài quvêt ván 32 TRÍ TUỆ NHÂN TẠO đề dựa trên việc quy vấn đề về các vấn đế con. Quỵ vấn để về các vấn đê con còn gọi ì à rút gọn vấn để là một phương pháp dược sử .