TAILIEUCHUNG - Bài giảng Thuật toán ứng dụng: Thuật toán Tham lam - Trương Xuân Nam

Bài giảng Thuật toán ứng dụng: Thuật toán Tham lam cung cấp cho người học những kiến thức như: Ý tưởng tham lam; Bài toán đổi tiền; Bài toán lập lịch; Tóm lược về tiếp cận tham lam; Bài tập. Mời các bạn cùng tham khảo! | THUẬT TOÁN ỨNG DỤNG Thuật toán Tham lam Nội dung 1. Ý tưởng tham lam 2. Bài toán đổi tiền 3. Bài toán lập lịch 4. Tóm lược về tiếp cận tham lam 5. Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Ý tưởng tham lam TRƯƠNG XUÂN NAM 3 Ý tưởng tham lam Bài toán tối ưu tìm cực trị theo hàm mục tiêu hoặc ҧ Quay lui Duyệt toàn bộ mọi cấu hình x Ghi nhận cực trị của hàm f x Nhánh cận Vẫn là quay lui Quay lui sớm nếu đánh giá thấy nhánh hiện tại không đủ tốt Vấn đề thời gian thực hiện vẫn quá lớn do độ phức tạp tính toán vẫn là hàm mũ TRƯƠNG XUÂN NAM 4 Ý tưởng tham lam Cấu hình đầu tiên là rỗng A Tìm cách xây dựng dần dần các phần tử a1 a2 . aN Quy tắc xây dựng phần tử ak Nếu k gt N cấu hình A đã hoàn chỉnh ghi nhận và kết thúc Xây dựng tập Sk chứa mọi giá trị có thể của ak Chọn một giá trị trong Sk đem lại lợi ích lớn nhất cho hàm mục tiêu gán cho ak nhận giá trị này Lặp lại quá trình để xây dựng phần tử ak 1 Như vậy tham lam dựa trên quay lui nhưng Không có bước quay lui Không cần viết đệ quy Thế nào là lợi ích lớn nhất Phần 2 Bài toán đổi tiền TRƯƠNG XUÂN NAM 6 Bài toán đổi tiền Một cửa hàng bán lẻ sử dụng các đồng xu 1 5 10 25 100 cents để trả lại tiền thừa cho khách. Đưa ra cách thức trả cho khách sử dụng số lượng đồng tiền là ít nhất. Ví dụ - Cần đổi 34 cents thì sử dụng 1 đồng 25 cents 1 đồng 5 cents và 4 đồng 1 cent - Khách cần đổi 2 usd 89 cents - 2 đồng 1 usd - 3 đồng 25 cents - 1 đồng 10 cents - 4 đồng 1 cent TRƯƠNG XUÂN NAM 7 Bài toán đổi tiền N là giá trị tiền lẻ phải trả lại khách Đặt số đồng xu loại 100 25 10 5 1 cent cần trả lại khách lần lượt là a1 a2 a3 a4 a5 N 100 x a1 25 x a2 10 x a3 5 x a4 1 x a5 Bài toán trở thành tìm cấu hình A a1 a2 a3 a4 a5 có F A a1 a2 a3 a4 a5 nhỏ nhất Có thể giải bằng quay lui xét mọi cấu hình A và ghi nhận cấu hình tốt nhất Nhưng ta nhận thấy giá trị a1 càng lớn càng tốt Vì nếu a1 bớt đi một thì phải thay thế đồng xu 100 bằng các loại khác nhỏ hơn. Chẳng hạn 4 đồng xu 25 cents hoặc 10 đồng xu 10 cents hoặc 20 đồng xu 10 cent hoặc 100 đồng xu 1

• Cơ sở dữ liệu
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Thuật toán Tham lam
• Ý tưởng tham lam
• Bài toán lập lịch
• Tiếp cận tham lam
• Phân tích Thuật toán
• Quy hoạch động
• Cài đặt thuật toán
• Toán ứng dụng
• Bài giảng Toán ứng dụng
• Biểu diễn đồ thị
• Thuật toán tìm kiếm
• Bài toán đường đi ngắn nhất
• Thuật toán Floyd
• Tiếp cận chia để trị
• Bài toán tháp Hà Nội
• Bài toán tính giá trị đa thức
• Bài toán đếm số dãy con
• Bài giảng Ma trận
• Khái niệm thuật toán
• Thuật toán trong tin học
• Phương pháp biểu diễn thuật toán
• Cấu trúc dữ liệu
• Chương trình nhân hai số nguyên
• Kỹ năng phân loại bài toán
• Kỹ năng phân tích thuật toán
• Quay lui đệ qui
• Bài toán quy hoạch động
• Thuật toán quay lui
• Liệt kê nhị phân
• Đệ quy quay lui
• Bài toán liệt kê xâu nhị phân
• Phương trình tuyến tính
• Thuật toán nhánh và cận
• Chu trình Euler
• Thuật toán Dijkstra
• Thuật toán Kruskal
• Disjoint set structure
• Bài toán xếp ba lô
• Bài toán dãy con chung dài nhất
• Phân tích về quy hoạch động
• Biểu diễn đồ thị trong máy tính
• Thuật toán Floyd Warshall
• Đồ thị phẳng
• Thư viện cấu trúc dữ liệu
• Cấu trúc dữ liệu mở
• Thuật toán Dequeue
• Chia để trị
• Thuật toán chia để trị
• Công thức truy hồi
• Tìm kiếm nhị phân
• Thuật toán Tarjan DFS
• Duyệt theo chiều sâu
• Cấu trúc dữ liệu duy trì
• Cấu trúc dữ liệu trừu tượng
• Giải thuật tìm kiếm
• Cài đặt tìm kiếm ở thư viện
• Hàm đệ quy
• Quy tắc xây dựng phần tử
• Nhánh cận
• Chiến lược tìm kiếm tối ưu tổ hợp
• Danh sách tuyến tính
• Quan hệ tuyến tính
• Ngăn xếp dữ liệu
• Dãy con cực đại
• Dãy con tăng dần dài nhất
• Dãy con chung dài nhất
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Thuật toán quay lui tổng quát
• Ứng dụng của thuật toán quay lui
• Chuỗi nhị phân
• Bài giảng Lý thuyết tài chính ứng dụng
• Lý thuyết tài chính ứng dụng
• Kế toán doanh nghiệp
• Bản chất cuả tài chính
• Chức năng của tài chính
• Vai trò của tín dụng
• Tài chính doanh nghiệp
• Bài giảng Tin học 10 bài 8
• Bài giảng điện tử Tin học 10
• Bài giảng lớp 10 Tin học
• Bài giảng điện tử lớp 10
• Quy trình quản lý tin học
• Giải các bài toán khoa học kĩ thuật
• Những ứng dụng của tin học
• Bài giảng Kỹ thuật điện tử
• Kỹ thuật điện tử
• Vi mạch khuếch đại thuật toán
• Vi mạch thuật toán
• Thông số kỹ thuật vi mạch thuật toán
• Ứng dụng vi mạch thuật toán
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Cấu trúc dữ liệu và thuật toán
• Ứng dụng cây gia phả
• Ứng dụng cây thư mục
• Thiết kế thuật toán
• Bài giảng Phân tích thuật toán
• Thuật toán hoán vị
• Số nghịch thế
• Bảng nghịch thế
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Thuật toán tìm kiếm trên đồ thị
• Thuật toán tìm kiếm theo chiều sâu
• Thuật toán tìm kiếm theo chiều rộng
• Ứng dụng thuật toán tìm kiếm đồ thị