Backtracking:En systematisk problemlösningsteknik
Backtracking är en kraftfull algoritmisk teknik som används för att lösa problem som innebär att söka efter en lösning bland ett stort antal möjligheter. Det fungerar genom att stegvis bygga kandidatlösningar och överge ("backtracking") en kandidat så snart den fastställer att kandidaten omöjligt kan leda till en giltig lösning. Tänk på det som ett smart, strukturerat sätt att utföra en djupgående sökning genom ett beslutsträd.
Nyckelidéer:
* Inkrementell byggnad: Backtracking Construct Solutions steg för steg och lägger till en bit åt gången.
* beskärning (begränsning tillfredsställelse): Vid varje steg kontrollerar den om den nuvarande partiella lösningen uppfyller problemets begränsningar. Om det inte gör det, överger det omedelbart den vägen och går tillbaka till den tidigare beslutspunkten. Detta beskärningssteg minskar dramatiskt sökutrymmet.
* rekursion (ofta): Backtracking implementeras ofta med hjälp av rekursiva funktioner, där varje rekursivt samtal representerar ett val eller steg i lösningsprocessen.
* Beslutsträd: Du kan visualisera sökprocessen som ett beslutsträd, där varje nod representerar ett tillstånd (partiell lösning) och kanterna representerar val eller åtgärder. Backtracking utforskar detta träd på ett djupgående sätt.
Hur det fungerar (allmän algoritm):
1. Börja med en tom (eller delvis initialiserad) lösning.
2. gör ett val (utforska en gren): Välj ett möjligt värde eller åtgärd för att utöka den aktuella lösningen.
3. Kontrollera för giltighet:
* Om lösningen är giltig (uppfyller begränsningar):
* Är lösningen klar?
* Ja: Returnera lösningen.
* no: Rekursivt ring backtracking -funktionen för att göra ett annat val och fortsätta bygga lösningen.
* Om lösningen är ogiltig (bryter mot begränsningar):
* Backtrack: Lossa det sista valet och prova ett annat. Om alla val har testats på denna nivå, backtrack till föregående nivå.
4. ingen lösning: Om alla möjliga val har uttömts utan att hitta en giltig lösning, indikerar att det inte finns någon lösning.
Analogi:Lösa en labyrint
Föreställ dig att du löser en labyrint. Du börjar vid ingången och försöker olika vägar.
* Gå framåt: Du gör ett "val" genom att flytta ner en väg.
* bra väg (giltig): Om vägen verkar leda mot utgången fortsätter du.
* återvändsgränd (ogiltig): Om du når en återvändsgränd, "backtrack" genom att återgå till dina steg till den sista korsningen (beslutspunkt) och prova en annan väg.
* löst: Om du når utgången har du hittat en lösning.
Vanliga användningsfall vid programmering:
* Begränsningsproblem (CSP): Problem där målet är att hitta en uppsättning värden för variabler som uppfyller en uppsättning begränsningar.
* n-Queens Problem: Placera N Chess Queens på ett NXN -schackbräde så att inga två drottningar hotar varandra.
* Sudoku Solver: Fyllning av ett 9x9 rutnät med siffror så att varje rad, kolumn och 3x3 subgrid innehåller alla siffror från 1 till 9.
* Map Coloring: Tilldela färger till regioner på en karta så att inga två angränsande regioner har samma färg.
* kombinatoriska optimeringsproblem: Hitta den bästa lösningen från en stor uppsättning möjliga kombinationer.
* Travel Salesperson Problem (TSP): Att hitta den kortaste möjliga rutten som besöker varje stad i en lista och återvänder till startstaden (backtracking kan användas för små instanser, men andra algoritmer är mer effektiva för större fall).
* ryggsäcksproblem: Bestämma den mest värdefulla delmängden av objekt som kan passa in i en ryggsäck med en begränsad viktkapacitet.
* SUMSUM SUM -problem: Hitta en delmängd av en uppsättning siffror som sammanfattar ett givet målvärde.
* parsing och syntaxanalys:
* Kontextfria grammatik: Backtracking kan användas i parsers för att prova olika härledningar av en mening tills ett giltigt parse -träd hittas.
Exempel:N-Queens problem (förenklad)
Låt oss illustrera N-Queens-problemet med n =4 (ett 4x4-kort).
`` `python
def is_safe (styrelse, rad, col):
"" "Kontroller om att placera en drottning vid styrelsen [rad] [col] är säker." "" "
# Kontrollera samma kolumn
för jag inom räckvidd (rad):
Om styrelsen [i] [col] ==1:
returnera falskt
# Kontrollera den övre vänstra diagonalen
för i, j i zip (intervall (rad -1, -1, -1), intervall (col -1, -1, -1)):
Om styrelsen [i] [j] ==1:
returnera falskt
# Kontrollera övre högra diagonalen
för i, j i zip (intervall (rad -1, -1, -1), intervall (col + 1, 4)):
Om styrelsen [i] [j] ==1:
returnera falskt
returnera
DEF SOLVE_N_QUEENS_UTIL (styrelse, rad):
"" "Rekursiv hjälpfunktion för att lösa N-Queens-problemet." "" "
Om rad ==4:# Alla drottningar placeras framgångsrikt
returnera
För kol inom intervallet (4):
if is_safe (bräde, rad, col):
styrelse [rad] [col] =1 # Placera drottningen
Om Solve_N_Queens_util (bräde, rad + 1):# Placera nästa drottning nästa drottning
returnera
brädet [rad] [col] =0 # backtrack:ta bort drottningen om det inte leder till en lösning
returnera falsk # ingen lösning hittades för den här raden
DEF SOLVE_N_QUEENS ():
"" "Löser N-Queens-problemet för n =4." "" "
styrelse =[[0 för _ inom intervallet (4)] för _ inom intervallet (4)] # Initiera ett tomt kort
om inte lösning_n_queens_util (styrelse, 0):
tryck ("Lösning finns inte")
återvända
# Skriv ut lösningen
för rad i styrelsen:
tryck (rad)
Solve_n_queens ()
`` `
Förklaring av koden:
1. `is_safe (styrelse, rad, col)`: Kontroller om det är säkert att placera en drottning på `brädet [rad] [col]`. Den kontrollerar konflikter i samma kolumn och diagonaler.
2. `SOLVE_N_QUEENS_UTIL (bräd, rad)`:
* Basfall: `Om rad ==4:` Om vi har nått den sista raden (alla drottningar placerade), har vi en lösning, så returnera 'true'.
* iteration: Slinga genom varje kolumn i den aktuella raden (`för Col inom intervallet (4)`).
* Kontrollera säkerhet: `If Is_Safe (styrelse, rad, col):` Om det är säkert att placera en drottning i den här kolumnen:
* Placera drottningen: `Board [rad] [col] =1`
* Rekursivt samtal: `Om SOLVE_N_QUEENS_UTIL (BOARD, ROW + 1):` Rekursivt försök att placera nästa drottning i nästa rad. Om detta rekursiva samtal returnerar "sant" betyder det att en lösning hittades från denna punkt, så vi returnerar "sant" också.
* Backtrack: `Board [rad] [col] =0` Om det rekursiva samtalet returnerar` falskt '(ingen lösning hittades), ångrar vi * drottningens placering (backtrack) och prova nästa kolumn i den aktuella raden.
* ingen lösning i den här raden: "Return False" om vi har provat alla kolumner i den aktuella raden utan att hitta en lösning, betyder det att det inte finns någon giltig placering av drottningar, så vi returnerar "falsk".
3. `SOLVE_N_QUEENS ()`:
* Initialiserar styrelsen.
* Ringer `SOLVE_N_QUEENS_UTIL` för att starta backtracking -processen.
* Skriver ut lösningen om man hittas.
Fördelar med backtracking:
* Systematisk sökning: Garantier att hitta en lösning om man finns (uttömmande sökning).
* beskärning: Undviker att utforska onödiga grenar av sökutrymmet, vilket gör det mer effektivt än en brute-force-strategi.
* Konceptuell enkelhet: Kärnidén är relativt lätt att förstå.
Nackdelar med backtracking:
* Tidskomplexitet: Kan fortfarande ha hög tid komplexitet (exponentiell i värsta fall) för stora problem, eftersom det kan utforska många återvändsgränd.
* Rymdkomplexitet: Kan kräva betydande minne, särskilt för djup rekursion.
Nyckelöverväganden för att tillämpa backtracking:
* Begränsningar: Definiera tydligt begränsningarna för problemet.
* Val av handling: Överväg noggrant hur du gör val vid varje steg.
* beskärningsstrategi: Utveckla en effektiv beskärningsstrategi för att eliminera ogiltiga kandidater så tidigt som möjligt. Detta är avgörande för prestanda.
* Problemstruktur: Backtracking fungerar bäst för problem där partiella lösningar enkelt kan utvärderas med avseende på giltighet.
Sammanfattningsvis är backtracking en mångsidig problemlösningsteknik som kan tillämpas på ett brett spektrum av problem. Genom att systematiskt utforska möjliga lösningar och beskära sökutrymmet erbjuder det ett kraftfullt tillvägagångssätt för att hitta lösningar som uppfyller specifika begränsningar. Även om det kan ha hög tid komplexitet i värsta fall, kan noggrann begränsning och effektiv beskärning förbättra dess prestanda avsevärt.
