logo

TechCodeview

Backtracking-algoritm

Backtracking-algoritmer är som problemlösningsstrategier som hjälper till att utforska olika alternativ för att hitta den bästa lösningen. De fungerar genom att prova olika vägar och om en inte fungerar, backar de och försöker en annan tills de hittar rätt. Det är som att lösa ett pussel genom att testa olika bitar tills de passar ihop perfekt.

Backtracking

java huvudmetod

Innehållsförteckning



Vad är Backtracking Algorithm?

Backtracking är en problemlösningsalgoritmisk teknik som går ut på att hitta en lösning stegvis genom att försöka olika alternativ och fördärv dem om de leder till en återvändsgränd .

Det används ofta i situationer där du behöver utforska flera möjligheter för att lösa ett problem, som att söka efter en väg i en labyrint eller lösa pussel som Sudoku . När en återvändsgränd nås, backar algoritmen till den tidigare beslutspunkten och utforskar en annan väg tills en lösning hittas eller alla möjligheter har uttömts.

Hur fungerar en bakåtspårningsalgoritm?

A bakåtspårningsalgoritm fungerar genom att rekursivt utforska alla möjliga lösningar på ett problem. Den börjar med att välja en initial lösning, och sedan utforskar den alla möjliga förlängningar av den lösningen. Om en förlängning leder till en lösning, returnerar algoritmen den lösningen. Om en förlängning inte leder till en lösning, går algoritmen tillbaka till den tidigare lösningen och försöker med en annan förlängning.

Följande är en allmän översikt över hur en backtracking-algoritm fungerar:

biträdande poliskommissarie
  1. Välj en första lösning.
  2. Utforska alla möjliga tillägg av den nuvarande lösningen.
  3. Om en förlängning leder till en lösning, returnera den lösningen.
  4. Om en förlängning inte leder till en lösning, gå tillbaka till den tidigare lösningen och prova en annan förlängning.
  5. Upprepa steg 2-4 tills alla möjliga lösningar har utforskats.

Exempel på bakåtspårningsalgoritm

Exempel: Att hitta den kortaste vägen genom en labyrint

Inmatning: En labyrint representerad som en 2D-array, där 0 representerar ett öppet utrymme och 1 representerar en vägg.

Algoritm:

  1. Börja vid startpunkten.
  2. För var och en av de fyra möjliga riktningarna (upp, ner, vänster, höger), försök att röra dig i den riktningen.
  3. Om rörelse i den riktningen leder till slutpunkten, återvänd den väg du tagit.
  4. Om rörelse i den riktningen inte leder till slutpunkten, gå tillbaka till föregående position och prova en annan riktning.
  5. Upprepa steg 2-4 tills slutpunkten nås eller alla möjliga vägar har utforskats.

När ska man använda en bakåtspårningsalgoritm?

Backtracking-algoritmer används bäst för att lösa problem som har följande egenskaper:

  • Det finns flera möjliga lösningar på problemet.
  • Problemet kan delas upp i mindre delproblem.
  • Delproblemen kan lösas självständigt.

Tillämpningar av Backtracking Algorithm

Backtracking-algoritmer används i en mängd olika applikationer, inklusive:

  • Lösa pussel (t.ex. Sudoku, korsord)
  • Att hitta den kortaste vägen genom en labyrint
  • Schemaläggningsproblem
  • Resursfördelningsproblem
  • Nätverksoptimeringsproblem

Grundläggande om bakåtspårningsalgoritm:

  • Skillnaden mellan Backtracking och Branch-N-Bound teknik
  • Vad är skillnaden mellan Backtracking och Rekursion?

Standardproblem på backtracking-algoritmen:

  • Riddarens turnéproblem
  • Råtta i en labyrint
  • N Queen Problem | Backtracking-3
  • Delmängd Summa problem
  • m Färgproblem
  • Hamiltons cykel
  • Sudoku | Backtracking-7
  • Magnet pussel
  • Ta bort ogiltiga parenteser
  • En bakåtspårningsmetod för att generera n-bitars gråkoder
  • Skriv ett program för att skriva ut alla permutationer av en given sträng

Enkla problem med backtracking-algoritmen:

  • Backtracking för att hitta alla delmängder
  • Kontrollera om en given sträng är summasträng
  • Räkna alla möjliga vägar mellan två hörn
  • Hitta alla distinkta delmängder av en given uppsättning
  • Ta reda på om det finns en väg med mer än k längd från en källa
  • Skriv ut alla sökvägar från en given källa till en destination
  • Skriv ut alla möjliga strängar som kan göras genom att placera mellanslag

Medelstora problem med backtracking-algoritmen:

  • Dragkamp
  • 8 drottning problem
  • Kombinationssumma
  • Warnsdorffs algoritm för Knights turnéproblem
  • Hitta vägar från hörncell till mellancell i labyrint
  • Hitta högsta möjliga antal genom att göra högst K byten
  • Råtta i en labyrint med flera steg eller hopp tillåtet
  • N Queen i O(n) utrymme

Svåra problem med backtracking-algoritmen:

  • Power Set i lexikografisk ordning
  • Word Break Problem med Backtracking
  • Fördelning av en mängd i K delmängder med lika summa
  • Längsta möjliga rutt i en matris med hinder
  • Hitta den kortaste säkra vägen i en stig med landminor
  • Skriv ut alla palindromiska partitioner av en sträng
  • Skriver ut alla lösningar i N-Queen Problem
  • Skriv ut alla längsta vanliga delsekvenser i lexikografisk ordning

Snabblänkar :

  • Lär dig datastruktur och algoritmer | Handledning för DSA
  • Topp 20 intervjufrågor för bakåtspårningsalgoritm
  • 'Videos' på Backtracking