TAILIEUCHUNG - Nguyên lý heuristic

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 | 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 đe 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 . Bài toán người du lịch Traveling Saleman Problem - TSP 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. TO 1 3 5 6 1 TO 5 3 4 3 5 TO 1 2 5 3 1 TO 2 6 4 2 2 TO 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. Thuật toán GTS1 Greedy Traveling Saleman Thuật toán GTS 1 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 .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.