tailieunhanh - Giáo trình Trí tuệ nhân tạo: Phần 2

Nối tiếp phần 1, giáo trình Trí tuệ nhân tạo - Phần 2 trang bị cho người học những kiến thức như: Các chiến lược tìm kiếm tối ưu, tìm kiếm có đối thủ, học máy (Machine Learning), tiếp cận kí hiệu, tiếp cận kết nối: Mạng neuron, tiếp cận xã hội và nổi trội: giải thuật di truyền (Genetic Algorithm - GA). | Chương V CÁC CHIÊN Lược TÌM KIÊM Tổl uu Vấn đề tìm kiếm tối ưu một cách tổng quát có thể phát biểu như sau. Mỗi đối tượng x trong không gian tìm kiếm được gắn với một số đo giá trị của đối tượng đó f x mục tiêu của ta là tìm đối tượng có giá trị f x lớn nhất hoặc nhỏ nhất trong không gian tìm kiếm. Hàm f x được gọi là hàm mục tiêu. Trong chương này chúng ta sẽ nghiên cứu các thuật toán tìm kiếm sau -I- Các kỹ thuật tìm đường đi ngắn nhất trong không gian trạng thái Thuật toán A thuật toán nhánh_và_cận. -I- Các kỹ thuật tìm kiếm đối tượng tốt nhất Tìm kiếm leo đổi tìm kiếm gradient tìm kiếm mô phỏng luyện kim. -I- Tìm kiếm bắt chước sự tiến hóa thuật toán di truyền. I. Tìm đường đi ngắn nhất Trong các chương trước chúng ta đã nghiên cứu vấn đề tìm kiếm đường đi từ trạng thái ban đầu tới trạng thái kết thúc trong không gian trạng thái. Trong mục này ta giả sử rằng giá phải trả để đưa trạng thái a tới trạng thái b bồi một toán tử nào đó là một số k a b 0 ta sẽ gọi số này là độ dài cung a b hoặc giá trị của cung a b trong đổ thị không gian trạng thái. Độ dài của các cung được xác định tùy thuộc vào vấn đề. Chẳng hạn trong bài toán tìm đường đi trong bản đổ giao thông giá của cung a b chính là độ dài của đường nối thành phố a với thành phố b. Độ dài đường đi được xác định là tổng độ dài của các cung trên đường đi. Vấn đề của chúng ta trong mục này tìm đường đi ngắn nhất từ trạng thái ban đầu tới trạng thái đích. Không gian tìm kiếm ồ đây bao gổm tất cả các đường đi từ trạng thái ban đầu tới trạng thái kết thúc hàm mục tiêu được xác định ồ đây là độ dài của đường đi. Chúng ta có thể giải quyết vấn đề đặt ra bằng cách tìm tất cả các đường đi có thể có từ trạng thái ban đầu tới trạng thái đích chẳng hạn sử sụng các kỹ thuật tìm kiếm mù sau đó so sánh độ dài của chúng ta sẽ tìm ra đường đi ngắn nhất. Thủ tục tìm kiếm này thường được gọi là thủ tục bảo tàng Anh Quốc British Museum Procedure . Trong thực tế kỹ thuật này không thể áp dụng được vì cây tìm kiếm thường rất lớn .