Hẳn khi các bạn tìm hiểu về phần 1 sách cũng đã cảm nhận được giáo trình thật sự giúp tích trong việc làm quen với một số kiến thức cơ bản nhất về các phương pháp tìm kiếm lời giải và các phương pháp xử lý tri thức. Ngoài ra, cuốn sách cũng giới thiệu một số chương trình cài đặt, nhằm giúp sinh viên có thể hiểu một cách tường tận các giải thuật, đồng thời tin tưởng rằng các giải thuật này có thể áp dụng thực tế và cài đặt được trên máy tính một cách dễ dàng. tiếp phần 2 sách với 3 nội dung: Phân rã bài toán - Tìm kiếm lời giải trên đồ thị và/hoặc, biểu diễn bài toán bằng logic và các phương pháp chứng minh, tri thức và các phương pháp suy diễn. Mời các bạn tham khảo tiếp phần 2 giáo trình. | Chương 3 PHÂN RÃ BÀI TOÁN - TÌM KIẾM LỜI GIẢI TRÊN ĐỒ THỊ VÀ/ HOẶC 1. Đặt vấn đề. Trong chương 2, chúng ta đã nghiên cứu việc biểu diễn bài toán thông qua các trạng thái và các toán tử. Khi đó việc tìm lời giải của bài toán được quy về việc tìm đường đi trong không gian trạng thái. Trong chương này chúng ta sẽ nghiên cứu một phương pháp luận khác để giải quyết vấn đề, dựa trên việc quy vấn đề về các vấn đề con. Ý tưởng chủ yếu là xuất phát từ bài toán ban đầu, tách ra các bài toán con, quá trình này tiếp tục đối với các bài toán con cho đến khi gặp các bài toán sơ cấp (bài toán có lời giải ngay). Ví dụ 1. Xét bài toán tính tích phân x(ln x x 2 ) dx . Thông thường để tính tích phân bất định, chúng ta thường sử dụng các quy tắc tính tích phân: tích phân của tổng, quy tắc tích phân từng phần hay các phép biến đổi để đưa tích phân cần tính về tích phân của các hàm số sơ cấp mà chúng ta đã biết cách tính. Đối với tích phân trên, áp dụng quy tắc tích phân của tổng ta đưa về hai tích phân xlnxdx và tích phân x3dx. Áp dụng quy tắc tích phân từng phần ta đưa tích phân xlnx về tích phân xdx. Quá trình trên có thể biểu diễn bởi đồ thị trong Hình 1. x(lnx+x2)dx x3dx xlnxdx xdx Hình 1. 90 Trong bài toán tích phân, các tích phân cơ bản là các trạng thái kết thúc. Ví dụ 2. Bài toán tìm đường đi trên bản đồ giao thông. Bài toán này đã được phát biểu như bài toán tìm đương đi trong không gian trạng thái, trong đó mỗi trạng thái ứng với một thành phố, mỗi toán tử ứng với một con đường, nối thành phố này với thành phố khác. Bây giờ ta đưa ra một cách bểu diễn khác dựa trên việc quy vấn đề về các vấn đề con Xét bản đồ giao thông giữa các thành phố trong Hình 2. A C D F E I H G B K Hình 2. Giả sử ta cần tìm đường đi từ thành phố A đến thành phố B. Có một con sông chảy qua hai thành phố E và G và có cầu qua sông ở mỗi thành phố đó. Như vậy mọi đường đi từ A đến B đều phải đi qua E hoặc G. Khi đó bài toán tìm đường đi từ A đến B được quy về một trong hai .
