» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Bài giảng Trí tuệ nhân tạo: Các chiến lược tìm kiếm - Trường Đại học Thủy Lợi

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:86

Báo xấu

25
lượt xem 2
download

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

Bài giảng “Trí tuệ nhân tạo”, một môn cơ sở chuyên ngành trong chương trình đào tạo cử nhân tin học, ngoài mục đích xây dựng nhiều bài giảng trên một khung chương trình đào tạo, mà còn giúp cho sinh viên có tài liệu học tập phù hợp với hoàn cảnh thực tế của Đại học Thủy Lợi. Nội dung Chương 2b của tài liệu trình bày Giải quyết vấn đề bằng tìm kiếm.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Trí tuệ nhân tạo: Các chiến lược tìm kiếm - Trường Đại học Thủy Lợi

Các chiến lược tìm kiếm I. Các chiến lược tìm kiếm II. Các chiến lược tìm kiếm mù - Tìm kiếm theo bề rộng, tìm kiếm theo độ sâu, tìm kiếm theo độ sâu hạn chế, tìm kiếm sâu lặp. III. Các chiến lược tìm kiếm kinh nghiệm - Hàm đánh giá, tìm kiếm tốt nhất đầu tiên, tìm kiếm leo đồi, tìm kiếm A*, tìm kiếm nhánh cận. IV. Tìm kiếm có đối thủ - Cây trò chơi, chiến lược tìm kiếm minimax, phương pháp cắt tỉa alpha-beta. 1
I. Các chiến lược tìm kiếm • Khi ta biểu diễn một vấn đề cần giải quyết thông qua các trạng thái và các toán tử thì việc tìm lời giải của vấn đề được quy về việc tìm đường đi từ trạng thái ban đầu tới một trạng thái kết thúc • Có thể phân các chiến lược tìm kiếm thành hai loại: – Các chiến lược tìm kiếm mù – Các chiến lược tìm kiếm kinh nghiệm (tìm kiếm heuristic). 2
Các chiến lược tìm kiếm • Các chiến lược tìm kiếm mù – Trong các chiến lược tìm kiếm này, không có một sự hướng dẫn nào cho việc tìm kiếm, mà ta chỉ phát triển các trạng thái ban đầu cho tới khi gặp một trạng thái đích nào đó. – Có hai kỹ thuật tìm kiếm mù đó là tìm kiếm theo bề rộng và tìm kiếm theo độ sâu. – Khi sử dụng các chiến lược tìm kiếm mù thì số lượng các trạng thái được phát triển trước khi ta gặp trạng thái đích thường cực kỳ lớn. Do đó các thuật toán tìm kiếm mù kém hiệu quả, đòi hỏi rất nhiều không gian và thời gian. 3
Các chiến lược tìm kiếm • Các chiến lược tìm kiếm kinh nghiệm – Trong rất nhiều vấn đề chúng ta có thể dựa vào sự hiểu biết của chúng ta về vấn đề, dựa vào kinh nghiệm, trực giác, để đánh giá các trạng thái. – Sử dụng sự đánh giá các trạng thái để hướng dẫn sự tìm kiếm: trong quá trình phát triển các trạng thái, ta sẽ chọn trong số các trạng thái chờ phát triển, trạng thái được đánh giá tốt nhất để phát triển. Do đó tốc độ tìm kiếm sẽ nhanh hơn. – Các phương pháp tìm kiếm dựa vào sự đánh giá các trạng thái để hướng dẫn sự tìm kiếm gọi chung là các phương pháp tìm kiếm kinh nghiệm. 4
Cây tìm kiếm • Quá trình tìm kiếm là quá trình xây dựng cây tìm kiếm. Cây tìm kiếm là cây mà các đỉnh được gắn bởi các trạng thái của không gian trạng thái. Gốc của cây tìm kiếm tương ứng với trạng thái ban đầu. • Có thể chuyển vấn đề tìm kiếm đồ thị thành vấn đề tìm kiếm trên cây (hình dưới). 5
Các chiến lược tìm kiếm • Một chiến lược tìm kiếm được xác định bằng việc lựa chọn thứ tự phát triển các nút • Các chiến lược tìm kiếm được đánh giá dựa trên các tiêu chí sau đây: – tính hoàn thành: nó có luôn tìm ra nghiệm nếu thực sự có nghiệm? – độ phức tạp thời gian: số lượng các nút được tạo ra – độ phức tạp không gian: số lượng lớn nhất các nút trong bộ nhớ – tính tối ưu: nó có luôn tìm thấy nghiệm có giá thấp nhất? • Độ phức tạp thời gian và không gian được tính toán dựa trên – b: nhân tố nhánh lớn nhất của cây tìm kiếm – d: độ sâu của nghiệm có giá thấp nhất – m: độ sâu lớn nhất của không gian trạng thái (có thể là ∞) 6
II. Các chiến lược tìm kiếm mù • Các chiến lược tìm kiếm mù: chỉ sử dụng thông tin được cung cấp trong định nghĩa vấn đề • Tìm kiếm theo bề rộng (Breadth-first search) • Tìm kiếm theo độ sâu (Depth-first search) • Tìm kiếm độ sâu hạn chế (Depth-limited search) • Tìm kiếm sâu lặp (Iterative deepening search 7
Tìm kiếm theo bề rộng • Tư tưởng của tìm kiếm theo bề rộng là các trạng thái được phát triển theo thứ tự mà chúng được sinh ra, tức là trạng thái nào được sinh ra trước sẽ được phát triển trước • Thuật toán: 8
Tìm kiếm theo bề rộng • Phát triển nút nông nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào cuối danh sách chờ phát triển 9
Tìm kiếm theo bề rộng • Phát triển nút nông nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào cuối danh sách chờ phát triển 10
Tìm kiếm theo bề rộng • Phát triển nút nông nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào cuối danh sách chờ phát triển 11
Tìm kiếm theo bề rộng • Phát triển nút nông nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào cuối danh sách chờ phát triển 12
Tìm kiếm theo bề rộng • Hoàn thành? Chắc chắn sẽ tìm ra nghiệm nếu bài toán có nghiệm (nếu b là hữu hạn) • Thời gian? 1+b+b2+b3+… +bd + b(bd-1) = O(bd+1) • Không gian? O(bd+1) (luôn giữ tất cả các nút trong bộ nhớ) • Tối ưu? Thuật toán là tối ưu nếu giá = 1 ở mỗi bước • Không gian là vấn đề quan trọng hơn thời gian 13
Tìm kiếm theo độ sâu • Tư tưởng của tìm kiếm theo bề sâu là, tại mỗi bước trạng thái được chọn để phát triển là trạng thái được sinh ra sau cùng trong số các trạng thái chờ phát triển. • Thuật toán: 14
Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 15
Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 16
Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 17
Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 18
Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 19
Tìm kiếm theo độ sâu • Phát triển nút sâu nhất chưa được phát triển • Thực hiện: Nút mới tiếp theo sẽ được đặt vào đầu danh sách chờ phát triển 20

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2009-2019 TaiLieu.VN. All rights reserved.