Thuật toán Heuristic

Tìm hiểu thuật toán Heuristic

Nguyễn Văn Sơn

Đối với nhiều bài toán, hoặc không có lời giải, hoặc độ phức tạp tính toán là hàm mũ, hoặc

là bài toán NP-đầy đủ…, có nghĩa là nó không có lời giải khả thi, thì thông thường thay vì

tìm lời giải tối ưu cho chúng, chúng ta cố gắng tìm lời giải có thể chấp nhận được, đáp ứng

được yêu cầu của thực tế. Các lời giải này chính là các thuật toán heuristic.

Các thuật toán tìm kiếm luôn luôn đóng vai trò quan trọng trong việc giải các bài toán tin

học. Các thuật toán loại này rất phong phú, có thể kể đến như: vét cạn, đệ quy quay lui,

nhánh cận, nhị phân…Tuy nhiên, khi gặp những bài toán có không gian tìm kiếm lớn (đặc

biệt trong các trò chơi cờ) thì các thuật toán tìm kiếm thông thường không cho kết quả

hoặc kết quả không tối ưu (do những hạn chế về thời gian và bộ nhớ). Một hướng tiếp cận

độc đáo có thể đáp ứng được đòi hỏi cho nhiều bài toán loại này là dùng thuật toán

Heuristic.

Thuật ngữ Heuristic xuất phát từ tiếng Hy Lạp là ″heuriskein″ có nghĩa là ″tìm kiếm″ hoặc

″phát minh″. Chắc chắn chúng ta vẫn còn nhớ câu chuyện về nhà bác học Archimedes. Khi

phát hiện ra định luật về trọng lượng riêng, ông đã trần truồng chạy ra đường và kêu lớn

″tôi tìm ra rồi″. Thực ra, lúc đó ông đã kêu lên ″heureka″, về sau này người ta đổi từ này

thành ″eureka″.

Thuật ngữ Heuristic được Feigenbaum Feldman định nghĩa như sau: ″Heuristic là các quy

tắc, phương pháp, chiến lược, mẹo giải hay phương cách nào đó nhằm làm giảm khối

lượng tìm kiếm lời giải trong không gian bài toán cực lớn″.

Tư tưởng chính để giảm khối lượng tìm kiếm là thay vì ″loại bỏ các hướng tìm kiếm chắc

chắn không dẫn đến lời giải″, ta hãy ″chọn đi theo hướng có nhiều khả năng dẫn đến lời

giải″.

Do thuật toán Heuristic được con người sử dụng thường mang đặc trưng của những gợi ý

hay lời khuyên, nên các phương pháp dựa trên Heuristic đôi khi không chỉ ra con đường

trực tiếp để đạt tới mục đích.

Nhiều kết quả nghiên cứu trong trí tuệ nhân tạo cho thấy rằng, tuy có nhiều điểm mạnh nổi

bật, nhưng trong một vài lĩnh vực nghiên cứu nào đó thì các phương pháp Heuristic còn

bộc lộ những điểm yếu nhất định. Điều phức tạp chính là vì mọi chương trình máy tính

phải đảm bảo chắc chắn kết thúc công việc (theo định nghĩa một thuật toán phải đảm bảo

tính đúng và tính dừng). Vì vậy, nếu nói rằng một chương trình nào đó sử dụng Heuristic

thì kết luận về tính dừng chỉ đúng trong đa số các trường hợp. Do đó, trong phần lớn

trường hợp giải quyết bài toán, các chương trình Heuristic có lúc cho kết quả mong đợi,

đôi khi lại không.

Các Heuristic không chỉ tác động đến các chiến lược tìm kiếm, mà còn ảnh hưởng quyết

định tới các chiến lược điều khiển (hướng tìm kiếm trong không gian bài toán và xử lý

cạnh tranh). Đối với những bài toán trí tuệ phức tạp, số khả năng có thể lớn tới mức không

thể có một máy tính nào dầu hiện đại đến mấy đáp ứng nổi. Do vậy, thủ tục duyệt toàn thể

không thể chấp nhận được. Trong phần lớn các bài toán chứng minh định lý sử dụng logic,

số khả năng cần phải xét trở lên vô hạn. Việc lựa chọn một nước đi tốt nhất trong trò chơi

đòi hỏi phải tìm kiếm trong khoảng 1040 khả năng khác nhau, thậm chí đối với chơi cờ, số