5.2 Các dạng bài toán CSP và nguyên tắc giải bài toán này



Có ít nhất hai cách để giải bài toán CSP bằng cách giải thuật tìm kiếm đã nghiên cứu.
1/ Cách 1: khi mô hình qua bài toán tìm kiếm, biểu diễn một trạng thái trong không gian tìm kiếm sao cho nó chứa thông tin của tất cả n biến của bài toán CSP (complete-state representation).
2/ Cách 2: mỗi trạng thái chỉ chứa thông tin của một biến được chọn để xem xét.
Cách 1 là không khả thi vì số lượng nốt lá (nghiệm sẽ là một trong những nốt lá có chiều sâu là n) lớn quá một cách không cần thiết: (n!d^n)
Cách 2 có vẻ khả quan hơn. Tuy nhiên, nếu không áp dụng các kinh nghiệm (heuristic) vào thì nó vẫn không khả thi: O(d^n) trong trường hợp không may mắn!

Nguồn: https://gizmondolive.com/

Xem thêm bài viết khác: https://gizmondolive.com/category/cong-nghe

No comments yet, be the first!

Comments

Your email address will not be published. Required fields are marked *