Trí tuệ Nhân Tạo - Buổi 2 - Thuật giải Heuristic

🎓 TỔNG QUAN BUỔI HỌC: THUẬT GIẢI HEURISTIC

Buổi học giới thiệu khái niệm thuật giải Heuristic, các nguyên lý thiết kế và ứng dụng thực tế trong việc giải quyết những bài toán phức tạp mà thuật toán chuẩn không thể xử lý hiệu quả.
Giảng viên hướng tới việc giúp người học hiểu bản chất, nắm nguyên tắc và biết cách vận dụng Heuristic vào các bài toán tối ưu.

🧠 1. KHÁI NIỆM CƠ BẢN
🔹 Thuật toán tiêu chuẩn

Là tập hợp các bước chính xác, dừng được và cho ra kết quả đúng. Tuy nhiên, khi áp dụng cho các bài toán có độ phức tạp lớn (như tối ưu tổ hợp), thuật toán chuẩn thường rất chậm và tốn tài nguyên.

🔹 Thuật giải Heuristic

Là hướng tiếp cận gần đúng, mô phỏng trực giác con người, nhằm tìm lời giải “đủ tốt” trong thời gian ngắn hơn.
Đặc điểm:
Không đảm bảo kết quả tối ưu tuyệt đối, nhưng nhanh và khả thi.
Khai thác thông tin và kinh nghiệm của con người.
Phản ánh tư duy tự nhiên trong quá trình ra quyết định.

Một lời giải Heuristic được xem là chấp nhận được nếu:
Tận dụng được thông tin bài toán.
Sử dụng tri thức, kinh nghiệm thực tế.
Mô phỏng hợp lý cách tư duy của con người.

⚙️ 2. BỐN NGUYÊN LÝ THIẾT KẾ THUẬT GIẢI HEURISTIC
1️⃣ Nguyên lý Vét cạn thông minh (Intelligent Pruning)

Thay vì duyệt toàn bộ không gian tìm kiếm khổng lồ, Heuristic rút gọn phạm vi tìm kiếm dựa trên đặc trưng bài toán — chỉ giữ lại phần “có triển vọng”.

2️⃣ Nguyên lý Tham lam (Greedy Principle)

Tại mỗi bước, chọn phương án tốt nhất ở hiện tại với hy vọng kết quả cuối cùng cũng tốt.
→ Đơn giản, hiệu quả, nhưng có thể rơi vào “bẫy cục bộ”.

3️⃣ Nguyên lý Thứ tự (Ordering Principle)

Sắp xếp các phần tử theo thứ tự hợp lý (tăng/giảm hoặc ưu tiên đặc biệt) để quá trình giải nhanh và hiệu quả hơn.

4️⃣ Hàm Heuristic (Heuristic Function)

Hàm đánh giá giúp ước lượng mức “tốt” của một bước đi.
Ví dụ: trong tìm đường, dùng khoảng cách chim bay để dự đoán vị trí gần đích nhất, dù thực tế không đi đúng đường đó.

🧩 3. ỨNG DỤNG CỤ THỂ
🔸 Bài toán 1: Phân công công việc (Work Assignment Problem)

Phân N công việc cho M máy để tối thiểu hóa thời gian hoàn thành.

Giải pháp vét cạn có độ phức tạp rất cao 𝑂(𝑀^𝑁)
Heuristic áp dụng (Nguyên lý Thứ tự):
Sắp xếp công việc theo thời gian giảm dần.
Giao công việc lớn nhất cho máy đang rảnh nhất (ít việc nhất).
✅ Ưu điểm: Tốc độ nhanh, độ phức tạp giảm mạnh (~O(max(NlogN, M²))).
⚠️ Nhược điểm: Không đảm bảo tối ưu tuyệt đối.

🔸 Bài toán 2: Tô màu đồ thị (Graph Coloring Problem)

Tô màu các đỉnh sao cho hai đỉnh kề nhau khác màu và dùng ít màu nhất.
Ứng dụng: Sắp lịch thi học kỳ, phân bổ tài nguyên, xếp lịch hội thảo,…
Heuristic áp dụng (Nguyên lý Thứ tự):
Tô màu đỉnh có bậc cao nhất (liên kết nhiều nhất) trước.
Ưu tiên dùng lại màu cũ, chỉ tạo màu mới khi cần.
✅ Giúp giảm xung đột, tối ưu số màu trong thực tế.

🔸 Bài toán 3: Người du lịch (Traveling Salesperson Problem – TSP)

Tìm chu trình ngắn nhất đi qua tất cả thành phố một lần và quay lại điểm xuất phát.

Độ phức tạp tối ưu: 𝑂(𝑁!) → không khả thi khi N lớn.
Heuristic áp dụng (Nguyên lý Tham lam):

Ở mỗi bước, chọn thành phố gần nhất chưa đi qua.
✅ Nhanh hơn nhiều, độ phức tạp chỉ 𝑂(𝑁^2)
⚠️ Tuy nhiên, có thể tạo kết quả kém nếu các bước “tham lam” dẫn đến đoạn cuối rất dài.

📚 4. KẾT LUẬN BUỔI HỌC

Buổi học đặt nền tảng cho việc hiểu tư duy Heuristic – phương pháp giải gần đúng, dựa trên trực giác và kinh nghiệm thay vì tính toán toàn diện.
Sinh viên nắm được:

Sự khác biệt giữa thuật toán chuẩn và thuật giải Heuristic.
Bốn nguyên lý cốt lõi khi thiết kế Heuristic.
Cách áp dụng Heuristic vào bài toán thực tế như phân công công việc, tô màu đồ thị, TSP.

Buổi sau sẽ mở rộng sang các thuật giải tìm đường tối ưu, điển hình là Dijkstra và A* – những ví dụ tiêu biểu của việc kết hợp Heuristic với tìm kiếm có định hướng.