Lewati ke konten utama
Numekara
Konsultasi GratisKontak

K1 · Modul 15

Rakus dan backtracking

45 langkah singkat, dari mudah sampai tantangan.

  1. Level 1

    Kenal

  2. Level 2

    Paham

  3. Level 3

    Terapkan

  4. Level 4

    Tantangan

  5. Level 5

    Pendalaman

Intinya

  • Algoritma rakus memilih yang terbaik saat ini dan tidak pernah mundur; ia benar hanya bila dibuktikan, misalnya dengan argumen tukar.
  • Pemilihan aktivitas (urutkan menurut waktu selesai) adalah contoh rakus yang terbukti benar; kembalian dengan sistem koin tertentu adalah contoh yang gagal.
  • Backtracking menjelajahi pohon pilihan (pilih, jelajahi, batalkan) dan memangkas cabang yang pasti kalah.
  • Untuk rute kunjungan banyak tujuan tidak ada algoritma polinomial yang diketahui; untuk sedikit tujuan, jawaban tepat masih terjangkau.

Sebelum mulai

±4–5 jam.

Modul ini memakai materi di bawah. Belum yakin? Ulas dulu bagian yang disebut.

Hasil belajar: setelah modul ini kamu bisa menjelaskan kapan algoritma rakus benar dan membuktikannya dengan argumen tukar; menunjukkan contoh tempat cara rakus gagal; memakai heap untuk partisi interval; menulis backtracking (pilih, jelajahi, batalkan) dengan pemangkasan; menghitung rute terbaik untuk beberapa tujuan secara tepat; serta menjelaskan intuisi P vs NP tanpa klaim berlebihan.

Proyek: Kurir Makmur langkah 15: jadwal_maksimal(interval) dengan pemilihan aktivitas rakus dan rute_terbaik(graf, dari, tujuan) dengan backtracking dan pemangkasan untuk paling banyak 8 tujuan (kontrak Proyek Kurir §3).

Istilah di modul ini (33)

Ketuk istilah untuk melihat penjelasannya. Di materi, istilah bergaris titik membuka kartu yang sama. Semua istilah course

Bahan modul

Semua kode, latihan, dan data modul ini dalam satu zip, untuk dijalankan di laptop atau Google Colab.

  • 23 contoh kode
  • 9 berkas latihan + tes
  • 1 berkas data
Semua data course (data-k1.zip) Cara menjalankan di laptop
Lihat isi zip
  • BACA-DULU.txt
  • kurir13.py
  • contoh_k1_15_100.py
  • contoh_k1_15_165.py
  • contoh_k1_15_240.py
  • contoh_k1_15_290.py
  • contoh_k1_15_356.py
  • contoh_k1_15_389.py
  • contoh_k1_15_793.py
  • contoh_k1_15_828.py
  • contoh_k1_15_966.py
  • contoh_k1_15_1079.py
  • contoh_k1_15_1106.py
  • contoh_k1_15_1141.py
  • contoh_k1_15_1178.py
  • contoh_k1_15_1211.py
  • contoh_k1_15_1335.py
  • contoh_k1_15_1717.py
  • contoh_k1_15_1784.py
  • contoh_k1_15_1810.py
  • contoh_k1_15_2127.py
  • contoh_k1_15_2166.py
  • contoh_k1_15_2238.py
  • contoh_k1_15_2293.py
  • contoh_k1_15_2311.py
  • test_k1_15_1.py
  • test_k1_15_4.py
  • test_k1_15_6.py
  • test_k1_15_3.py
  • test_k1_15_2.py
  • test_k1_15_5.py
  • test_k1_15_7.py
  • test_k1_15_8.py
  • test_k1_15_9.py
  • peta.json