Algoritma pengurutan, pengepakan, dan jaringan
Diperkenalkan| English | Makna |
|---|---|
| algorithm/ˈælɡərɪθəm/ | Algoritma |
Apakah metode pengemasan cepat selalu optimal?
- Metode pengemasan mengisi kotak dengan cepat, tetapi susunan valid yang cepat belum tentu menggunakan jumlah kotak terkecil.
- Pelajaran ini mempelajari algoritma: Kumpulan terbatas instruksi berurutan yang memecahkan kelas masalah yang didefinisikan.
Pilih struktur matematika
- Jejak algoritma yang dinamai secara tepat, termasuk aturan pemecah seri. Dalam pengemasan first-fit, tempatkan setiap item dalam bin pertama yang tersedia yang dapat menampungnya. First-fit decreasing mengurutkan sebelum menerapkan first-fit. Heuristik mungkin valid tanpa menjadi optimal.
- Nyatakan input yang diperbolehkan dan satuan sebelum menghitung. Persamaan harus mengekspresikan hubungan, bukan sekadar mencatat entri kalkulator.
Pertama-cocok digunakan 2 bin untuk 6,5,4,3,2 dengan kapasitas 10, sesuai batas bawah. Apa yang dapat disimpulkan?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Memenuhi batas bawah hanya membuktikan optimalitas untuk kasus ini. Keberhasilan heuristik pada satu contoh tidak memberikan informasi apa pun tentang kasus terburuk—daftar item lain membuat first-fit melebihi batas tersebut.
Kerjakan kasus yang dicek
- Periksa hasilnya terhadap besaran awal. Substitusikan ke dalam hubungan asli, atau bandingkan grafik dan jawaban numerik jika sesuai.
Dengan kapasitas bin 10 dan item 6,5,4,3,2 sesuai urutan tersebut, first-fit menempatkan 6 dan 4 dalam bin 1, kemudian 5,3,2 dalam bin 2. Algoritma ini menggunakan 2 bin. Total ukuran adalah 20, sehingga batas bawahnya adalah ceil(20/10)=2; susunan ini optimal untuk instansi ini.
Algoritma pengurutan, pengepakan, dan jaringan
Jejakkan algoritma yang dinamai secara tepat, termasuk aturan pemecah imbang
Bandingkan model dengan kasus yang diselesaikan dan jelaskan satu perubahan.
Berapa banyak bin yang digunakan oleh pengaturan first-fit yang dikerjakan?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Pengaturan first-fit mengisi dua bin, masing-masing dengan total ukuran 10.
Uji jalan pintas yang menggoda
- Contoh keberhasilan tidak membuktikan bahwa heuristik selalu optimal. Simpan daftar antara dalam jejak pengurutan; jangan melompat dari input ke daftar akhir yang telah diurutkan. Pembaruan jalur terpendek harus mempertahankan informasi pendahulu jika rute diminta.
- Ketika jalan pintas gagal, identifikasi asumsi yang dilanggar. Pertahankan nilai eksak hingga pembulatan akhir yang diminta.
Heuristik pengemasan yang bekerja baik pada satu contoh harus selalu optimal. Klaim ini salah. Jelaskan definisi atau asumsi mana yang dilanggar.
Temukan batas bawah untuk bin dengan total ukuran 20 dan kapasitas 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Setiap bin menampung paling banyak 10, sehingga diperlukan setidaknya ceiling(20/10)=2 bin.
Heuristic pengepakan yang bekerja baik pada satu contoh harus selalu optimal.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Sebuah contoh keberhasilan tidak membuktikan bahwa heuristic selalu optimal. Simpan daftar antara dalam jejak pengurutan; jangan melompat dari input ke daftar akhir yang sudah diurutkan. Pembaruan jalur terpendek harus mempertahankan informasi pendahulu jika rute diminta.
Interpretasikan situasi baru
- Untuk Dijkstra, pilih label sementara yang belum terselesaikan terkecil dan perbarui tetangganya. Untuk masalah inspeksi rute, bedakan rute tertutup dari yang terbuka dan identifikasi simpul ganjil sebelum memasangkannya.
- Solusi lengkap memberikan hasil matematis dan menjelaskan maknanya. Periksa apakah hal itu mungkin dalam konteks yang dinyatakan.
Temukan ruang tersisa dalam sebuah bin yang berisi item 5,3,2 dengan kapasitas 10.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Kapasitas tidak terpakai=10-(5+3+2)=0.
Cocokkan setiap aturan pengemasan dengan aksinya.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Jejakkan algoritma persis seperti yang didefinisikan; batas bawah menilai seberapa baik pengemasan mungkin bisa dilakukan.
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.
Kumpulan terbatas instruksi berurutan yang memecahkan kelas masalah yang didefinisikan. Pilih hubungannya, tunjukkan metodenya, periksa asumsinya dan interpretasikan hasilnya.