GIẢI THUẬT HEURISTIC

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.1 MB, 17 trang )


Bạn đang xem: Giải thuật heuristic

Thuật toán nâng caoGVHD:Nguyễn Bá TườngHọc viên: Nhóm 3 GIẢI THUẬT HEURISTIC & ỨNG DỤNG GIẢI THUẬT HEURISTIC TRONG BÀI TOÁN NGƯỜI ĐƯA THƯNội dung Tiểu luận Ứng dụng bài toán người đưa thư2 Hỏi đáp3Nội dung thuật giải HeuristicGiới thiệu thuật giải Heuristic 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ườiThuật giải Heuristic là một sự mở rộng khái niệm thuật toánThường tìm được lời giải tốt Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơnNội dung thuật giải HeuristicHàm HeuristicĐó là các hàm đánh giá thô - một ước lượng về khả năng dẫn đến lời giải tính từ trạng thái hiện tại (khoảng cách giữa trạng thái hiện tại và trạng thái đích)
Chi phí ước lượng h’ = 6 và chi phí tối ưu thực sự h = 4+5 = 9 Nội dung thuật giải Heuristic Nguyên lý thuật giải Heuristickhi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêuLấy tiêu chuẩn tối ưu của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước trong quá trình tìm kiếm lời giảiThực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốtNguyên lý tham lamNguyên lý thứ tựNguyên lý vét cạn thông minhNội dung thuật giải Heuristic Các phương pháp tìm kiếm HeuristicCấu trúc chung của bài toán tìm kiếmTìm kiếm chiều rộngItem 1
Item 2Item 5Item 3Item 4Tìm kiếm chiều sâuTìm kiếm leo đồiTìm kiếm ưu tiên tối ưuCác phương pháp tìm kiếm Heuristic Cấu trúc chung của bài toán tìm kiếmNhiều vấn đề-bài toán phức tạp đều có dạng "tìm đường đi trong đồ thị"Xuất phát từ một đỉnh của một đồ thị, tìm đường đi hiệu quả nhất đến một đỉnh nào đóĐa số các bài đều có thể được biểu diễn dưới dạng đồ thịVấn đề chungMột trạng thái là một đỉnh của đồ thịCác phương pháp tìm kiếm Heuristic Tìm kiếm chiều sâu(DFS) Là thuật toán duyệt hoặc tìm kiếm trên một câyhoặc đồ thị. Thuật toán khởi đầu tại gốc và phát triển xa nhất có thể theo mỗi nhánhTìm kiếm chiều sâu bắt đầu từ đỉnh xuất phát, đi theo cạnh trái, tiếp tục tìm kiếm xong ở cây con
trái mới chuyển sang tìm kiếm ở cây con phải. Ví dụ: Thứ tự thăm viếng các đỉnh là: A, B, D, F, E, C, GCác phương pháp tìm kiếm Heuristic Tìm kiếm chiều rộng(BFS) Ngược lại với tìm kiếm theo kiểu chiều sâu, tìm kiếm chiều rộng mang hình ảnh của vết dầu loang Từ trạng thái ban đầu, ta xây dựng tập hợp S bao gồm các trạng thái kế tiếp . Ứng với mỗi trạng thái Tk trong tập S, ta xây dựng tập Sk bao gồm các trạng thái kế tiếp của Tk rồi lần lượt bổ sung các Sk vào S. lặp lại cho đến lúc S có chứa trạng thái kết thúcCác phương pháp tìm kiếm Heuristic Tìm kiếm Leo Đồi
Định nghĩaLeo đồi đứng dốcTìm kiếm leo đồi, thực chất chỉ là trường hợp đặc biệt của tìm kiếm theo chiều sâu nhưng không thể quay lui. Là leo đồi nhưng sẽ duyệt tất cả các hướng đi có thể và chọn đi theo trạng thái tốt nhất trong số các trạng thái kế tiếp có thể cóNếu trạng thái bắt đầu cũng là trạng thái đích thì báo là đã tìm được lời giải. Ngược lại, đặt trạng thái hiện hành (Ti) là trạng thái khởi đầuTư tưởngLặp lại cho đến khi đạt đến trạng thái kết thúc hoặc cho đến khi không tồn tại một trạng thái tiếp theo hợp lệ (Tk) của trạng thái hiện hànhCác phương pháp tìm kiếm Heuristic
Tìm kiếm ưu tiên tối ưu Định nghĩa:Tìm kiếm ưu tiên tối ưu sẽ kết hợp 2 phương pháp tìm kiếm theo chiều rộng và theo chiều sâu là không phải quan tâm đến sự mở rộng của tất cả các nhánh và không bị sa vào các đường dẫn bế tắc22334411Thuật giải AT: là một phương pháp tìm kiếm theo kiểu BFS với độ tốt của nút là giá trị hàm g – tổng chiều dài con đường đã đi từ trạng thái bắt đầu đến trạng thái hiện tạiThuật giải AKT: Thuật giải AKT mở rộng AT bằng cách sử dụng thêm thông tin ước lượng h’. Độ tốt của một trạng thái f là tổng của hai hàm g và h’Thuật giải A*: A* là một phiên bản đặc biệt của AKT áp dụng cho trường hợp đồ thị. Thuật giải A* có sử dụng thêm tập hợp CLOSE để lưu trữ những trường hợp đã được xét đếnNội dung thuật giải Heuristic ỨNG DỤNG BÀI TOÁN NGƯỜI ĐƯA THƯPhát biểu bài toánHạn chế khi sử dụng thuật toán tối ưuCài đặt thuật toán123
4Chương trình DemoỨNG DỤNG BÀI TOÁN NGƯỜI ĐƯA THƯ Phát biểu bài toánMục đích bài toán : Để tiết kiệm thời gian đi đưa thư trong một địa phương.Người đưa thư phải đi qua tất cả các điểm cần phát thư rồi trở về vị trí ban đầu với đường đi ngắn nhất.Bài toán có thể phát biểu lại như sau: Giả sử có một đồ thị có trọng số dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban đầu.ỨNG DỤNG BÀI TOÁN NGƯỜI ĐƯA THƯ Hạn chế khi sử dụng thuật toán tối ưuĐồ thị có n đỉnh, khi đó thuật toán tối ưu cho bài toán này sẽ là thuật toán tìm đường đi ngắn nhất cho chu trình Haminton. Do đó thuật toán tối ưu sẽ có độ phức tạp là O( n!) và không thể thực hiện thuật toán.Vì vậy sẽ sử dụng thuật giải Heuristic cho bài toán này.ỨNG DỤNG BÀI TOÁN NGƯỜI ĐƯA THƯ Cài đặt thuật toánThử việc & đào tạoChương trình được viết trên môi trường Visual C++ 6.0Công cụ lập trìnhInput
OutputMột ma trận vuông trong file “graph.txt “ có dạng như hình bên, hay nhập ma trận bằng tayĐường đi theo thuật giải Heuristic, và chi phí của đường đi đóỨNG DỤNG BÀI TOÁN NGƯỜI ĐƯA THƯ Chương trình Đề MôThử việc & đào tạo?


