TAILIEUCHUNG - Bài giảng Cơ sở lập trình nâng cao - Chương 7: Phương pháp thiết kế thuật toán – tham lam

Bài giảng cung cấp cho người học các kiến thức: Phương pháp thiết kế thuật toán – tham lam, sơ đồ cài đặt, ưu điểm và khuyết điểm,. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu. chi tiết nội dung bài giảng. | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi PHƯƠNG PHÁP THIẾT KẾ THUẬT TOÁN – THAM LAM – Chương 7 2 Nội dung Giới thiệu Phương pháp Sơ đồ cài đặt Các ví dụ Ưu điểm và khuyết điểm 3 Hình ảnh 1 2 3 4 5 Giới thiệu Định nghĩa [Tham lam – Greedy]: Tham lam là một phương pháp thiết kế thuật toán để tìm nghiệm của bài toán tối ưu bằng cách xây dựng nghiệm dần dần từng bước. Tại mỗi bước: Chúng ta luôn luôn chọn giá trị tốt nhất tại thời điểm đó mà không quan tâm đến tương lai (tối ưu cục bộ) Chúng ta hy vọng việc chọn các tối ưu cục bộ tại mỗi bước sẽ cho tối ưu toàn cục 5 Phương pháp Phát biểu bài toán: Giả sử bài toán yêu cầu tìm phương án X=(x1, x2, , xn), trong đó xi được chọn ra từ tập Di. f(X) là hàm đánh giá sự tốt nhất của phương án X (f là hàm mục tiêu hay hàm chi phí) Phương pháp Phương pháp Tham lam Phương pháp Tham lam xây dựng dần nghiệm X của bài toán: Ban đầu X=( ) Giả sử đã xây dựng được (k-1) thành phần của nghiệm (x1, x2, , xk-1) Bây giờ ta mở rộng nghiệm thành (x1, x2, , xk-1, xk) bằng cách chọn xk là giá trị tốt nhất trong tập Dk Phương pháp Phương pháp Tham lam Thông thường tập D được sắp theo một trật tự tăng dần hay giảm dần theo tiêu chí nào đó từ đó giúp việc chọn giá trị tốt nhất cho xi sẽ dễ dàng hơn Bước 1 [Sắp xếp]: Sắp xếp dữ liệu D tăng dần hay giảm dần theo tiêu chí nào đó Bước 2 [Chọn giá trị tốt nhất]: Với mỗi thành phần xi. Ta tìm giá trị tốt nhất trong dữ liệu đã được sắp xếp trong bước 1 và thỏa điều kiện của bài toán để gán cho xi Sơ đồ cài đặt void Greedy1() { X=(); for (i=1; i<=n; i++) { Xác định Di; xi = SelectBest(Di); } } Sơ đồ 1: Sơ đồ cài đặt void Greedy2() { Sort(D); for (i=1; i<=n; i++) { - Chọn v là giá trị tốt nhất trong D và thỏa điều kiện bài toán - xi = v; - Bỏ v khỏi D } } Sơ đồ 2: Chú ý Một ý tưởng đối nghịch với phương pháp “tham lam” là ý tưởng “trông rộng”: Gom .

• Kỹ thuật lập trình
• Bài giảng Cơ sở lập trình nâng cao
• Cơ sở lập trình nâng cao
• Phương pháp thiết kế thuật toán tham lam
• Thiết kế thuật toán
• Sơ đồ cài đặt
• Nội dung cơ sở lập trình nâng cao
• Cơ sở lập trình
• Lập trình đệ quy
• Phương pháp quay lui
• Cơ sở dữ liệu nâng cao
• Bài giảng Cơ sở dữ liệu nâng cao
• Giao diện lập trình
• Giao diện lập trình C
• Giao diện lập trình JAVA
• Giao diện lập trình PHP
• Cài đặt hàm đệ quy
• Phân loại đệ quy
• Phương pháp khử đệ quy
• Tối ưu hóa chương trình
• Loại tối ưu
• Quy tắc vòng lặp
• Quy tắc hàm
• Quy tắc biểu thức
• Ôn tập kỹ thuật xử lý file
• Xử lý mảng
• Xử lý xâu ký tự
• Thuật toán cơ bản
• Phương pháp thiết kế thuật toán
• Toán hình học
• Cấu trúc dữ liệu cơ bản
• Điểm và đa giác
• Cơ sở dữ liệu
• Cơ sở dữ liệu phân tán
• Cơ sở dữ liệu hướng đối tượng
• Lập trình PL/SQL
• Quy hoạch động
• Bài toán tối ưu
• Sơ đồ cài đặt
• Độ phức tạp của thuật toán
• Ước lượng độ phức tạp
• Phân tích thuật toán
• Thời gian thực hiện thuật toán
• Phương pháp thiết kế thuật toán quay lui
• Phương pháp thiết kế thuật toán nhánh cận
• Chia để trị
• Sơ đồ cài đặt
• Tìm kiếm nhị phân
• Giáo trình cơ sở lập trình
• Tài liệu cơ sở lập trình
• Kỹ thuật lập trình
• Bài toán con trùng lắp
• Phương pháp quy lui
• Bài giảng Lập trình hướng đối tượng nâng cao
• Lập trình hướng đối tượng nâng cao
• Lập trình hướng đối tượng
• Mô hình đa lớp
• Lập trình windows form
• Độ phức tạp thuật toán
• Kỹ thuật xử lý mảng
• Kỹ thuật xử lý file văn bản
• Hàm đệ quy
• Phương pháp Đệ qui
• Thuật toán Insertion sort
• Phương pháp Tham lam
• Thuật toán Merge sort
• Thuật toán Dijkstra
• Cấu trúc dữ liệu
• Thuật toán Viterbi
• Kết nối cơ sở dữ liệu