Algoritma, jaringan, dan pemrograman linear
Diperkenalkan| English | Makna |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | pohon rentang minimum |
Rangkaian termurah atau laluan terpendek?
- Sebuah sekolah mesti menyambungkan bangunan dengan kabel. Laluan terpendek antara dua bangunan dan rangkaian keseluruhan termurah adalah masalah yang berbeza.
- Pelajaran ini mengaji pokok rentang minimum: Rangkaian bersambung tanpa kitaran yang menyambungi setiap bucu dengan jumlah berat tepi yang paling kecil.
Pilih struktur matematika
- Kruskal memilih tepi secara bertambah berat sambil mengelakkan kitaran. Dijkstra mengemas kini jarak sementara terpendek dari titik permulaan. Pengoptimuman linear mengoptimumkan fungsi objektif linear atas kawasan layak; periksa bucu dan kekangan integer apabila diperlukan.
- Nyatakan input yang diperbolehkan dan satuan sebelum menghitung. Persamaan harus mengekspresikan hubungan, bukan sekadar mencatat entri kalkulator.
Algoritma Kruskal dan jalur terpendek keduanya menghasilkan total 6 pada jaringan contoh. Mengapa hal itu tidak membuatnya dapat saling menggantikan?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Tujuannya berbeda: pohon rentang minimum menghubungkan semua titik simpul (n-1 sisi, tanpa siklus), sementara jalur terpendek mengoptimalkan rute asal-tujuan tunggal. Jawaban sama di sini adalah kebetulan.
Kerjakan kasus yang dicek
- Periksa hasilnya terhadap besaran awal. Substitusikan ke dalam hubungan asli, atau bandingkan grafik dan jawaban numerik jika sesuai.
Untuk bucu A,B,C,D dan tepi AB=2, BC=3, AC=4, CD=1, BD=5, Kruskal memilih CD, AB, BC untuk jumlah 6. Laluan A-ke-D terpendek ialah A-B-C-D, juga 6, tetapi kesamaan itu hanyalah kebetulan. Maksimumkan 3x+2y dengan x+y≤4, x≤2, x,y≥0: bucu terbaik ialah (2,2), nilai 10.
Algoritma, jaringan, dan pemrograman linear
Kruskal memilih sisi dengan bobot meningkat sambil menghindari siklus
Bandingkan model dengan kasus yang diselesaikan dan jelaskan satu perubahan.
Temukan bobot pohon rentang minimum untuk contoh jaringan.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Kruskal memilih bobot sisi 1,2,3 tanpa siklus, menghubungkan setiap titik: total 6.
Uji jalan pintas yang menggoda
- Pokok rentang tidak mempunyai kitaran dan menyambungi semua bucu. Tepi tunggal terbesar tidak secara automatiknya dikecualikan daripada setiap penyelesaian optimum. Algoritma laluan terpendek tidak boleh menggantikan algoritma pokok rentang minimum.
- Ketika jalan pintas gagal, identifikasi asumsi yang dilanggar. Pertahankan nilai eksak hingga pembulatan akhir yang diminta.
Laluan terpendek antara dua bucu mesti juga menjadi pokok rentang minimum bagi seluruh rangkaian. Tuntutan ini adalah salah. Terangkan definisi atau andaian mana yang dilanggar.
Temukan nilai maksimum dari 3x+2y untuk daerah layak contoh.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Periksa titik-titik layak: (2,2) menghasilkan 3×2+2×2=10, nilai tujuan terbesar.
Jalur terpendek antara dua titik juga merupakan pohon rentang minimum dari seluruh jaringan.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Pohon rentang tidak memiliki siklus dan menghubungkan semua titik. Sisi tunggal terbesar tidak secara otomatis dikecualikan dari setiap solusi optimal. Algoritma jalur terpendek tidak dapat menggantikan algoritma pohon rentang minimum.
Interpretasikan situasi baru
- Untuk laluan kritikal, kira masa peristiwa awal dan akhir serta kenal pasti aktiviti dengan sifar kelongsoran. Nyatakan unit dan tafsirkan optimum. Arkib sedia ada tiada pasangan D1, jadi tugasan asli ini tidak menubuhkan bank soalan kertas peperiksaan D1 yang ditinjau.
- Solusi lengkap memberikan hasil matematis dan menjelaskan maknanya. Periksa apakah hal itu mungkin dalam konteks yang dinyatakan.
Berapa banyak sisi yang dimiliki pohon rentang pada 4 titik?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Pohon pada n titik memiliki n-1 sisi, sehingga empat titik memerlukan tiga.
Pasangkan setiap algoritma dengan aturannya.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Setiap algoritma tepat untuk kelas masalahnya sendiri; menelusuri aturan yang disebutkan, termasuk penanganan seri, adalah yang mendapatkan nilai.
Gunakan ini dalam kursus anda
- edexcel IAL matematika; unit resmi D1. Pengayaan unit lain diidentifikasi dalam tinjauan cakupan; ini bukan persyaratan tambahan untuk pencairan uang.
- Berikan metodenya sebelum jawaban akhir, dan gunakan aturan kalkulator serta rumus pada kertas ujian. Tinjau jawaban yang salah dengan menemukan langkah pertama yang tidak valid.
Rangkaian bersambung tanpa kitaran yang menyambungi setiap bucu dengan jumlah berat tepi yang paling kecil. Pilih hubungan, tunjukkan kaedah, periksa andaannya dan tafsirkan hasilnya.