Tri tu nhan to
➤ Gửi thông báo lỗi ⚠️ Báo cáo tài liệu vi phạmNội dung chi tiết: Tri tu nhan to
Tri tu nhan to
I.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quát Tri tu nhan to t, có thê hiểu lả tìm một đối tượng thỏa màn một số đòi hòi nào đó. trong một tập hợp rộng lớn các đôi tương. Chúng ta có thê kè ra rất nhiều vấn đề mã việc giãi quyết nó được quy về van đề tìm kiếm.Các trò chơi, chẳng hạn cờ vua. cờ carò có thê xem như vấn đề tim kiếm. Trong số rắt nhiều nước đi đư Tri tu nhan to ơc phép thực hiện, ta phài tim ra các nước đi dần tới tình the kết cuộc mà ta là người thăng.Chứng minh định lý cũng có thê xem như van đe tìm kiêm. CTri tu nhan to
ho một tập các tiên đe và các luật suy diẻn. trong trường hợp này mục tiêu cua ta là tim ra một chứng minh (một dày các luật suy diễn được áp dụng) đêI.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quát Tri tu nhan to m Đặc biệt trong lập kế hoạch và học máy, tìm kiêm đóng vai trò quan trọng.Trong phan này chúng ta sẽ nghiên cửu các kỳ- thuật tim kiếm cơ bân được áp dung đê giai quyết các van đe vã đươc áp dụng rộng rài trong các lĩnh vực nghiên cứu khác cua Tri Tuệ Nhân Tạo. Chúng ta lần lượt nghiên cứu các kỳ t Tri tu nhan to huật sau:z Các kỳ thuật tim kiếm mù. trong đó chủng ta không có hiểu biết gì về các đôi tirợng đê hướng dần tim kiếm mà chì đơn thuần Là xem xét theoTri tu nhan to
một hệ thông nào đó tat cả các đối tượng đê phát hiện ra đối tượng cần tìm.z Các kỳ thuật tim kiêm kinh nghiệm (tìm kiêm heuristic) trong đó chúng ta I.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quát Tri tu nhan to i ưu.z Các phương pháp tìm kiếm có đỗi thú. tức Là các chiến lươc tim kiêm nước đi trong các trò chơi hai người, chăng hạn cờ vua. cờ tướng, cở carò.Chương 1Các chiến lược tìm kiếm mùTrong chương nãy. chúng tôi sè nghiên cứu các chiến lược tìm kiếm mũ (blind search): lìm kiềm theo bê rộng (breadth-f Tri tu nhan to irst search) và lim kiêm theo độ sâu (depth-first search). Iliệu qua cua các phương pháp tim kiếm này cùng sè dược đánh giá.1.1 Biêu diễn vấn để trongTri tu nhan to
không gian trạng tháiMỘI khi chúng líi muôn giãi quy cl một vân đê nào đó báng lìm kiêm, đâu liên la phái xác định không gian lìm kiêm. Không gian lìI.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quát Tri tu nhan to g có the là không gian các đôi tượng rời rạc.Trong mục này ta sê xét việc biểu diễn một vấn dề trong không gian trạng thái sao cho việc giãi quyết vân đề được quy vê việc tim kiếm trong không gian trạng thãi.Một phạm vi rộng lớn các vẩn đề. đặc biệt các câu đố. các trò chơi, có thế mò tà bang cách s Tri tu nhan to ư dung khái niệm trạng thái và toán từ (phép biên đôi trạng thái). Chăng hạn. một khách du lịch có trong tay bân đo mạng lưới giao thông nôi các thànhTri tu nhan to
phố trong một vùng lành thô (hình 1.1), du khách đang ơ thành phố A và anh ta muốn tim đường đi tới thâm thành phố B Trong bài toán này. các thành phI.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quát Tri tu nhan to D anh ta có thè đi theo các con đường đê nôi ten các thành phô c, F và (ì. Các con đường nòi các thành phố sè dược biêu điền bơi các toán tư. Một toán từ biến dổi một trạng thái thành một trạng thái khác. Châng hạn, ỡ trạng thái I) SC có ba toán lữ dan trạng thái D tỡi các trạng thái C. F và G. vấn Tri tu nhan to dề cùa du khách bây giở sè Là tim một dày toán tữ đê đưa trạng thái ban đâu A ten trạng thái kêl thúc B.Một ví dụ khác, trong trô chơi cờ vua, moi cáTri tu nhan to
ch bô trí các quàn trên bàn cờ là một trạng thái. Trạng thái ban dầu lã sự sắp xếp các quân lúc bắt dầu cuộc choi. Mỗi nước đi hợp lệ là một toán lữ, I.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quát Tri tu nhan to u tố sau:z Trạng thái ban dầu.z Một tập họp các toán từ. Trong dó mỗi toán tư mò ta một hành dộng hoặc một phép bicn đôi có thê đưa một trạng thái t(h một trạng thái khác.Tập hợp tất cá các trạng thái có thê đạt tới tử trọng thái ban đầu bảng cách áp dụng một dày toán tử. lập thành không gian trạng Tri tu nhan to thái của van để.Ta sẽ ký hiệu không gian trạng thái là ư. trạng thái ban dầu là U(j (Uộ € ư). Mồi toán tử R có thê xem như một ánh xạ R: U—>ư. Nói chuTri tu nhan to
ng R lã một ánh xạ không xác định khắp nơi trên ư.□ Một tập hợp T các trạng thái kết thúc (trạng thái đích). T là tập con cùa không gian ư. Trong van I.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quát Tri tu nhan to vả la không thê xác định trước dược các trạng thái đích. NÓI chung trong phần lớn các van đề hay. ta chi có thẻ mô tà các trạng thái đích là các trạng thái thòa màn một số điều kiện nào đóKhi chúng ta biêu diễn một vấn đề thông qua các trạng thái và các toán từ. thì việc tìm nghiệm của bãi toán được Tri tu nhan to quy vê việc tim dường di từ trạng thái ban đâu tới trạng thái đích (Một đường đi trong không gian trạng thái là một dày toán tư dản một trạng thái lớTri tu nhan to
i một trạng thái khác).Hình l.l Tìm dường di từ A dến BChúng ta có thê biêu diễn không gian trạng thái băng đồ thị định hướng, trong đó mồi đinh cua đI.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quát Tri tu nhan to mót đường đi trong không gian trạng thái sẽ là một đường đi trong đo thị này.Sau đày chùng ta sê xét một số ví dụ về các không gian trạng thái dược xây dựng cho một so van đề.Vi dụ ỉ: Bài toán 8 số. Chúng ta có bâng 3x3 ô và tám quân mang so hiệu từ 1 đen 8 được xếp vào tám ô. còn Lại một ô trông, c Tri tu nhan to hăng hạn như trong hình 2 bênI.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quátI.Đinh Mạnh TườngGiáo trìnhTrí tuê Nhân taoKhoa CNTT - Đại Học Quốc Gia Hà NộiPhần IGiải quyết vấn để bàng tim kiếmVẩn đề tim kiếm, một cách tông quátGọi ngay
Chat zalo
Facebook