Backtracking -algoritmen undersöker effektivt ett sökutrymme genom att systematiskt prova olika kombinationer och överge vägar som garanteras att inte leda till en lösning. Det fungerar med principen om * Djup-första sökning * med ett avgörande tillägg:
beskärning .
Här är en uppdelning av hur det fungerar:
1. State Space Representation: Problemet representeras som ett träd eller graf där varje nod representerar en partiell lösning. Rotnoden representerar det initiala tillståndet och grenar representerar val eller beslut som fattas vid varje steg. Bladen representerar antingen kompletta lösningar eller återvändsgränd.
2. Rekursiv utforskning (Djup-första sökning): Algoritmen börjar vid rotnoden och utforskar en gren åt gången och går så djupt som möjligt (djup först). Detta innebär att det gör en serie val tills den antingen hittar en lösning eller träffar en återvändsgränd.
3. Begränsningskontroll/lovande: Vid varje nod utförs en kontroll för att se om den nuvarande partiella lösningen fortfarande "lovar" - vilket innebär att det är möjligt att utöka den till en komplett lösning. Det är här effektiviteten kommer in. Om den nuvarande partiella lösningen bryter mot begränsningarna för problemet (t.ex. i ett Sudoku -pussel och placerar ett nummer som redan finns i raden, kolumnen eller 3x3 -blocket), vet algoritmen att den inte behöver utforska den grenen vidare. Detta är beskärningen steg.
4. Backtracking: Om en nod anses vara inte lovande, eller om en bladnod representerar ett misslyckat försök att hitta en lösning, algoritmen "backtracks" till föregående nod (dess förälder) och försöker en annan gren (ett annat val). Detta innebär att ångra de val som gjorts längs den grenen och utforska alternativa möjligheter.
5. Lösning hittades: När en bladnod representerar en komplett och giltig lösning har algoritmen hittat en lösning och kan antingen stoppa (om det är tillräckligt att hitta en lösning) eller fortsätta att söka efter andra lösningar genom att backtracka och utforska andra grenar.
Exempel:N-Queens problem
Låt oss överväga att placera N Chess Queens på ett N × N -schackbräde så att inga två drottningar hotar varandra.
* State Space: Varje nod i trädet representerar en partiell placering av drottningar på brädet.
* Val: På varje nivå i trädet görs ett val om var man ska placera nästa drottning i kolumnen.
* Begränsning: Begränsningen är att inga två drottningar kan vara på samma rad, kolumn eller diagonal.
* beskärning: Om placering av en drottning bryter mot begränsningen beskärs den grenen. Algoritmen utforskar inte längre ner den grenen.
* Backtracking: Om en placering leder till en överträdelse tar algoritmens backtracks till föregående kolumn, tar bort drottningen och försöker en annan position i den kolumnen.
Sammanfattningsvis: Backtrackings effektivitet härstammar från dess förmåga att undvika att utforska onödiga delar av sökutrymmet genom intelligent beskära grenar som garanteras att inte leda till en lösning. Detta minskar beräkningstiden avsevärt jämfört med uttömmande sökmetoder som skulle prova varje kombination. Effektiviteten beror på hur väl den "lovande" kontrollen är utformad för att identifiera och eliminera icke-livskraftiga vägar tidigt i sökningen.
