Materi
Layanan kurir di sebuah kota kecil punya dua masalah. Rute antarhalte dicari dengan tangan sehingga kurir sering melewati lebih banyak transit daripada perlu. Pemindai di gudang memeriksa resi ganda dengan list, dan setiap sore pemeriksaannya melambat sampai antrean truk menumpuk. Misi ini meminta struktur dan algoritma yang tepat untuk keduanya, dan alasan pemilihannya.
Memilih dimulai dari satu pertanyaan: operasi apa yang dijalankan paling sering, dan berapa biayanya di setiap struktur? Struktur yang tepat untuk satu operasi bisa sangat lambat untuk operasi lain. Tabel di bawah merangkum biaya yang sudah dibahas di kelas ini; n adalah banyaknya data, V dan E banyaknya simpul dan sisi graf.
| Kebutuhan | Struktur atau algoritma | Biaya |
|---|---|---|
| Ambil yang paling baru | Tumpukan (list.append, list.pop) | tetap per operasi |
| Ambil yang paling lama | Antrean (deque.popleft) | tetap per operasi |
| Sudah ada atau belum | set atau dict | rata-rata tetap |
| Ambil prioritas tertinggi berulang | heapq | log n per operasi |
| Data urut yang terus disisipi | Pohon pencarian biner seimbang | log n per operasi |
| Transit paling sedikit | BFS | V + E |
Rute kurir memakai graf berarah halte. Rute yang diminta adalah urutan halte dari awal sampai tujuan dengan jumlah transit paling sedikit; bila ada lebih dari satu, yang dipakai adalah yang ditemukan lebih dulu menurut urutan tetangga di daftar. Untuk merangkai rutenya, catat dari mana setiap halte pertama kali dicapai, lalu telusuri catatan itu mundur dari tujuan.
