MỞ ĐẦU
George Polya định nghĩa heuristic là “sự nghiên cứu về các phương pháp và các qui tắc trong việc khám phá và phát minh” (Polya 1945). Nghĩa này có thể xuất phát từ gốc Hy Lạp của động từ eurisco nghĩa là “tôi phát hiện”. Khi Archimedes nhảy ra khỏi bồn tắm và chộp lấy chiếc mũ miện bằng vàng, ông ta đã la lên “Eureka!” có nghĩa “Tôi đã tìm thấy nó!”. Trong tìm kiếm không gian trạng thái, heuristic là các luật dùng để chọn những nhánh nào có nhiều khả năng nhất dẫn đến một giải pháp chấp nhận được.
Các chương trình giải quyết những vấn đề trí tuệ nhân tạo sử dụng heuristic cơ bản theo hai dạng:
- Vấn đề có thể không có giải pháp chính xác vì những điều không rõ ràng trong diễn đạt vấn đề hoặc trong các dữ liệu có sẵn. Chẩn đoán y khoa là một ví dụ. Tập hợp các triệu chứng cho trước có thể do nhiều nguyên nhân gây ra, bác sĩ có thể dùng heuristic để chọn kết quả chẩn đoán nào thích hợp nhất và đưa ra kế hoạch điều trị.
- Vấn đề có thể có giải pháp chính xác, nhưng chi phí tính toán để tìm ra nó không cho phép. Trong nhiều vấn đề (như cờ vua chẳng hạn), không gian trạng thái phát triển rất nhanh và rất rộng vì số lượng các trạng thái có thể xảy ra tăng theo hàm mũ hoặc giai thừa cùng với độ sâu tìm kiếm. Trong những trường hợp này, các kỹ thuật tìm kiếm thô sơ như tìm kiếm sâu hay tìm kiếm rộng sẽ không tìm được giải pháp trong một giới hạn thời gian. Heuristic sẽ giảm bớt độ phức tạp bằng cách hướng việc tìm kiếm theo con đường có nhiều hứa hẹn nhất. Nhờ đã loại bỏ bớt các trạng thái không hứa hẹn và con cháu của chúng ra khỏi việc xem xét nên thuật toán heuristic có thể khắc phục việc bùng nổ trạng thái và tìm ra một giải pháp có thể chấp nhận được.
Giống như tất cả các luật khám phá và phát minh khác, heuristic có thể sai lầm. Heuristic chỉ là một phỏng đoán chứa các thông tin về bước tiếp theo sẽ được chọn dùng trong việc giải quyết một vấn đề. Nó thường dựa vào kinh nghiệm hoặc trực giác. Vì các heuristic sử dụng những thông tin hạn chế nên chúng ít khi có khả năng đoán trước chính xác cách hành xử của không gian trạng thái ở những giai đoạn xa hơn. Heuristic có thể dẫn đến một thuật toán tìm kiếm chỉ đạt được giải pháp gần tối ưu hoặc hoàn toàn không tìm được bất kỳ giải pháp nào. Đây là một hạn chế thuộc về bản chất tìm kiếm heuristic.
Các heuristic và việc thiết kế thuật toán để thực hiện tìm kiếm heuristic từ lâu đã là sự quan tâm chủ yếu của các công trình nghiên cứu trí tuệ nhân tạo. Chơi game và chứng minh định lý là hai ứng dụng lâu đời nhất, cả hai đều cần đến các heuristic để thu giảm bớt không gian giải pháp có thể. Không thể nào kiểm tra hết mọi suy luận có thể sinh ra trong lĩnh vực toán hoặc mọi nước đi có thể có trên bàn cờ vua, tìm kiếm heuristic thường là câu trả lời thực tế duy nhất. Gần đây việc tìm kiếm trong các hệ chuyên gia cũng xác nhận mức độ quan trọng của các heuristic như là một phần không thể thiếu trong quá trình giải quyết vấn đề.
Thuật toán heuristic gồm hai phần: Hàm đánh giá heuristic và thuật toán để sử dụng nó trong tìm kiếm không gian trạng thái.
Xét trò chơi Tic-tac-toe, để tìm kiếm đến hết không gian, số lượng trạng thái sẽ là rất lớn nhưng không phải là không thể vượt qua. Mỗi nước đi trong chín nước đầu tiên đều có tám khả năng đặt quân cờ kế tiếp và đến lượt mình mỗi nước đi này lại có bảy khả năng đặt quân cờ cho nước đi tiếp tục ... Một phân tích đơn giản cho biết số lượng các trạng thái cần được xem xét cho quá trình này là 9 x 8 x 7 x ... x 1 = 9!.
Áp dụng một nhận xét trực quan nhỏ dựa theo tính chất đối xứng của cấu hình bàn cờ có thể làm giảm nhỏ không gian tìm kiếm xuống một ít. Nhiều cấu hình của bài toán tương đương nhau trong các thao tác. Chẳng hạn, thực tế chỉ có ba nước đi cho quân cờ đầu tiên: ô cạnh, ô góc hoặc ô giữa. Các rút gọn đối xứng ở mức thứ hai của các trạng thái sẽ giảm tiếp số lượng đường đi có thể xảy ra trong không gian đó xuống đến tổng số 12 x 7! . Nó đã nhỏ hơn không gian ban đầu nhưng vẫn phát triển theo hàm giai thừa.
Hình 4.1 – Không gian trạng thái bài toán Tic-tac-toe thu giảm bởi tính đối xứng
Tuy nhiên, một heuristic đơn giản có thể loại bỏ việc tìm kiếm hầu như toàn bộ: heuristic “nước đi chắc thắng nhất”, nghĩa là chọn vị trí đặt quân cờ mà có nhiều đường chắc thắng nhất giao nhau. Trong trường hợp các trạng thái đều có số lượng bằng nhau, chọn trạng thái đầu tiên.
Sau đó thuật toán này sẽ chọn lựa và chuyển đến trạng thái có giá trị heuristic cao nhất (xem hình). Như trong hình vẽ, quân X sẽ chọn đặt vào vị trí trung tâm bàn cờ. Chú ý không chỉ các trạng thái tương đương khác bị loại bỏ mà tất cả con cháu của chúng cũng bị loại. Hai phần ba không gian trạng thái này đã bị loại ngay từ nước đi đầu tiên.
Sau nước đi đầu tiên, đối thủ có thể chọn một trong hai nước đi tương đương nhau. Dù chọn nước đi nào, heuristic đó cũng được áp dụng cho các bước tiếp theo. Khi quá trình tìm kiếm tiếp tục, từng bước đi sẽ đánh giá các con của một nút duy nhất mà không yêu cầu tìm kiếm hết không gian. Mặc dù khó tính chính xác số lượng trạng thái phải được kiểm tra theo cách này nhưng vẫn có thể tính phỏng đoán một giới hạn trên. Trong thực tế số lượng sẽ ít hơn 9! rất nhiều.
Hình 4.3 – Không gian trạng thái đã được thu giảm bởi heuristic
Download slide bài giảng tại đây