Bài giảng: Thuật giải Heuristic (ThS. Đào Quốc Thắng)

Chuyên đề bồi dưỡng đội tuyển Olympic Tin học: Thuật giải Heuristic của trường ĐH Ngân hàng Tp. HCM gồm các nội dung chính: Khái niệm “Thuật toán” và “Thuật giải”; Thuật giải Heuristic; Một số ví dụ ứng dụng; Bài tập.
Nội dung trích xuất từ tài liệu:
Bài giảng: Thuật giải Heuristic (ThS. Đào Quốc Thắng)CHUYÊN ĐỀ BỒI DƯỠNG ĐỘI TUYỂN OLYMPIC TIN HỌC THUẬT GIẢI HEURISTIC Giảng viên: ThS. Đào Quốc Thắng Khoa Công nghệ thông tin Trường ĐH Ngân hàng Tp HCM 1Nội dung Khái niệm “Thuật toán” và “Thuật giải” Thuật giải Heuristic Một số ví dụ ứng dụng Bài tập 2Khái niệm “Thuật toán” và“Thuật giải” Quan điểm lập trình cấu trúc Algorithm + Data structure = Program Thuật toán: dãy hữu hạn các bước không mập mờ và có thể thực hiện được, quá trình hành động theo các bước này phải dừng và cho kết quả như mong muốn. 3Các tính chất cơ bản của thuậttoán Xác định. Hữu hạn. Tính đúng. 4Hạn chế Có nhiều bài toán cho tới nay vẫn chưa xây dựng được thuật toán. Có bài toán xây dựng được thuật toán song không thể áp dụng được do không đủ tài nguyên để cung cấp. Có thể giải quyết một số bài toán theo những cách khác, thường cho kết quả tốt và thực hiện dễ dàng hơn so với thuật toán. 5Thuật giải Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán. 62. Thuật giải Heuristic Là sự mở rộng của thuật toán với các đặc tính:  Thường cho lời giải tốt (nhưng không chắc là tốt nhất).  Cho phép giải quyết bài toán một cách nhanh chóng, dễ dàng.  Thể hiện tự nhiên, gần gũi với suy luận của con người. 7Các nguyên lý cơ sở của thuậtgiải Heuristic Nguyên lý tham lam (nguyên lý Greedy). Nguyên lý thứ tự. Nguyên lý hướng đích (hàm Heuristic). Nguyên lý vét cạn. 8Nguyên lý tham lam Lấy tiêu chuẩn tối ưu toàn cục (đặt ra cho bài toán) làm tiêu chuẩn chọn lựa hành động cục bộ (từng bước/từng giai đoạn thực hiện). 9Nguyên lý hướng đích (HàmHeuristic) Các hàm đánh giá thô, giá trị phụ thuộc vào trạng thái hiện tại của bài toán tại một bước giải, cho phép chọn lựa hành động một cách hợp lý trong từng bước của thuật giải. 10Nguyên lý vét cạn Bài toán tìm kiếm: cố gắng hạn chế không gian tìm kiếm hoặc sử dụng một kiểu dò tìm đặc biệt dựa vào đặc thù riêng của bài toán để nhanh chóng đi tới mục tiêu. 113. Một số ví dụ ứng dụng Bài toán hành trình ngắn nhất: ứng dụng nguyên lý Greedy Bài toán phân việc: ứng dụng nguyên lý thứ tự Bài toán tô màu bản đồ: ứng dụng nguyên lý thứ tự Bài toán Ta-canh: ứng dụng hàm Heuristic 12Bài toán hành trình ngắn nhất Một người bán hàng mỗi ngày phải đem hàng từ công ty đến giao cho các đại lý trong thành phố, rồi sau đó quay trở lại vị trí xuất phát (về lại công ty). Giả sử giữa mỗi cặp điểm (công ty/đại lý) đều tồn tại một đường đi trực tiếp. Hãy tìm con đường đi ngắn nhất sao cho mỗi đại lý chỉ được đi qua đúng 1 lần. 13Ví dụ minh họa 1 5 1 7 2 3 2 5 4 2 4 3 4 3 1 14Bài toán phân việc Một công ty nhận hợp đồng gia công n chi tiết máy J1, J2, …Jn. Công ty có m máy công cụ P1, P2, …Pm, trong đó mỗi chi tiết máy đều có thể gia công trên bất kỳ máy nào, một khi đã gia công một chi tiết máy thì không thể ngưng giữa chừng. 15Ví dụ Giả sử thời gian cần thiết để gia công mỗi chi tiết Ji là Ti, hãy phân công công việc trên các máy để thời gian thực hiện hợp đồng là ngắn nhất. VD 1: m=3, n=5, T1=2, T2=5, T3=8, T4=1, T5=5. VD 2: m-2, n=5, T1=3, T3, T4=2, T5=2. 16Bài toán tô màu bản đồ Cho một bản đồ n vùng, hãy tô màu các vùng sao cho mỗi cặp 2 vùng lân cận phải được tô bằng 2 màu riêng biệt và số màu được sử dụng là ít nhất. 17Ví dụ: Tô màu bản đồ 6 8 2 3 5 91 7 4 18Bài toán Ta-canh (trò chơi 9-puzzle) Cho hình vuông kích thước 3x3 với 9 ô chứa 1 trong 8 con số 1, 2, …, 8 và 1 ô để trống. Hãy di chuyển ô trống sao cho các ô số được sắp xếp theo thứ tự tứ 1 đến 8. 19Ví dụ minh họa3 1 4 1 2 37 6 4 5 68 2 5 7 8 20 ...