Sắp xếp, đóng gói và thuật toán mạng
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| algorithm/ˈælɡərɪθəm/ | thuật toán |
Phương pháp đóng gói nhanh có luôn tối ưu?
- Một phương pháp đóng gói nhanh có thể lấp đầy hộp, nhưng một sắp xếp hợp lệ nhanh chưa chắc sử dụng số lượng hộp ít nhất.
- Bài học này nghiên cứu thuật toán: Một tập hữu hạn các lệnh được sắp xếp thứ tự giải quyết một lớp vấn đề xác định.
Chọn cấu trúc toán học
- Theo dõi thuật toán được nêu tên chính xác, bao gồm cả các quy tắc xử lý trường hợp ngang hàng. Trong đóng gói First-fit, đặt mỗi mục vào thùng chứa đầu tiên có thể chứa nó. First-fit decreasing sắp xếp trước khi áp dụng first-fit. Một heuristic có thể đúng đắn mà không cần tối ưu.
- Nêu rõ các đầu vào và đơn vị được phép trước khi tính toán. Một phương trình nên biểu diễn mối quan hệ, chứ không chỉ ghi lại một lần nhập liệu trên máy tính.
Thuật toán First-fit sử dụng 2 thùng chứa cho 6,5,4,3,2 với dung lượng 10, khớp với cận dưới. Điều gì có thể kết luận?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Việc đạt cận dưới chỉ chứng minh tính tối ưu cho trường hợp này. Sự thành công của một heuristic trên một ví dụ không nói lên điều gì về các trường hợp xấu nhất - các danh sách mặt hàng khác có thể khiến First-fit vượt quá cận dưới.
Làm qua một trường hợp đã kiểm tra
- Kiểm tra kết quả so với các lượng ban đầu. Thay thế vào mối quan hệ gốc, hoặc so sánh đồ thị và câu trả lời số học khi phù hợp.
Với dung tích thùng chứa 10 và các vật phẩm 6,5,4,3,2 theo thứ tự đó, thuật toán fit-first đặt 6 và 4 vào thùng 1, sau đó đặt 5,3,2 vào thùng 2. Nó sử dụng 2 thùng. Tổng kích thước là 20, nên cận dưới là ceil(20/10)=2; cách sắp xếp này tối ưu cho trường hợp này.
Sắp xếp, đóng gói và thuật toán mạng
Truy vết thuật toán được đặt tên một cách chính xác, bao gồm cả các quy tắc liên kết.
So sánh mô hình với ví dụ đã giải thích và giải thích một sự thay đổi.
Sơ đồ first-fit mẫu đầu tiên sử dụng bao nhiêu thùng chứa?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Sơ đồ first-fit mẫu lấp đầy hai thùng chứa, mỗi thùng có tổng kích thước là 10.
Thử một cách tắt hấp dẫn
- Một ví dụ về thành công không chứng minh heuristic luôn tối ưu. Giữ lại danh sách trung gian trong quá trình theo dõi sắp xếp; đừng nhảy từ đầu vào sang danh sách đã sắp xếp cuối cùng. Cập nhật đường đi ngắn nhất phải giữ thông tin tiền nhiệm nếu yêu cầu tuyến đường.
- Khi một cách tắt thất bại, hãy xác định giả thiết mà nó vi phạm. Giữ nguyên giá trị chính xác cho đến khi làm tròn cuối cùng theo yêu cầu.
Một heuristic đóng gói hoạt động tốt trên một ví dụ thì luôn tối ưu. Phát biểu này sai. Hãy giải thích định nghĩa hoặc giả thiết nào bị vi phạm.
Tìm cận dưới đối với số thùng chứa cho tổng kích thước 20 và dung tích 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Mỗi thùng chứa chứa tối đa 10, nên cần ít nhất ceiling(20/10)=2 thùng chứa.
Một heuristic đóng gói hoạt động tốt trên một ví dụ không nhất thiết luôn tối ưu.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Một ví dụ thành công không chứng minh được heuristic luôn tối ưu. Giữ các danh sách trung gian trong quá trình truy vết sắp xếp; đừng nhảy từ đầu vào sang danh sách cuối đã sắp xếp. Việc cập nhật đường đi ngắn nhất phải giữ lại thông tin tiền nhiệm nếu yêu cầu một tuyến đường cụ thể.
Giải thích tình huống mới
- Đối với Dijkstra, chọn nhãn tạm thời chưa được chốt nhỏ nhất và cập nhật các lân cận của nó. Đối với bài toán kiểm tra tuyến đường, phân biệt tuyến đường kín và mở, xác định các đỉnh lẻ trước khi ghép cặp chúng.
- Một lời giải đầy đủ đưa ra kết quả toán học và giải thích ý nghĩa của nó. Kiểm tra xem điều đó có khả thi trong ngữ cảnh đã nêu hay không.
Tìm dung tích còn lại trong một thùng chứa vật dụng 5,3,2 với dung tích 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Dung tích chưa sử dụng = 10 - (5 + 3 + 2) = 0.
Gắn mỗi quy tắc đóng gói với hành động của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Theo dõi thuật toán đúng như đã định nghĩa; cận dưới đánh giá mức độ tốt nhất mà một cách đóng gói có thể đạt được.
Sử dụng trong khóa học của bạn
- Toán học IAL Edexcel; đơn vị chính thức D1. Sự làm phong phú từ các đơn vị khác được xác định trong việc xem xét phạm vi; đây không phải là yêu cầu thi thêm để lấy điểm.
- Trình bày phương pháp trước đáp án cuối cùng, và tuân thủ quy tắc sử dụng máy tính cũng như công thức trong đề thi. Xem xét lại câu trả lời sai bằng cách tìm bước đầu tiên vi phạm.
Một tập hữu hạn các lệnh được sắp xếp thứ tự giải quyết một lớp vấn đề xác định. Chọn mối quan hệ, trình bày phương pháp, kiểm tra các giả thiết và diễn giải kết quả.