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
103
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
462012
59
Giới thiệu :Lập trình mã nguồn mở
14
23544
70
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
11084
535
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10307
454
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
9609
106
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8570
1146
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8337
423
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7918
2242
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6939
260
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
6558
1581
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
Giáo án mầm non chương trình đổi mới: Đề tài: Ôn xác định vị trí trên – dưới, trước- sau của đối tượng khác.
8
411
3
16-06-2024
Động cơ đốt trong và máy kéo công nghiêp tập 1 part 7
23
281
0
16-06-2024
extremetech Hacking BlackBerry phần 9
31
275
0
16-06-2024
Anh văn bằng C-124
8
206
0
16-06-2024
TƯƠNG QUAN GIỮA MÔ HỌC, GIẢI PHẪU VÀ HÌNH ẢNH CỦA CÁC KHỐI U PHẦN PHỤ
3
184
1
16-06-2024
Báo cáo nghiên cứu khoa học " KẾT QUẢ NGHIÊN CỨU BƯỚC ĐẦU VỀ THIÊN ĐỊCH CHÂN KHỚP TRÊN CÂY THANH TRÀ Ở THỪA THIÊN HUẾ "
7
198
1
16-06-2024
HƯỚNG DẪN SỬ DỤNG PHẦN MỀM CAITA part 9
18
147
0
16-06-2024
Bài Tiểu Luận Chuyên Đề Tổ Chức Hoạt Động Nhận Thức Trong Dạy Học Vật Lý " Định Luật Ôm Cho Các Loại Đoạn Mạch Chứa Nguồn Điện"
10
174
3
16-06-2024
MẪU GIẤY PHÉP VẬN TẢI LOẠI C
2
132
0
16-06-2024
GYNECOLOGIC CANCERS IN PREGNANCY: GUIDELINES OF AN INTERNATIONAL CONSENSUS MEETING
12
115
0
16-06-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7918
2242
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
6558
1581
Ebook Chào con ba mẹ đã sẵn sàng
112
3968
1296
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5602
1170
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8570
1146
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3611
664
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3820
581
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
11084
535
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4261
528
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4273
483
Đã 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.