TAILIEUCHUNG - Thuật giải AT, AKT

Giống như leo đồi đơn giản, chỉ khác ở điểm là leo đồi dốc đứ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ó (trong khi đó leo đồi đơn giản chỉ chọn đi theo trạng thái kế tiếp đầu tiên tốt hơn trạng thái hiện hành mà nó tìm thấy). | Thuật giải AT, AKT Thuật giải AT (Algorithm for Tree): Mỗi đỉnh n tương ứng với một số g(n): giá thành của đường đi từ đỉnh ban đầu đến đỉnh n. Đỉnh: + Đỉnh đóng (Closed) : là những đỉnh đã được xem xét. +Đỉnh mở (Open) : là những đỉnh giả thiết sẽ được xem xét ở bước sau. + Đỉnh ẩn (Hiden) : là những đỉnh mà tại đó hàm g(n) chưa được xác định. Thuật giải AT Bước 1: + Mọi đỉnh n, mọi giá trị g(n) đều là ẩn. + Mở đỉnh đầu tiên và gọi đó là đỉnh S. Đặt g(S) = 0. Bước 2 : Chọn đỉnh mở với giá thành g tương ứng là nhỏ nhất và gọi đó là đỉnh N. + Nếu N là mục tiêu: đường đi từ đỉnh ban đầu đến N là đường đi ngắn nhất và bằng g(N). Dừng (Success). + Nếu không tồn tại một đỉnh mở nào nữa: cây biểu diễn vấn đề không có đường đi tới mục tiêu. Dừng (Fail). + Nếu tồn tại nhiều hơn 1 đỉnh N (nghĩa là có 2 đỉnh N trở lên) mà có cùng giá thành g(N) nhỏ nhất. Kiểm tra xem trong số đó có đỉnh nào là đích hay không. Nếu có: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N), dừng (Success). Nếu không có: Chọn ngẫu nhiên một trong các đỉnh đó và gọi là đỉnh N. Bước 3: Đóng đỉnh N và mở các đỉnh sau N (là những đỉnh có cung hướng từ N tới). Tại mọi đỉnh S sau N tính : g(S) = g(N) + cost(N S) Bước 4: Quay lại bước 2 Thuật giải AT- Ví dụ Thuật giải AT- Ví dụ Mọi đỉnh n, g(n) chưa biết. B1: Mở S, đặt g(S) = 0. B2: Đóng S; mở A, B, C, D g(A) = g(S) + gt(S A) = 0 + 100 = 100 g(B) = 0 + 17 = 17 g(C) = g(D) = 0 + 1 = 1 (min) Chọn ngẫu nhiên giữa C, D: chọn C B3: Đóng C, mở G, H: g(A) = 100 g(B) = 17 g(D) = 1 (min) g(G) = 11 g(H) = 21 Thuật giải AT- Ví dụ B4: Đóng D, mở I, J: g(A) = 100 g(B) = 17 g(I) = 13 g(J) = 2 (min) g(G) = 11 g(H) = 21 B5: Đóng J, mở N: g(A) = 100 g(B) = 17 g(I) = 13 g(G) = 11 g(H) = 21 g(N) = 3 (min) Thuật giải AT- Ví dụ B6: Đóng N, mở P: g(A) = 100 g(B) = 17 g(I) = 13 g(G) = 11 g(H) = 21 g(P) = 4 (min) B7: Đóng P, mở R: g(A) = 100 g(B) = 17 g(I) = 13 g(G) = 11 g(H) = 21 g(R) = 5 (min) R là đích. Vậy đường đi là: Nhận xét: Thuật toán này chỉ sử dụng 3 thông

• Kỹ thuật lập trình
• leo đồi dốc đứng
• leo đồi đơn giản
• tìm kiếm leo đồi
• tài liệu học đại học
• thủ tục min max
• thuật giải AT
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Kỹ thuật phân tích giải thuật
• Đánh giá giải thuật
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Phân tích thiết kế giải thuật
• Kỹ thuật thiết kế giải thuật
• Thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Bài giảng phân tích thiết kế giải thuật
• Chia để trị
• Giải thuật quay lui
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• Giải thuật đệ quy
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật sắp xếp nổi bọt
• Giải thuật sắp xếp chèn
• Giải thuật sắp xếp chọn
• Giải thuật tham lam
• Quy hoạch động
• Giải thuật nâng cao
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• khái niệm giải thuật
• mã giá điều khiên
• biểu diễn giải thuật
• bài toán và giải thuật
• thuật toán giải thuật
• thủ thuật lập trình
• giải thuật chia để trị
• giải thuật quicksort
• giải thuật mergesort
• giải thuật heapsort
• giải thuật couting sort
• Kỹ thuật mã hóa
• độ phức tạp của giải thuật
• cấu trúc của điều khiển
• phương pháp giải thuật
• hiệu quả của giải thuật
• Giải thuật lập trình
• Giáo trình giải thuật
• Khoa học máy tính
• Giải thuật lưu trữ ngoài
• bài giảng
• giải thuật nhánh và cận
• giải thuật DFS
• bài toán DFS
• thuật giải
• bài tập thuật giải
• luyện thi thuật giải
• tài liệu thuật giải
• lập trình với thuật giải
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật