Nguyên lý heuristic

Chia sẻ: Nguyen Van Tien | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

241
lượt xem 88
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần này mở rộng khái niệm heuristic cho một số bài toán tìm kiếm khác. Các thuật toán tìm kiếm UCS, tìm kiếm tốt nhất và A* thực hiện chiến lược vét cạn trên không gian tìm kiếm để tìm lời giải. Chiến lược này bảo đảm tìm được đường đi (tối ưu) nhưng phải duyệt nhiều trạng thái, đặc biệt khi bài toán có độ sâu lời giải lớn. Các bài toán dưới đây áp dụng các chiến lược tìm kiếm heuristic (cố gắng đưa ra lời giải tốt tại mỗi bước thực hiện) và không quay lui....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Nguyên lý heuristic

Nguyên lý heuristic trong việc giải quyết một số bài toán Phần này mở rộng khái niệm heuristic cho một số bài toán tìm kiếm khác. Các thuật toán tìm kiếm UCS, tìm kiếm tốt nhất và A* thực hiện chiến lược vét cạn trên không gian tìm kiếm để tìm lời giải. Chiến lược này bảo đảm tìm được đường đi (tối ưu) nhưng phải duyệt nhiều trạng thái, đặc biệt khi bài toán có độ sâu lời giải lớn. Các bài toán dưới đây áp dụng các chiến lược tìm kiếm heuristic (cố gắng đưa ra lời giải tốt tại mỗi bước thực hiện) và không quay lui. Do đó các thuật toán này không phải vét cạn không gian tìm kiếm và chỉ ra được những lời giải “đủ tốt”. 1.1 Bài toán người du lịch (Traveling Saleman Problem - TSP): 1.1.1 Phát biểu bài toán Cho N thành phố trong đó hai thành phố bất kỳ đều có đường nối với. Hãy xác định lộ trình cho người du lịch, xuất phát từ thành phố thứ nhất, đi qua tất cả các thành phố còn lại, trở về thành phố xuất phát sao cho tổng chi phí là nhỏ nhất. Hình bên trái dưới đây là đồ thị biểu diễn một ví dụ của bài toán người du lịch với N = 5. Hình bên phải biểu diễn bài toán dưới dạng ma trận kề. Trong ma trận kề, ô a[i, j] cho biết chi phí để đi từ thành phố i đến thành phố j. 1 6 1 ∞1 3 5 6 1 ∞5 3 4 5 2 543 3 5 ∞1 2 23 5 3 1 ∞2 2 5 6 4 2 2∞ 4 3 1 Lời giải tốt nhất của bài toán đạt được bằng cách so sánh tất cả các trường hợp đường đi có thể có. Số trường hợp có thể có chính là một sắp xếp hoán vị của N thành phố hay nói cách khác không gian tìm kiếm của bài toán có kích thước N! lời giải. Việc tìm kiếm trên không gian trạng thái là không khả thi do số trường hợp là khổng lồ (ví dụ, N=25 thì N! = 25!  1025 trạng thái). Áp dụng nguyên lý heuristic, ta có thể đạt được những thuật toán đơn giản với lời giải đủ tốt như sau. 1.1.2 Thuật toán GTS1 (Greedy Traveling Saleman) Thuật toán GTS1 cố gắng đạt được lời giải tốt nhất ở mỗi bước thực hiện bằng cách chọn đường đi có chi phí thấp nhất tại thành phố hiện tại và tiếp tục đi. Thuật toán gồm các bước sau: [Khởi đầu] TOUR = {}, COST = 0; v = 1. [Chọn lộ trình]: Lặp cho đến khi chọn đủ N đỉnh Với mỗi bước lặp: Chọn (v,w) là cạnh có chi phí nhỏ nhất tính từ v đến các đỉnh chưa sử dụng w. 1
Gán TOUR = TOUR + {(v,w)}, COST = COST + C(v,w). Sử dụng đỉnh w cho bước kế tiếp: v = w. [Hoàn thành]: Gán TOUR = TOUR + {(v,1)}, COST = COST + C(v,1). Áp dụng GTS 1 với ví dụ trên: [Khởi đầu]: - Chọn w = ___: TOUR = - Chọn w = ___: - Chọn w = ___: - Chọn w = ___: [Hoàn thành]: Chu trình: 1.1.3 Thuật toán GTS2 Thuật toán GTS1 rõ ràng không bảo đảm tìm được lộ trình tốt nhất. Nếu không bị ràng buộc bởi đỉnh xuất phát, GTS2 lựa chọn P (P
Xét ví dụ: Cho 3 máy M1, M2, M3 và 6 công việc với thời gian thực hiện tương ứng: T1 = 2, T2 = 5, T3 = 8, T4 = 1, T5 = 5, T6 = 1. Hãy bố trí công việc vào các máy sao cho thời gian thực hiện là thấp nhất. Thứ tự các công việc sắp xếp theo thời gian Công việc Thời gian Phân công:  M1  M2  M3 1.3 Bài toán thoả mãn ràng buộc – Thuật toán tô màu 1.3.1 Phát biểu Trong bài toán thoả mãn ràng buộc, ta cần xác định các gán giá trị cho một tập đỉnh sao cho việc gán giá trị này tho ả mãn một điều kiện cho trước. Một ví dụ tiêu biểu là bài toán tô màu: cho bản đồ các quốc gia trong một khu vực, xác định cách tô màu cho các quốc gia sao cho hai quốc gia láng giềng được tô bằng hai màu khác nhau và tổng số màu tô là thấp nhất. Hình là đồ thị biểu diễn các nước láng giềng của Việt Nam. 1.3.2 Thuật toán tô màu Hai thuật toán tô màu bao gồm: thuật toán heuristic dựa trên ràng buộc (đỉnh nào có nhiều ràng buộc nhất –bậc cao nhất– sẽ được tô trước) và thuật toán tô màu theo giá trị (tham lam). 3
Thuật toán tô màu trên đồ thị dựa vào số bậc (ràng buộc) Đếm bậc các đỉnh và Lặp lại các bước sau cho đến khi bậc của tất cả các đỉnh bằng 0 và các đỉnh đã được tô màu: Bước 1: Tô màu i cho đỉnh có bậc lớn nhất Bước 2: Hạ bậc. + Bậc của đỉnh được tô màu i thì: Bậc = 0 + Bậc của đỉnh có liên hệ với đỉnh được tô màu i thì: Bậc= Bậc -1 Bước 3: Cấm tô màu i cho các đỉnh vừa bị hạ bậc. Với ví dụ tô màu cho các nước ở trên, các bước thực hiện của thuật toán như sau: Xác định bậc của các đỉnh TQ VN LAO MIA THAI CAM PHI MAL BRU SING INDO Đỉnh Bậc Tô màu: TQ VN LAO MIA THAI CAM PHI MAL BRU SING INDO Đỉnh Bậc Màu Bậc Màu Bậc Màu Bậc Màu Bậc Màu Thuật toán tô màu greedy Dùng màu thứ nhất tô cho một đỉnh bất kỳ và tất cả các đỉnh khác có thể tô được. Sau đó dùng màu thứ hai tiếp tục tô cho các đỉnh còn lại theo cùng nguyên tắc … cho đến khi tất cả các đỉnh của đồ thị đã được tô màu. TQ VN LAO MIA THAI CAM PHI MAL BRU SING INDO i=1 i=2 i=3 i=4 4