Bài giảng về Trí tuệ nhân tạo

- Các chiến lƣợc tìm kiếm mù.
- Biểu diễn vấn đề trong không gian trạng thái 01.
- Các chiến lược tìm kiếm 01.
- Các chiến lược tìm kiếm mù 02.
- Tìm kiếm theo bề rộng 1.3.2.
- Tìm kiếm theo độ sâu 1.3.3.
- Các trạng thái lặp 1.3.4.
- Tìm kiếm sâu lặp.
- Tìm kiếm tốt nhất đầu tiên 01.
- Tìm kiếm leo đồi 01.
- Tìm kiếm beam 01.
- Thuật toán tìm kiếm nhánh – và - cận.
- Tìm kiếm leo đồi 3.2.2.
- Tìm kiếm gradient.
- Tìm kiếm có đối thủ.
- PHầN I: GIảI QUYếT VấN Đề BằNG TÌM KIếM.
- Các kỹ thuật tìm kiếm tối ưu..
- tìm kiếm theo bề rộng (breadth-first search) và tìm kiếm theo độ sâu (depth-first search).
- 1.1 Biểu diễn vấn đề trong không gian trạng thái.
- Trạng thái ban đầu..
- Ta sẽ ký hiệu không gian trạng thái là U, trạng thái ban đầu là u 0 (u 0  U).
- Một tập hợp T các trạng thái kết thúc (trạng thái đích).
- Trạng thái ban đầu là (3, 3, 1)..
- Trạng thái kết thúc là (0, 0, 0)..
- 1.2 Các chiến lƣợc tìm kiếm.
- Tập T các trạng thái kết thúc.
- Quá trình áp dụng các toán tử để sinh ra các trạng thái kề u được gọi là phát triển trạng thái u.
- Các chiến lược tìm kiếm mù.
- Tìm kiếm kinh nghiệm (tìm kiếm heuristic).
- Như vậy chiến lược tìm kiếm được xác định bởi chiến lược chọn trạng thái để phát triển ở mỗi bước.
- Trong tìm kiếm mù, ta chọn trạng thái để phát triển theo thứ tự mà đúng được sinh ra.
- còn trong tìm kiếm kinh nghiệm ta chọn trạng thái dựa vào sự đánh giá các trạng thái..
- 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.
- Mỗi chiến lược tìm kiếm trong không gian trạng thái tương ứng với một phương pháp xây dựng cây tìm kiếm.
- Kỹ thuật tìm kiếm theo bề rộng (theo độ sâu) tương ứng với phương pháp xây dựng cây tìm kiếm theo bề rộng (theo độ sâu)..
- 1.3 Các chiến lƣợc tìm kiếm mù.
- 1.3.1 Tìm kiếm theo bề rộng.
- Khởi tạo danh sách L chỉ chứa trạng thái ban đầu;.
- 7 2.2 Loại trạng thái u ở đầu danh sách L;.
- 2.3 if u là trạng thái kết thúc then.
- {thông báo tìm kiếm thành công.
- Đánh giá tìm kiếm theo bề rộng.
- 1.3.2 Tìm kiếm theo độ sâu.
- 1.3.3 Các trạng thái lặp.
- Chẳng hạn, trong cây tìm kiếm hình 4b, các trạng thái C, E, F là các trạng thái lặp.
- Vì vậy trong quá trình tìm kiếm ta cần tránh phát sinh ra các trạng thái mà ta đã phát triển.
- 1.3.4 Tìm kiếm sâu lặp.
- Khởi tạo danh sách L chỉ chứa trạng thái ban đầu u 0 .
- 2.2 Loại trạng thái u ở đầu danh sách L;.
- 2.3 if u là trạng thái kết thúc then {thông báo thành công.
- for mỗi trạng thái v kề u do.
- Trong tìm kiếm sâu lặp, ta phải phát triển lặp lại nhiều lần cùng một trạng thái.
- Chúng ta có thể biểu diễn việc quy một vấn đề về các vấn đề con cơ bởi các trạng thái.
- ở đây, bài toán cần giải là trạng thái ban đầu.
- Các trạng thái kết thúc là các bài toán sơ cấp (các bài toán đã biết cách giải).
- Ví dụ: Giả sử chúng ta có không gian trạng thái sau:.
- Trạng thái ban đầu (bài toán cần giải) là a..
- Tập các trạng thái kết thúc (các bài toán sơ cấp) là T = {b, c, e, j, l}..
- Không gian trạng thái trên có thể biểu diễn bởi đồ thị và/hoặc trong hình 1.9.
- Trong chương I, chúng ta đã nghiên cứu việc biểu diễn vấn đề trong không gian trạng thái và các kỹ thuật tìm kiếm mù.
- Hàm đánh giá và tìm kiếm kinh nghiệm:.
- Tìm biểu diễn thích hợp mô tả các trạng thái và các toán tử của vấn đề..
- Chúng ta có xây dựng được hàm đánh giá cho ta sự đánh giá đúng các trạng thái thì tìm kiếm mới hiệu quả.
- Tìm kiếm tốt nhất - đầu tiên:.
- Đến đây ta đã đạt tới trạng thái kết thúc.
- 2.4 for mỗi trạng thái v kề u do.
- Tìm kiếm leo đồi:.
- Ví dụ: Ta lại xét đồ thị không gian trạng thái trong hình 2.2.
- Quá trình tìm kiếm kết thúc..
- trạng thái u, khi ta phát triển u.
- 2.3 for mỗi trạng thái v kề u do đặt v vào L 1.
- Tìm kiếm beam.
- Ví dụ: Chúng ta lại xét đồ thị không gian trạng thái trong hình 2.2.
- 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.
- Giả sử u là một trạng thái đạt tới (có dường đi từ trạng thái ban đầu u 0 tới u).
- h(u) là đánh giá độ dài đường đi ngắn nhất từ u tới trạng thái đích..
- Hàm h(u) được gọi là chấp nhận được (hoặc đánh giá thấp) nếu với mọi trạng thái u, h(u.
- độ dài đường đi ngắn nhất thực tế từ u tới trạng thái đích.
- Ta có thể sử dụng kỹ thuật tìm kiếm leo đồi với hàm đánh giá h(u).
- 2.4 for mỗi trạng thái v kề u do {g(v.
- Giả sử thuật toán dừng lại ở đỉnh kết thúc G với độ dài đường đi từ trạng thái ban đầu u 0.
- 1.5.2 Thuật toán tìm kiếm nhánh-và-cận..
- Ví dụ: Chúng ta lại xét không gian trạng thái trong hình 3.1.
- Cây tìm kiếm được biểu diễn trong hình 3.4..
- 25 2.3 if u là trạng thái kết thúc then.
- 2.5 for mỗi trạng thái v kề u do {g(v.
- 1.6.1 Tìm kiếm leo đồi.
- 1.6.2 Tìm kiếm gradient.
- 1.6.3 Tìm kiếm mô phỏng luyện kim:.
- Nếu trạng thái v được chọn tốt hơn u (cost(v) >.
- u  trạng thái ban đầu nào đó;.
- v  trạng thái được chọn nhẫu nhiên trong lân cận u;.
- Chơi cờ có thể xem như vấn đề tìm kiếm trong không gian trạng thái..
- Chiến lược tìm kiếm nước đi Minimax..
- Vấn đề chơi cờ có thể xem như vấn đề tìm kiếm trong không gian trạng thái.
- Mỗi trạng thái là một tình thế (sự bố trí các quân của hai bên trên bàn cờ)..
- Gốc của cây ứng với trạng thái ban đầu.
- Ta sẽ gọi đỉnh ứng với trạng thái mà Trắng (Đen) đưa ra nước đi là đỉnh Trắng (Đen)

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt