Beskjær søket for å overholde tidsgrensen
Kutt grener som ikke kan gi en bedre løsning
Beskjær søket for å overholde tidsgrensen er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hvorfor beskjæring er viktig
Ubeskåret backtracking kan utforske altfor mange grener og overskride tidsgrensen. Beskjæring kutter håpløse grener tidlig, slik at løsningen holder seg rask. ✂️
Hva beskjæring egentlig er
Beskjæring betyr å stoppe en gren så snart du kan bevise at den ikke kan nå et gyldig eller bedre svar. Da slipper du å utforske den videre.
Beskjæring basert på gjennomførbarhet
Hvis det nåværende delvalget allerede bryter en regel, returnerer du umiddelbart. Denne gjennomførbarhetssjekken hindrer at du bygger videre på en ugyldig tilstand.
if violates(cur):
returnBeskjæring med grenser
Hold oversikt over det beste svaret du har funnet så langt. Hvis det beste en gren kan oppnå, er dårligere, kutter du den. Dette er en grense for grenen.
Beskjæring i kode
Her stopper en grense grenen når selv det optimistiske anslaget ikke kan slå det nåværende beste svaret.
if cur_cost + best_possible <= best:
returnVelg rekkefølgen på valgene med omhu
Hvis du prøver det mest lovende alternativet først, finner du et godt svar tidligere. Det hever grensen og gjør at flere senere grener kan beskjæres.
Propager begrensninger
Etter et valg begrenser du hva senere trinn kan gjøre. Å fjerne umulige alternativer på forhånd er propagering av begrensninger og gjør treet mindre.
Bryt symmetrier
Hvis to grener er speilbilder av hverandre, utforsker du bare én. Symmetribryting kan halvere eller redusere arbeidet enda mer uten at du mister svar.
Memoiser overlappende tilstander
Hvis den samme delvise tilstanden oppstår på nytt, lagrer du resultatet i en hurtigbuffer. Memoisering gjør gjentatte undertrær til ett raskt oppslag.
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
...Beskjær tidlig, ikke sent
Sjekk betingelsen for å kutte før du gjør rekursjon, ikke etterpå. Tidlig beskjæring unngår det bortkastede arbeidet med å utvide en håpløs gren.
Beregn før du kjører
Sjekk alltid worst-case-anslaget for antall grener mot begrensningene. Hvis det er for stort, trenger du sterkere beskjæring eller en ny metode.
Hurtigsjekk
Hva er målet med beskjæring i backtracking?
Oppsummering: Kutt de håpløse grenene
Du har lært å beskjære med gjennomførbarhets- og grensesjekker, smart rekkefølge, symmetribryting og memoising for å holde deg innenfor tidsgrensen. 🎯
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Beskjær søket for å overholde tidsgrensen» gratis?
Ja – hele teksten i «Beskjær søket for å overholde tidsgrensen» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Beskjær søket for å overholde tidsgrensen»?
Kutt grener som ikke kan gi en bedre løsning Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Beskjær søket for å overholde tidsgrensen»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Tenk rekursivt: base og rekursjon
- Generer alle delmengder
- Permutasjoner og ideen bak N-Queens
- Beskjær søket for å overholde tidsgrensen