Memangkas untuk Bertahan dari Batas Waktu
Memotong cabang yang tidak dapat menghasilkan perbaikan
Memangkas untuk Bertahan dari Batas Waktu adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Mengapa Pemangkasan Penting
Runut balik tanpa pemangkasan dapat menjelajahi terlalu banyak cabang dan mencapai batas waktu. Pemangkasan memotong cabang yang tidak menjanjikan sejak awal agar proses tetap cepat. ✂️
Apa Sebenarnya Pemangkasan Itu
Pemangkasan berarti menghentikan sebuah cabang begitu Anda dapat membuktikan bahwa cabang tersebut tidak mungkin menghasilkan jawaban yang valid atau lebih baik. Anda melewatkan seluruh penjelajahannya.
Pemangkasan Kelayakan
Jika pilihan parsial saat ini sudah melanggar suatu aturan, segera kembalikan hasilnya. Pemeriksaan kelayakan ini mencegah Anda membangun solusi dari keadaan yang sudah rusak.
if violates(cur):
returnPemangkasan Berdasarkan Batas
Lacak jawaban terbaik yang telah ditemukan. Jika hasil terbaik yang mungkin dicapai sebuah cabang lebih buruk, potong cabang tersebut. Inilah batas pada cabang tersebut.
Pangkas dalam Kode
Di sini, sebuah batas menghentikan cabang saat perkiraan optimistis sekalipun tidak dapat mengungguli hasil terbaik saat ini.
if cur_cost + best_possible <= best:
returnUrutkan Pilihan dengan Cerdas
Mencoba pilihan yang paling menjanjikan terlebih dahulu akan menemukan jawaban yang baik lebih cepat. Hal ini menaikkan batas dan memangkas lebih banyak cabang berikutnya.
Propagasi Batasan
Setelah membuat pilihan, persempit tindakan yang dapat dilakukan pada langkah-langkah berikutnya. Menghapus pilihan yang mustahil sejak awal disebut propagasi batasan dan dapat memperkecil pohon.
Pemecahan Simetri
Jika dua cabang merupakan bayangan cermin satu sama lain, jelajahi hanya salah satunya. Pemecahan simetri dapat mengurangi pekerjaan hingga setengahnya atau lebih tanpa kehilangan jawaban.
Memoisasi Keadaan yang Tumpang Tindih
Jika keadaan parsial yang sama muncul kembali, simpan hasilnya. Memoisasi mengubah subpohon yang berulang menjadi satu pencarian cepat.
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
...Pangkas Sejak Awal, Bukan Terlambat
Periksa kondisi pemangkasan sebelum melakukan rekursi, bukan sesudahnya. Pemangkasan awal menghindari pekerjaan sia-sia untuk memperluas cabang yang sudah pasti gagal.
Perkirakan Sebelum Menjalankan
Selalu periksa kewajaran jumlah cabang pada kasus terburuk terhadap batasan yang ada. Jika terlalu besar, Anda memerlukan pemangkasan yang lebih kuat atau pendekatan baru.
Pemeriksaan Singkat
Apa tujuan pemangkasan dalam runut balik?
Rangkuman: Pangkas Cabang yang Buntu
Anda telah mempelajari cara memangkas menggunakan pemeriksaan kelayakan dan batas, pengurutan yang cerdas, pemecahan simetri, serta memoisasi agar dapat memenuhi batas waktu. 🎯
Belajar Python dengan tutor AI — gratis
Tulis dan jalankan kode asli di browser kamu, dapatkan bantuan instan dari tutor AI 24/7, dan lanjutkan di mana kamu tinggalkan di web atau aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Memangkas untuk Bertahan dari Batas Waktu” gratis?
Ya — teks lengkap “Memangkas untuk Bertahan dari Batas Waktu” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Memangkas untuk Bertahan dari Batas Waktu”?
Memotong cabang yang tidak dapat menghasilkan perbaikan Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.
Berapa lama pelajaran “Memangkas untuk Bertahan dari Batas Waktu” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Berpikir Rekursif: Basis & Rekursi
- Menghasilkan Semua Subset
- Permutasi dan Gagasan N-Queens
- Memangkas untuk Bertahan dari Batas Waktu