CHƯƠNG 2 – BÀI TOÁN VÀ PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢI

4. Tính tối ưu: Giải thuật có tìm ra lời giải có chi phí tối ưu (nhỏ nhất hoặc lớn nhất tùy theo ngữ cảnh của bài toán)? Độ phức tạp thời gian và độ phức tạp không gian của giải thuật tìm kiếm lời giải của bài toán có thể đánh giá dựa trên kích thước đầu vào của giải thuật. Các tham số kích thước đầu vào có thể là: - b – nhân tố nhánh của cây tìm kiếm: số nhánh tối đa của một nút, hay là số phép chuyển trạng thái tối đa của một trạng thái tổng quát - d – độ sâu của lời giải có chi phí nhỏ nhất - m – độ sâu tối đa của cây tìm kiếm (m có thể là vô hạn) Trong các giải thuật tìm kiếm lời giải đề cập đến ở chương này, chúng ta sẽ đánh giá ưu, nhược điểm của từng giải thuật dựa trên 4 tiêu chí trên.