Thuật toán, mạng lưới và lập trình tuyến tính
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | cây bao phủ tối thiểu |
Mạng rẻ nhất hay tuyến đường ngắn nhất?
- Một trường học cần nối các tòa nhà bằng cáp. Tuyến đường ngắn nhất giữa hai tòa nhà và mạng toàn bộ rẻ nhất là hai bài toán khác nhau.
- Bài học này nghiên cứu cây bao trùm tối thiểu: Một mạng liên thông không chu trình nối mọi đỉnh với tổng trọng số cạnh nhỏ nhất có thể.
Chọn cấu trúc toán học
- Kruskal chọn các cạnh theo thứ tự trọng số tăng dần trong khi tránh tạo chu trình. Dijkstra cập nhật các khoảng cách tạm thời ngắn nhất từ một điểm xuất phát. Quy hoạch tuyến tính tối ưu hóa một hàm mục tiêu tuyến tính trên miền khả thi; kiểm tra các đỉnh và giới hạn nguyên khi cần thiết.
- 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.
Cả thuật toán Kruskal và đường đi ngắn nhất đều cho tổng 6 trên mạng mẫu. Tại sao điều đó không khiến chúng thay thế lẫn nhau?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Mục tiêu khác nhau: cây bao phủ tối thiểu kết nối tất cả các đỉnh (n-1 cạnh, không có chu trình), trong khi đường đi ngắn nhất tối ưu hóa một tuyến điểm xuất phát - điểm đến duy nhất. Việc có đáp án giống nhau ở đây chỉ là tình cờ.
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.
Đối với các đỉnh A,B,C,D và các cạnh AB=2,BC=3,AC=4,CD=1,BD=5, Kruskal chọn CD,AB,BC với tổng 6. Tuyến đường ngắn nhất từ A đến D là A-B-C-D, cũng 6, nhưng sự bằng nhau này chỉ là tình cờ. Tối đa hóa 3x+2y với điều kiện x+y≤4,x≤2,x,y≥0: đỉnh tốt nhất là (2,2), giá trị 10.
Thuật toán, mạng lưới và lập trình tuyến tính
Kruskal chọn các cạnh theo trọng số tăng dần đồng thời tránh tạo chu trình
So sánh mô hình với ví dụ đã giải thích và giải thích một sự thay đổi.
Tìm trọng số cây bao trùm tối thiểu cho ví dụ về mạng lưới.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Kruskal chọn các trọng số cạnh 1,2,3 mà không tạo thành chu trình, kết nối mọi đỉnh: tổng 6.
Thử một cách tắt hấp dẫn
- Cây bao trùm không có chu trình và nối tất cả các đỉnh. Cạnh đơn lẻ lớn nhất không tự động bị loại bỏ khỏi mọi nghiệm tối ưu. Thuật toán tìm đường đi ngắn nhất không thể thay thế thuật toán cây bao trùm tối thiểu.
- 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 đường đi ngắn nhất giữa hai đỉnh cũng phải là cây bao trùm tối thiểu của toàn bộ mạng. tuyên bố này là sai. Hãy giải thích định nghĩa hoặc giả thiết nào mà nó vi phạm.
Tìm giá trị lớn nhất của 3x+2y trong miền khả thi cho ví dụ.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Kiểm tra các đỉnh khả thi: (2,2) cho 3×2+2×2=10, là giá trị mục tiêu lớn nhất.
Đường đi ngắn nhất giữa hai đỉnh cũng phải là cây bao trùm tối thiểu của toàn bộ mạng lưới.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Cây bao trùm không có chu trình và nối tất cả các đỉnh. Cạnh đơn lẻ lớn nhất không tự động bị loại khỏi mọi giải pháp tối ưu. Thuật toán đường đi ngắn nhất không thể thay thế thuật toán cây bao trùm tối thiểu.
Giải thích tình huống mới
- Đối với các đường găng, tính thời kiện sự kiện sớm nhất và muộn nhất và xác định các hoạt động có độ trễ bằng không. Nêu đơn vị và diễn giải kết quả tối ưu. Kho lưu trữ hiện tại không có cặp D1, do đó các nhiệm vụ gốc này không thiết lập ngân hàng đề thi đã xét D1.
- 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.
Cây bao trùm trên 4 đỉnh có bao nhiêu cạnh?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Cây trên n đỉnh có n-1 cạnh, nên bốn đỉnh cần ba cạnh.
Gắn mỗi thuật toán với quy tắc của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Mỗi thuật toán đều chính xác cho lớp bài toán riêng của nó; việc theo dõi quy tắc đã nêu, bao gồm cách xử lý khi có giá trị bằng nhau, sẽ mang lại điểm số.
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 mạng liên thông không chu trình nối mọi đỉnh với tổng trọng số cạnh nhỏ nhất có thể. 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ả.