Danh mục

Nguyên lý heuristic

Số trang: 4      Loại file: pdf      Dung lượng: 272.65 KB      Lượt xem: 13      Lượt tải: 0    
Thư viện của tui

Phí tải xuống: miễn phí Tải xuống file đầy đủ (4 trang) 0
Xem trước 2 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

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....
Nội dung trích xuất từ tài liệu:
Nguyên lý heuristicNguyên lý heuristic trong việc giải quyết một số bài toánPhầ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ìmkiế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ềutrạ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ácchiế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ôngquay 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 đượcnhữ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ánCho 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ìnhcho 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ếtchi 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 đicó 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óicá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ênkhô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 đơngiả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ướcsau: [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ưasử 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 GTS2Thuậ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ộcbở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 gianthự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  M31.3 Bài toán thoả mãn ràng buộc – Thuật toán tô màu1.3.1 Phát biểuTrong 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 choviệ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 chohai 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àuHai 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ềurà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 ...

Tài liệu được xem nhiều: