Tính xác định:Không mập mờ và có thể thực thi được Tính hữu hạn: chương trình phải dừng Tính đúng: cho kết quả chính xác Show 1. THUẬT GIẢILà giải pháp được viếc dưới dạng thủ tục tương tự như thuật toán nhưng không đòi hỏi các tiêu chuẩn như thuật toán. Tính đúng:chấp nhận các thuật giải đơn giản có thể cho kết quả đúng hay gần đúng nhưng có khả năng thành công cao hơn. Để có thể được chấp nhận, thuật giải phải thể hiện một giải pháp hợp lý nhất có thể trong tình huống hiện tại bằng cách: Tận dụng mọi thông tin hữu ích Sử dụng tri thức, kinh nghiệm trực giác của con người Tự nhiên đơn giản nhưng cho kết quả chấp nhận được Thuật giải HEURISTIC 1. CÁC ĐẶC TÍNHThuật giải Heuristic là một sự mở rộng khái niệm thuật toán, thể hiện cách giải bài toán với các đặc tính sau: Thường tìm được lời giải tốt nhất( nhưng không chắc là lời giải tốt nhất). Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gủi với cách suy nghĩ và hành động của con người. Giải bài toán theo thuật toán Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với thuật giải tối ưu, vì vậy chi phí thấp hơn. 1. CÁC NGUYÊN LÝ THUẬT GIẢI HEURISTIC Tham lam(Greedy) Phần 1 Khái Niệm Thuật Heuristic Lấy điểm chuẩn tối ưu(trên phạm vi toàn cục) của bài toán, dựa vào đó chọn lựa hành động tốt nhất của từng bước( hay từng giai đoạn) trong quá trình tìm kiếm lời giải. Phần 1 Khái Niệm Thuật Heuristic Bố trí việc J cho máy M Ví dụ: n=10, m= tj=4 9 5 2 7 6 10 8 7 5 M1 10 6 5 M2 8 7 4 2 M3 9 7 5 Tuy nhiên trong một số trường hợp thuật giải chưa cho ra lời giải chính xác. Ví dụ: n=5,m= tj=3 3 2 2 2 1. PHÁT BIỂU BÀI TOÁN:Có một đồ thị vô hướng đơn giản. Ta muốn tìm cách tô màu cho các đỉnh của đồ thị sao cho 2 đỉnh cạnh nhau phải có màu khác nhau. Yêu cầu: Tìm phương án tô sao cho số màu sử dụng là ít nhất Sử dụng nguyên lý thứ tự: Phần 1 Khái Niệm Thuật Heuristic for(k=0;k<n;k++){ Bước 1. Chọn đỉnh S: có số đỉnh chưa tô ở cạnh nó là lớn nhất(bậc lớn nhất) Bước 2. Chọn màu: Ưu tiên tô đỉnh S bằng những màu đã tô, nếu không được thì sử dụng màu mới Bước 3. Sau khi tô màu cho đỉnh S thì ta xóa các cạnh có nối đến S và đánh dấu các đỉnh kế bên không được tô màu vừa tô cho S. } Phần 2 Khái Niệm Đồ Thị 2. TÔ MÀU BẢN ĐỒ:Mỗi bản đồ có thể coi là một đồ thị phẳng. Trong một bản đồ, ta coi hai miền có chung nhau một đường biên là hai miền kề nhau (hai miền chỉ có chung nhau một điểm biên không được coi là kề nhau). Một bản đồ thường được tô màu , sao cho hai miền kề nhau được tô hai màu khác nha. Ta gọi một cách tô màu bản đồ như vậy là một các tô màu đúng. Để đảm bảo chắc chắn hai miền kề nhau không bao gờ có màu trùng nhau, chúng ta tô mỗi miền bằng một màu khác nhau. Tuy nhiên việc làm đó nói chung là không hợp lý. Nếu bản đồ có nhiều miền thì sẽ rất khó phân biệt những màu gần giống nhau. Do vậy người ta chỉ dùng một số màu cần thiết để tô bản đồ. Một Bài toán được đặt ra là: xác định số màu tối thiểu cần có để tô màu đúng một bản đồ. Ví dụ: Bản đồ hình bên có 6 miền, nhưng chỉ cần có 3 màu (vàng, đỏ, xanh) để tô cho M1 và M4, màu đỏ được tô cho M2 và M6, màu xanh được tô cho M3 và M Phần 3 Thuật Toán Tô Màu Trên Đồ Thị III. THUẬT TOÁN TÔ MÀU TRÊN ĐỒ THỊ TỐI ƯU3. CÁC BƯỚC CỦA THUẬT TOÁN:Bước 1: Tính giá trị bậc của các đỉnh trong V. Lập danh sách V’:=[v1tv2, ...,vn] là các đỉnh của đồ thị được sắp xếp theo thứ tự bậc giảm dần: d(v1) > d(v2) > ... > d(vn). Ban đầu tất cả các đỉnh trong V (V’) đều chưa được tô màu. Gán i := 1; Bước 2: Tô màu i cho đỉnh đầu tiên trong danh sách V’. Duyệt lần lượt các đỉnh khác trong V’(nếu có) và chỉ tô màu i cho các đỉnh không kề đỉnh đã có màu i. Bước 3: Kiểm tra nếu tất cả các đỉnh trong V đã được tô màu thì thuật toán kết thúc, đồ thị đã sử dụng i màu để tô. Ngược lại, nếu vẫn còn đỉnh chưa được tô thì chuyển sang bước 4. Bước 4: Loại khỏi danh sách V’ các đỉnh đã tô màu. Sắp xếp lại các đỉnh trong V’ theo thứ tự bậc giảm dần. Gán i := i + 1 và quay lại bước 2. Để dễ hiểu hơn, các bạn xem sự thể hiện các bước của thuật toán trong ví dụ sau: Cho đồ thị như hình vẽ, sử dụng thuật toán tô màu đồ thị ở trên, tô màu cho các đỉnh của đồ thị. Phần 3 Thuật Toán Tô Màu Trên Đồ Thị Đỉnh 3 được tô màu 3-Green. Số màu cần thiết phải sử dụng là i =3 màu. 3. VÍ DỤ BÀI TOÁN TÔ MÀU ĐỒ THỊĐỉnh A D B E F I C Bậc 4 4 3 3 3 3 2 Màu Màu 1 Màu 2 Màu 3 Màu 2 Màu 1 Màu 4 Màu 3 Bước 1. Sắp xếp các đỉnh theo thứ tự bậc giảm dần Bước 2. Xét đỉnh đầu tiên( bậc cao nhất) để gán màu Gán màu cho các đỉnh không kề với đỉnh đang xét, đảm bảo 2 đỉnh kề nhau không cùng 1 màu Lặp lại bước 2 đến hết danh sách Ví dụ: |
