Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình Trí tuệ Nhân tạo part 4

trong tìm kiếm theo bề rộng ta lần lượt phát triển tất cả các đỉnh ở mức hiện tại để sinh ra các đỉnh ở mức tiếp theo, còn trong tìm kiếm tốt nhất - đầu tiên ta chọn đỉnh để phát triển là đỉnh tốt nhất được xác định bởi hàm đánh giá (tức là đỉnh có giá trị hàm đánh giá là nhỏ nhất), đỉnh này có thể ở mức hiện tại hoặc ở các mức trên. | bề rộng ở chỗ trong tìm kiếm theo bề rộng ta lần lượt phát triển tất cả các đỉnh ở mức hiện tại để sinh ra các đỉnh ở mức tiếp theo còn trong tìm kiếm tốt nhất - đầu tiên ta chọn đỉnh để phát triển là đỉnh tốt nhất được xác định Hình 2.2 Đo thị không gian trạng thái bởi hàm đánh giá tức là đỉnh có giá trị hàm đánh giá là nhỏ nhất đỉnh này có thể ở mức hiện tại hoặc ở các mức trên. Ví dụ Xét không gian trạng thái được biểu diễn bởi đồ thị trong hình 2.2 trong đó trạng thái ban đầu là A trạng thái kết thúc là B. Giá trị của hàm đánh giá là các số ghi cạnh mỗi đỉnh. Quá trình tìm kiếm tốt nhất - đầu tiên diễn ra như sau Đầu tiên phát triển đỉnh A sinh ra các đỉnh kề là C D và E. Trong ba đỉnh này đỉnh D có giá trị hàm đánh giá nhỏ nhất nó được chọn để phát triển và sinh ra F I. Trong số các đỉnh chưa được phát triển C E F I thì đỉnh E có giá trị đánh giá nhỏ nhất nó được chọn để phát triển và sinh ra các đỉnh G K. Trong số các đỉnh chưa được phát triển thì G tốt nhất phát triển G sinh ra B H. Đến đây ta đã đạt tới trạng thái kết thúc. Cây tìm kiếm tốt nhất - đầu tiên được biểu diễn trong hình 2.3. Sau đây là thủ tục tìm kiếm tốt nhất - đầu tiên. Trong thủ tục này chúng ta sử dụng danh sách L để lưu các trạng thái chờ phát triển danh sách được sắp theo thứ tự tăng dần của hàm đánh giá sao cho trạng thái có giá trị hàm đánh giá nhỏ nhất ở đầu danh sách. Hình 2.3 Cây tìm kiểm tổt nhắt - đầu tiên procedure BestFirstSearch begin 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu 2. loop do 2.1 if L rỗng then thông báo thất bại stop 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 stop 2.4 for mỗi trạng thái v kề u do Xen v vào danh sách L sao cho L được sắp theo thứ tự tăng dần của hàm đánh giá end Tìm kiếm leo đồi Tìm kiếm leo đồi hill-climbing search là tìm kiếm theo độ sâu được hướng dẫn bởi hàm đánh giá. Song khác với tìm kiếm theo độ sâu khi ta phát triển một đỉnh u thì bước tiếp theo ta chọn trong số các đỉnh con của