*
Ứng dụng phương pháp moment trong bài toán phân tích các kết cấu điện tử phẳng được kích thích bởi sóng chạy 179 616 0
*
Báo cáo đồ án trí tuệ nhân tạo: Mô tả không gian trạng thái bài toán người đưa thư (Travelling Saleman Problem – PST) và dùng giải thuật Local Search để giải quyết 11 1 1

Xem thêm: Xứ Đông Lào Là Gì ? Đông Lào Là Quốc Gia Nào Trên Thế Giới? Đông Lào Là Gì

*
Báo cáo đồ án trí tuệ nhân tạo : xây dựng chương trình cho phép tìm kiếm đường đi tốt nhất theo giải thuật tìm kiếm Greedy best first search cho Không gian trạng thái bài toán người đưa thư 27 1 11
*
Hướng dẫn cài đặt SharePoint Ứng dụng công nghệ SharePoint trong bài toán quản lý công văn tại Bưu điện tỉnh Thái Nguyên 3 724 1
*
Ứng dụng công nghệ SharePoint trong bài toán quản lý công văn tại Bưu điện tỉnh Thái Nguyên 129 861 1
*
GIẢI THUẬT HEURISTIC ỨNG DỤNG GIẢI THUẬT HEURISTIC TRONG BÀI TOÁN NGƯỜI ĐƯA THƯ 17 1 1
*
THUẬT TOÁN NÂNG CAO GIẢI THUẬT HEURISTIC ỨNG DỤNG GIẢI THUẬT HEURISTIC TRONG BÀI TOÁN NGƯỜI ĐƯA THƯ 25 1 4
*
Báo cáo khoa học: " ỨNG DỤNG GIẢI THUẬT META-HEURISTIC TRONG BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT" pot 8 899 8
*
Ứng dụng của phép quay trong bài toán chứng minh trong mặt phẳng 45 1 1
*
Khóa luận tốt nghiệp ứng dụng của phép quay trong bài toán chứng minh trong mặt phẳng 45 655 1
*


(8.49 MB - 17 trang) - GIẢI THUẬT HEURISTIC ỨNG DỤNG GIẢI THUẬT HEURISTIC TRONG BÀI TOÁN NGƯỜI ĐƯA THƯ