Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Tìm kiếm heuristic-leo đồi, các thuật toán tìm kiếm cục bộ và thuật giải di truyền (Tô Hoài Việt)

Bài giảng Tìm kiếm heuristic-leo đồi, các thuật toán tìm kiếm cục bộ và thuật giải di truyền (Tô Hoài Việt) nhằm giới thiệu đến các bạn những nội dung về thuật giải leo đồi, vấn đề của thuật giải leo đồi, thuật giải leo đồi ngẫu nhiên, bài toán tối ưu hoá và các thuật toán tìm kiếm cục bộ, thuật giải di truyền, một số vấn đề lựa chọn của thuật giải di truyền, một ví dụ đơn giản. | Tìm kiếm heuristic – Leo đồi, Các thuật toán tìm kiếm cục bộ và thuật giải Di truyền Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@fit.hcmuns.edu.vn Tổng quát Thuật giải leo đồi Vấn đề của thuật giải leo đồi Thuật giải leo đồi ngẫu nhiên Bài toán tối ưu hoá và các thuật toán tìm kiếm cục bộ Thuật giải di truyền Một số vấn đề lựa chọn của thuật giải di truyền Một ví dụ đơn giản Thuật giải leo đồi Các thuật toán tìm kiếm toàn cục: sử dụng quá nhiều tài nguyên (A*) hoặc thời gian (IDA*) để tìm được lời giải tối ưu. Ta có thể thực hiện việc tìm kiếm lời giải trong thời gian và không gian hợp lý? Thuật giải leo đồi Leo đồi: Cố gắng tối đa hoá Eval(X) bắng cách di chuyển đến cấu hình cao nhất trong tập di chuyển của mình – Leo đồi dốc đứng Đặt S := trạng thái ban đầu Lặp Tìm trạng thái con S’ của S với Eval(S’) thấp nhất Nếu Eval(S’) không tốt hơn Eval(S) thì return S Ngược lại S = S’ Thuật giải leo đồi START GOAL d b p q c e h a f r 2 9 9 8 1 1 2 3 5 3 4 4 15 1 2 5 2 h=12 h=11 h=8 h=8 h=5 h=4 h=6 h=9 h=0 h=4 h=6 h=11 Leo đồi ngẫu nhiên Đặt S := trạng thái ban đầu Lặp sau một MAX lần cố gắng nào đó Lấy một trạng thái con ngẫu nhiên S’ của S Nếu Eval(S’) tốt hơn Eval(S) thì S= S’ Cuối lặp Return S Sau khi chạy vài lần có thể đưa đến trạng thái đích Ví dụ về bài toán tối ưu hoá Bài toán n-Hậu Đây là một bài toán Thoả mãn Ràng buộc (Contraint Satisfaction Problem CSP) Có thể xem xét dưới dạng một bài toán tối ưu hoá với hàm lượng giá h = số lượng cặp hậu đe doạ lẫn nhau Ví dụ về bài toán tối ưu hoá Thiết kế Mạch điện Có rất nhiều chip cố định Cùng số kết nối nhưng tốn ít không gian hơn Ví dụ về bài toán tối ưu hoá Bài toán tối ưu hoá Ta chỉ quan tâm đến việc đạt được một cấu hình tối ưu mà không cần quan tâm đến đường đi Xây dựng một tập di chuyển (moveset) từ một trạng thái sang một trạng thái khác VD: Cho biết tập di chuyển của Bài toán N-queen? Phát sinh ngẫu nhiên trạng thái ban đầu Thực hiện di chuyển xuống (lên) đồi Ví dụ về bài toán tối | Tìm kiếm heuristic – Leo đồi, Các thuật toán tìm kiếm cục bộ và thuật giải Di truyền Tô Hoài Việt Khoa Công nghệ Thông tin Đại học Khoa học Tự nhiên TPHCM thviet@fit.hcmuns.edu.vn Tổng quát Thuật giải leo đồi Vấn đề của thuật giải leo đồi Thuật giải leo đồi ngẫu nhiên Bài toán tối ưu hoá và các thuật toán tìm kiếm cục bộ Thuật giải di truyền Một số vấn đề lựa chọn của thuật giải di truyền Một ví dụ đơn giản Thuật giải leo đồi Các thuật toán tìm kiếm toàn cục: sử dụng quá nhiều tài nguyên (A*) hoặc thời gian (IDA*) để tìm được lời giải tối ưu. Ta có thể thực hiện việc tìm kiếm lời giải trong thời gian và không gian hợp lý? Thuật giải leo đồi Leo đồi: Cố gắng tối đa hoá Eval(X) bắng cách di chuyển đến cấu hình cao nhất trong tập di chuyển của mình – Leo đồi dốc đứng Đặt S := trạng thái ban đầu Lặp Tìm trạng thái con S’ của S với Eval(S’) thấp nhất Nếu Eval(S’) không tốt hơn Eval(S) thì return S Ngược lại S = S’ Thuật giải leo đồi START GOAL d b p q c e h a f r 2 9 9 8 1 1 2 3 5 3 4 4 15