Tiểu luận kết thúc môn học: Hệ chuyên gia

Nhiều bài toán phức tạp có thể được phát biểu dưới dạng sau: Cho trước hai trạng thái T0 và TG. Hãy xây dựng chuỗi trạng thái T0, T1, T2, .Tn (TG) sao cho cost(Ti-1,Ti) thỏa mãn điều kiện cho trước. Trong đó Ti thuộc tập hợp S gồm tất cả các trạng thái có thể có của bài toán và cost(Ti-1,Ti) là chi phí để biến đổi từ trạng thái Ti-1 đến Ti. Các bài toán thuộc dạng này đều có thể được biểu diễn dưới dạng đồ thị. Trong đó một trạng thái là một đỉnh của đồ thị. Tập hợp S gồm tất cả các trạng thái chính là tập hợp các đỉnh của đồ thị. Việc biến đổi từ trạng thái Ti-1 sang trạng thái Ti là việc đi từ đỉnh đại diện cho Ti-1 đến đỉnh đại diện cho Ti theo cung nối giữa hai đỉnh này.

Đối với loại bài toán này, một phương pháp tìm kiếm lời giải phổ biến và dễ cài đặt nhất là phương pháp thử-sai quay lui. Để giảm bớt không gian thử sai, có nhiều kỹ thuật như: đơn giản điều kiện, loại bỏ những hướng đi chắc chắn không dẫn đến lời giải, nhánh cận. Tuy nhiên đối với những bài toán có không gian tìm kiếm rất lớn, dù cố gắng tinh chỉnh đến bao nhiêu đi nữa các phương pháp này cũng không đạt được hiệu quả mong muốn.

Để tìm kiếm được lời giải nhanh hơn, người ta đưa ra một phương pháp với ý tưởng là “chọn đi theo hướng có nhiều khả năng dẫn đến lời giải. Đây chính là ý tưởng của thuật giải Heuristic.

Số lượng hướng đi mà chắc chắn không dẫn đến lời giải luôn ít hơn những hướng đi có thể dẫn đến lời giải. Nếu như đánh giá được khả năng dẫn đến lời giải của một hướng đi thì ta có thể xây dựng được một thứ tự ưu tiên để duyệt các hướng đi. Khi duyệt các hướng đi theo thứ tự ưu tiên giảm dần ta sẽ có cơ hội tiếp cận đến lời giải nhanh hơn là duyệt một cách mù quáng.

Thực ra các phương pháp tìm kiếm lời giải của một bài toán đã được trình bày rất cụ thể và chính xác ở nhiều tài liệu. Thuật giải Heuristic cũng đã được áp dụng rộng rãi trong nhiều ứng dụng. Tiểu luận không nhằm cải tiến các phương pháp tìm kiếm này mà chỉ tóm tắt những tri thức mà bản thân đã thu nhận được qua thời gian học tập và tham khảo tài liệu. Đồng thời vận dụng những tri thức đó để giải quyết một bài toán ứng dụng cụ thể, đó là lập trình trò chơi Caro.

Tiểu luận gồm 3 phần. Phần 1: Trình bày những phương pháp tìm kiếm lời giải của bái toán. Trong đó nhấn mạnh phương pháp tìm kiếm ưu tiên tốt nhất BFS và thuật giải A* cũng như các chiến lược phối hợp giữa các phương pháp. Phần 2: Giới thiệu hai thuật toán trong đó có áp dụng heuristic vào lập trình trò chơi. Phần 3: Lấy một ví dụ lập trình trò chơi Caro để minh họa cho hai phần đã được trình bày.