Beskær for at overholde tidsgrænsen
Fjern grene, der ikke kan forbedre resultatet
Beskær for at overholde tidsgrænsen er en gratis Competitive Programming Academy-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Competitive Programming Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvorfor beskæring er vigtig
Ren tilbageløbssøgning kan undersøge alt for mange grene og overskride tidsgrænsen. Beskæring fjerner håbløse grene tidligt, så du arbejder hurtigt. ✂️
Hvad beskæring egentlig er
Beskæring betyder, at du stopper en gren, så snart du kan bevise, at den ikke kan nå et gyldigt eller bedre svar. Du springer helt over at undersøge den.
Beskæring efter gennemførlighed
Hvis det aktuelle delvise valg allerede bryder en regel, skal du returnere med det samme. Dette gennemførlighedstjek forhindrer, at du bygger videre på en ugyldig tilstand.
if violates(cur):
returnBeskæring efter grænse
Hold styr på det bedste svar, du har fundet indtil videre. Hvis det bedst mulige resultat fra en gren stadig er dårligere, skal du fjerne den. Det er en grænse for grenen.
Beskæring i kode
Her stopper en grænse grenen, når selv det optimistiske estimat ikke kan slå det aktuelle bedste resultat.
if cur_cost + best_possible <= best:
returnOrdn valgene intelligent
Hvis du prøver den mest lovende mulighed først, finder du hurtigere et godt svar. Det hæver grænsen og fjerner flere senere grene.
Udbredelse af begrænsninger
Efter et valg skal du indsnævre, hvad de senere trin kan gøre. At fjerne umulige muligheder på forhånd er udbredelse af begrænsninger og gør træet mindre.
Bryde symmetri
Hvis to grene er spejlbilleder, skal du kun undersøge den ene. Symmetribrud kan halvere arbejdet eller reducere det endnu mere uden at miste svar.
Memoisér overlappende tilstande
Hvis den samme delvise tilstand opstår igen, skal du gemme dens resultat i en cache. Memoisering gør gentagne undertræer til ét hurtigt opslag.
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
...Beskær tidligt, ikke sent
Tjek din afskæringsbetingelse før rekursionen, ikke efter. Tidlig beskæring undgår det spildte arbejde med at udvide en dømt gren.
Estimér, før du kører
Lav altid et rimelighedstjek af det værst tænkelige antal grene i forhold til begrænsningerne. Hvis det er for stort, har du brug for stærkere beskæring eller en ny tilgang.
Hurtigt tjek
Hvad er målet med beskæring i tilbageløbssøgning?
Opsummering: Fjern de døde grene
Du har lært at beskære med gennemførligheds- og grænsetjek, intelligent rækkefølge, symmetribrud og memoisering, så du kan holde dig under tidsgrænsen. 🎯
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Beskær for at overholde tidsgrænsen” gratis?
Ja — hele teksten til “Beskær for at overholde tidsgrænsen” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Competitive Programming Academy-kurset, skal du opgradere til CoddyKit PRO. Competitive Programming Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Beskær for at overholde tidsgrænsen”?
Fjern grene, der ikke kan forbedre resultatet Du øver dig i Competitive Programming Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Competitive Programming Academy?
Der kræves ingen tidligere erfaring. Competitive Programming Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Beskær for at overholde tidsgrænsen”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Competitive Programming Academy-lektion?
Ja. Alle Competitive Programming Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Tænk rekursivt: base og rekursion
- Generér alle delmængder
- Permutationer og N-Queens-idéen
- Beskær for at overholde tidsgrænsen