Nhập môn Trí tuệ nhân tạo-Bài 2

NHẬP MÔN TRÍ TUỆ NHÂN TẠO
@copyrights by Dr Nguyễn Xuân Hoài
Nội Dung
Giải quyết vấn đề:
Một số vấn đề về giải quyết vấn đề.
Biểu diễn không gian lời giải bằng không gian trạng thái.
Giải quyết vấn đề bằng tìm kiếm.
Tìm kiếm cơ bản không dựa vào thông tin thu thập trong quá trình tìm kiếm: (uninformed/blind search).
Breadth-first search
Uniform-cost search
Depth-first search
Depth-limited search
Iterative deepening search
Giải quyết vấn đề
Giải quyết vấn đề là gì?

Để giải quyết vấn đề:
Phát biểu chính xác bài toán (Hiện trạng ban đầu, kết quả mong muốn,..)
Phân tích bài toán.
Thu thập và biểu diễn dữ liệu, tri thức cần thiết để giải bài toán.
Lựa chọn kỹ thuật giải quyết thích hợp.
Không gian trạng thái
Ví dụ: Tìm đường đi, Robot xếp hình, Máy hút bụi tự động, tính tích phân bất định, chương trình chơi cờ, chương trình chuẩn đoán bệnh, chương trình nhận dạng vân tay, mặt người, chương trình tự sản sinh ra chương trình máy tính...
Đi nghỉ tại Romania; hiện ở Arad.
+ Trạng thái hiện thời: Tại Arad.
+ Trạng thái đích: Tới Bucharest
+Biểu diễn dưới dạng không gian trạng thái:
trạngthái: tại các thành phố khác nhau
hành động: lái xe đến các thành phố khác nhau.
+ Tìm lời giải: Chuỗi các thành phố, từ Arad, đến Bucharest.
Không gian trạng thái
Không gian trạng thái
Không gian trạng thái
Yếu tố xác định không gian TT
Trạng thái.
Hành động.
Kiểm tra trạng thái thoả đích.
Chi phí cho mỗi bước chuyển trạng thái.
Không gian trạng thái
Không gian trạng thái
Các đặc trưng của vấn đề
Tính khả tách.
Có thể huỷ bỏ hay lần ngược bước giải?
Không gian bài toán có đoán định được trước? (sau mỗi bước giải).
Cần lời giải tốt hay tối ưu?
Lời giải là trạng thái hay dãy chuyển trạng thái?
Vai trò của tri thức?
Quá trình giải có cần tương tác người máy?
Phân loại vấn đề
Giải quyết vấn đề
Tìm kiếm trên cây trạng thái
Ý tưởng cơ bản:
Tìm kiếm trên không gian trạng thái dưới dạng cây, dùng toán tử EXPAND sinh các trạng thái có thể đến được trực tiếp từ một trạng thái đã được kiểm tra (trạng thái con).
Ví dụ
Ví dụ
Ví dụ
Khung tìm kiếm tổng quát
Trạng thái vs. Nodes
Chiến lược tìm kiếm
Chiến lược tìm kiếm là chiến lược lựa chọn thứ tự xét các nodes tạo ra bởi toán tử Expand
Các tiêu chuẩn để đáng giá chiến lược :
đủ : Liệu có tìm được lời giải (nếu có)?
độ phức tạp thời gian: số lượng node phải xét.
độ phức tạp lưu trữ: Tổng dung lượng bộ nhớ phải lưu trữ (các nodes trong quá trình tìm kiếm.
tối ưu: Có luôn cho lời giải tối ưu.
Độ phực tạp thời gian vàlưu trữ của bài toán có thể được đo bằng:
b: Độ phân nhánh của cây
d: Độ sâu của lời giải ngắn nhất
m: Độ sâu tối đa của không gian trạng thái (có thể vô hạn).
Các chiến lược tìm kiếm yếu (weak/uninformed/blind search)
Những chiến thuật tìm kiếm chỉ sử dụng thông tin từ định nghĩa của bài toán:

Tìm kiếm theo chiều rộng
Tìm kiếm đều giá (uniform-cost search).
Tím kiếm theo chiều sâu.
Tìm kiếm theo chiều sâu có hạn
Tìm kiếm sâu dần.
Tìm kiếm theo chiều rộng
Tìm kiếm theo từng tầng. Expand node gần nút nhất.
Cài đặt:
fringe (danh sách các node chờ được duyệt) được cài đặt dưới dạng danh sách FIFO, i.e., Các node con được sinh ra (bởi EXPAND) sẽ được đặt ở dưới cùng của fringe.
Tìm kiếm theo chiều rộng
Tìm kiếm theo từng tầng. Expand node gần nút nhất.
Cài đặt:
fringe (danh sách các node chờ được duyệt) được cài đặt dưới dạng danh sách FIFO, i.e., Các node con được sinh ra (bởi EXPAND) sẽ được đặt ở dưới cùng của fringe.
Tìm kiếm theo chiều rộng
Tìm kiếm theo từng tầng. Expand node gần nút nhất.
Cài đặt:
fringe (danh sách các node chờ được duyệt) được cài đặt dưới dạng danh sách FIFO, i.e., Các node con được sinh ra (bởi EXPAND) sẽ được đặt ở dưới cùng của fringe.
Tìm kiếm theo chiều rộng
Tìm kiếm theo từng tầng. Expand node gần nút nhất.
Cài đặt:
fringe (danh sách các node chờ được duyệt) được cài đặt dưới dạng danh sách FIFO, i.e., Các node con được sinh ra (bởi EXPAND) sẽ được đặt ở dưới cùng của fringe.
Đánh giá tìm kiếm BFS
đủ? có (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) (lưu mọi node của cây).
tối ưu? có (giải thiết giá của mỗi bước chuyển là 1)


Không gian lưu trữ hết sức tốn kém là vấn đề lớn nhất đối vơi BFS !!!
Tìm kiếm đều giá
Xét node có giá tìm kiếm nhỏ nhất trước.
Cài đặt:
fringe = Hàng đợi có ưu tiên (bằng nghịch dấu giá thành)
Tương đương với BFS nếu các node có giá như nhau.
Đủ ? có nếu cost ≥ ε

Thời gian? Số lượng nodes với g ≤ giá của lời giải tối ưu, O(bceiling(C*/ ε)) trong đó C* là giá của lời giải tối ưu.
Không gian? số lượng nodes với g ≤ giá của lời giải tối ưu, O(bceiling(C*/ ε)).
Tối ưu? Có – nodes được EXPAND theo thứ tự tăng dần của g(n).
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle

Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Tìm kiếm theo chiều sâu
EXPAND node chưa xét ở sâu nhất.
Cài đặt:
fringe = danh sách kiểu LIFO, i.e., Đẩy các nodes con sinh bởi EXPAND vào đầu fringle
Đánh giá tìm kiếm DFS
Đủ? không đủ (không gian vô hạn hoặc loop)
- Nếu sửa để tránh trùng lặp  đủ trong không gian hữu hạn.
Thời gian? O(bm)
- Rất xấu nếu m lớn hơn nhiều so với d.
- Nhưng nếu mật độ lời giải trong không gian lớn thì có thể nhanh hơn BFS.
Không gian? O(bm), i.e., Độ phức tạp tuyến tính
Tối ưu? không
Tìm kiếm với độ sâu giới hạn
= DFS với độ sâu giới hạn là l, i.e., nodes tại độ sâu l không có node con (successor-fn trả về rỗng).
Cài đặt:
Tìm Kiếm Sâu Dần
Tìm kiếm sâu dần l =0
Tìm kiếm sâu dần l =1
Tìm kiếm sâu dần l =2
Tìm kiếm sâu dần l =3
Tìm kiếm sâu dần
Đánh giá tìm kiếm sâu dần
Đủ ? Có.
Thời gian? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd).
Không gian? O(bd).
Tối ưu? Có, nếu giá mỗi bước = 1.
Tóm tắt các chiến lược tìm kiếm
Trạng thái bị trùng lặp
Việc không xử lý tốt các trạng thái bị lặp nhiều lần có thể làm cho độ phức tạp (thời gian, không gian) bị bùng nổ tổ hợp.
Tìm kiếm trên đồ thị
Tóm tắt
Để giải quyết vấn đề cần phân tích các �