Beskär sökningen för att klara tidsgränsen
Ta bort grenar som inte kan förbättra resultatet
Beskär sökningen för att klara tidsgränsen är en gratis lektion i Competitive Programming Academy på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Competitive Programming Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Varför beskärning är viktigt
Rå backtracking kan utforska alldeles för många grenar och överskrida tidsgränsen. Beskärning tar bort hopplösa grenar tidigt så att du håller dig snabb. ✂️
Vad beskärning egentligen innebär
Beskärning innebär att stoppa en gren så snart du kan bevisa att den inte kan nå ett giltigt eller bättre svar. Då slipper du utforska den helt.
Beskärning med genomförbarhetskontroll
Om det aktuella delvalet redan bryter mot en regel ska du returnera direkt. Den här genomförbarhetskontrollen hindrar dig från att bygga vidare på ett ogiltigt tillstånd.
if violates(cur):
returnBeskärning med gränser
Håll reda på det bästa svaret hittills. Om det bästa en gren över huvud taget kan nå är sämre än det bästa svaret hittills, beskär den. Detta är en gräns för grenen.
Beskärning i kod
Här stoppar en gräns grenen när inte ens den optimistiska uppskattningen kan slå det aktuella bästa resultatet.
if cur_cost + best_possible <= best:
returnVälj ordning på valen strategiskt
Om du provar det mest lovande alternativet först hittar du ett bra svar tidigare, vilket höjer gränsen och beskär fler senare grenar.
Propagera villkor
Efter ett val begränsar du vad senare steg kan göra. Att ta bort omöjliga alternativ i förväg kallas villkorspropagering och gör trädet mindre.
Symmetribrytning
Om två grenar är spegelbilder utforskar du bara en. Symmetribrytning kan halvera eller mer än halvera arbetet utan att några svar går förlorade.
Memoisera överlappande tillstånd
Om samma delvisa tillstånd återkommer sparar du resultatet i en cache. Memoisering förvandlar upprepade delträd till en enda snabb uppslagning.
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(state):
...Beskär tidigt, inte sent
Kontrollera beskärningsvillkoret före det rekursiva anropet, inte efteråt. Tidig beskärning undviker det bortkastade arbetet med att bygga ut en dömd gren.
Uppskatta innan du kör
Gör alltid en rimlighetskontroll av värsta tänkbara antal grenar mot begränsningarna. Om det är för stort behöver du starkare beskärning eller ett nytt angreppssätt.
Snabb kontroll
Vad är målet med beskärning i backtracking?
Repetition: beskär de döda grenarna
Du har lärt dig att beskära med genomförbarhets- och gränskontroller, smart ordning, symmetribrytning och memoisering för att klara tidsgränsen. 🎯
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Beskär sökningen för att klara tidsgränsen” gratis?
Ja – hela texten till ”Beskär sökningen för att klara tidsgränsen” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Competitive Programming Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Beskär sökningen för att klara tidsgränsen”?
Ta bort grenar som inte kan förbättra resultatet Ni övar på Competitive Programming Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Competitive Programming Academy?
Du behöver inga förkunskaper. Utbildningen i Competitive Programming Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Beskär sökningen för att klara tidsgränsen”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Competitive Programming Academy-lektionen?
Ja. Varje Competitive Programming Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Tänk rekursivt: basfall och rekursion
- Generera alla delmängder
- Permutationer och idén bakom N-damer
- Beskär sökningen för att klara tidsgränsen