Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Tài liệu HOT
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
0
Trang chủ
Khoa Học Tự Nhiên
Toán học
Thuật toán tham lam trong xây dựng cấu hình tổ hợp
TAILIEUCHUNG - Thuật toán tham lam trong xây dựng cấu hình tổ hợp
Nội dung chính của bài viết trình bày Thuật toán tham lam là tìm tối ưu địa phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục. Dĩ nhiên thuật toán tham lam không đảm bảo được tối ưu địa phương sẽ cho ta lời giải tối ưu toàn cục. Mời các bạn tham khảo! | THUẬT TOÁN THAM LAM TRONG XÂY DỰNG CẤU HÌNH TỔ HỢP Trần Minh Hiền THPT Chuyên Quang Trung Bình Phước Thuật toán tham lam là tìm tối ưu địa phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục. Dĩ nhiên thuật toán tham lam không đảm bảo được tối ưu địa phương sẽ cho ta lời giải tối ưu toàn cục. Nhưng trong nhiều bài toán việc này sẽ xảy ra. Ví dụ quot Cho trước một tập hợp S các đồng xu. Khi đó cần lấy ít nhất bao nhiêu đồng xu trong S để được tổng số tiền M cho trước. Khi S D f1 5 10 25g chúng ta có thể áp dụng thuật toán tham lam để xây dựng phương án tối ưu như sau Thêm đồng xu x lớn nhất trong S sao cho x M Áp dụng lại thuật toán cho M x. Ví dụ với M D 91 đầu tiên ta chọn 25 trong S sau đó lại tiếp tục áp dụng thuật toán cho 91 25 D 66. Khi đó ta lại tiếp tục chọn số tục áp dụng thuật toán cho 66 25 D 41 ta chọn số 25. Lại áp dụng thuật toán cho 41 25 D 16 ta sẽ chọn số 10. Lại tiếp tục áp dụng thuật toán cho 16 10 D 6 thì ta chọn số 5. Và cuối cùng áp dụng thuật toán cho 6 5 D 1 ta chọn số 1. Từ đó tập hợp tối ưu là f25 25 25 10 5 1g. Tức là với tập S D f1 5 10 25g thuật toán tham lam cho ta phương án tối ưu. Tuy nhiên thuật toán tối ưu không phải lúc nào cũng cho ta phương án tối ưu. Ví dụ với S D f1 3 4g và M D 6 thuật toán tham lam cho ta tập f1 1 4g tuy nhiên phương án tối ưu là f3 3g. quot Dưới đây là một số bài toán minh họa. Câu 1 BMO 1998 . Một đại lý vé tàu hỏa phân phối vé tàu hỏa cho 200 đại lý. Trong một ngày đặc biệt có tất cả 3800 người ở 200 đại lý đến mua vé mỗi người được mua một vé. 1. Chứng minh rằng có ít nhất 6 đại lý có cùng số người đến mua vé trong ngày hôm đó. 2. Ý trên không còn đúng nếu thay 6 bởi số 7. Lời giải. 1. Gọi s1 s2 s200 là số người đến đại lý thứ nhất đại lý thứ hai đại lý thứ 200 mua vé tàu hỏa trong ngày đó. Không mất tính tổng quát ta có thể giả sử s1 s2 s200 . Đặt S D s1 C s2 C C s200 thì S D 3800. Bây giờ ta sẽ tìm hiểu S nhỏ nhất bao nhiêu khi điều kiện bài toán không thỏa tức không tồn tại dãy si si C1
Uyển Khanh
99
16
pdf
Báo lỗi
Trùng lắp nội dung
Văn hóa đồi trụy
Phản động
Bản quyền
File lỗi
Khác
Upload
Tải xuống
đang nạp các trang xem trước
Bấm vào đây để xem trước nội dung
Tải xuống
TÀI LIỆU LIÊN QUAN
Bài giảng Thuật toán ứng dụng: Thuật toán Tham lam - Trương Xuân Nam
23
42
4
Bài giảng Phương pháp tham lam
24
47
5
Bài giảng Thuật toán nâng cao: Chương 7 - Nguyễn Thanh Bình
33
105
2
Bài giảng Toán rời rạc: Thuật toán tham lam - Trần Vĩnh Đức
64
33
3
Thuật toán tham lam trong xây dựng cấu hình tổ hợp
16
80
4
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
29
113
1
Bài giảng Toán rời rạc: Tô màu đỉnh của đồ thị - Trần Vĩnh Đức
44
64
2
Đề thi Phân tích và thiết kế thuật toán
5
163
4
Bài giảng Thuật toán: Chương 3 - GV. Nguyễn Thanh Cẩm
67
128
1
Bài giảng Phân tích và thiết kế thuật toán: Kỹ thuật Greedy (Tham lam) - Phạm Thế Bảo
7
141
2
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
461742
55
Giới thiệu :Lập trình mã nguồn mở
14
22075
54
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10740
524
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
9929
445
Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3
9427
104
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8134
1122
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8134
421
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7819
2212
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6502
247
Vật lý hạt cơ bản (1)
29
5680
81
TỪ KHÓA LIÊN QUAN
Toán học
Thuật toán tham lam
Xây dựng cấu hình tổ hợp
Phương pháp giải toán
Toán đại số
Lý thuyết tối ưu toàn cục
Bài giảng Thuật toán Ứng dụng
Thuật toán Ứng dụng
Ý tưởng tham lam
Bài toán lập lịch
Tiếp cận tham lam
Bài giảng Phương pháp tham lam
Phương pháp tham lam
Giải thuật tham lam
Greedy algorithm
Bài toán tối ưu
Thuật toán nâng cao
Bài giảng Thuật toán nâng cao
Greedy algorithms
Nguyên tắc thuật toán tham lam
Cấu trúc tổng quát
Độ phức tạp của thuật toán
Bài giảng Toán rời rạc
Toán rời rạc
Cây bao trùm nhỏ nhất
Mã hóa Huffman
Công thức Horn
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
Tô màu đỉnh của đồ thị
Thuật toán tham lam tô màu đỉnh
Đồ thị hai phần
Phân tích thiết kế thuật toán
Đề thi Phân tích thiết kế thuật toán
Câu hỏi Phân tích thiết kế thuật toán
Ôn tập Phân tích thiết kế thuật toán
Trình diễn thuật toán
Ngôn ngữ lập trình
Bài giảng thuật toán
Biểu diễn thuật toán
Cài đặt thuật toán
Kỹ thuật thiết kế thuật toán
Phân tích thuật toán
Đáng giá thuật toán
Bài giảng Phân tích thuật toán
Kỹ thuật Greedy
Bài toán tối ưu tổ hợp
Bài toán trả tiền của ATM
Phân tích thiết kế giải thuật
Bài toán cái túi
Bài toán người du lịch
Bài toán đường đi ngắn nhất
Bài toán cây bao trùm nhỏ nhất
Bài toán tô màu
Bài toán các khoảng không giao nhau
Phân tích và thiết kế thuật toán
Độ phức tạp thuật toán
Đánh giá thuật toán
Phương pháp chia để trị
Quy hoạch động
Thuật toán đồ thị cơ bản
Bài giảng công nghệ thông tin
Tập bài giảng Thiết kế và đánh giá thuật toán
Kỹ thuật chia để trị
Kỹ thuật tham lam
Kỹ thuật quay lui
Bài giảng Thiết kế và đánh giá thuật toán
Thiết kế và đánh giá thuật toán
thuật toán
chuyên đề toán học
thuật toán đệ quy
thuật toán lập trình
Điều khiển quá trình Mimo
Sử dụng mạng Nơ ron
Nơ ron thích nghi với thuật toán MFA
Mô hình tham chiếu
Hệ bồn nước đôi
Kĩ thuật giải nhanh bài toán Hóa học
Giải bài toán Hóa học nhanh
Cách giải Hóa học nhanh
Tìm hiểu kỹ thuật giải Hóa học nhanh
Tham khảo cách giải bài toán Hóa học
Hướng dẫn làm bài toán Hóa học nhanh
thuật toán cặp ghép
thời khóa biểu trường chuyên
luận văn
kỹ thuật điện
luận văn thạc sỹ
khoa học máy tính
thiết kế hệ thống
Giáo trình Phân tích thiết kế thuật toán
Lập trình máy tính
Phương pháp quay lui
Chứng minh sự đúng đắn
Độ phức tạp
Chia để trị
Thiết kế giải thuật
Phân tích giải thuật
Qui hoạch động
Bài toán nhân xâu
Cấu trúc dữ liệu
giải thuật
tài liệu giải thuật
lý thuyết giải thuật
chuyên ngành công nghệ thông tin
Bài giảng Các hệ thống thông minh nhân tạo
Hệ thống thông minh nhân tạo
Bài toán tìm kiếm 2
Tìm kiếm tham lam
Thuật giải A*
Hàm ước lượng mức độ
Cơ sở lập trình
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
Thuật toán Merge sort
TÀI LIỆU MỚI ĐĂNG
Đánh giá hao mòn và độ tin cậy của chi tiết và kết cấu trên đầu máy diezel part 3
12
282
0
29-03-2024
Báo cáo khoa học: Loss of kinase activity in Mycobacterium tuberculosis multidomain protein Rv1364c
14
221
0
29-03-2024
Động cơ đốt trong và máy kéo công nghiêp tập 1 part 7
23
245
0
29-03-2024
Coherence and Ultrashort Pulse Laser Emission Part 9
40
237
0
29-03-2024
Động cơ đốt trong và máy kéo công nghiêp tập 2 part 8
32
250
0
29-03-2024
Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 2 - Chương 4
47
233
1
29-03-2024
Sẵn sàng cho thảm họa
9
210
0
29-03-2024
Getting StartED with Windows 7 phần 5
42
171
1
29-03-2024
Bơm máy nén quạt trong công nghiệp part 8
20
189
2
29-03-2024
MySQL Database Usage & Administration PHẦN 9
37
128
0
29-03-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7819
2212
Ebook Chào con ba mẹ đã sẵn sàng
112
3652
1219
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
5130
1173
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8134
1122
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5037
1084
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3403
638
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3620
524
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10740
524
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
3901
502
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4027
470
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.