logo

TechCodeview

Tilbagesporingsalgoritme

Backtracking algoritmer er som problemløsningsstrategier, der hjælper med at udforske forskellige muligheder for at finde den bedste løsning. De arbejder ved at prøve forskellige veje, og hvis den ene ikke virker, går de tilbage og prøver en anden, indtil de finder den rigtige. Det er som at løse et puslespil ved at teste forskellige brikker, indtil de passer perfekt sammen.

Backtracking

Indholdsfortegnelse



Hvad er Backtracking Algorithm?

Backtracking er en problemløsende algoritmisk teknik, der involverer at finde en løsning trinvist ved at prøve forskellige muligheder og fortryder dem, hvis de fører til en blindgyde .

Det bruges ofte i situationer, hvor du har brug for at udforske flere muligheder for at løse et problem, som at søge efter en sti i en labyrint eller løse gåder som f.eks. Sudoku . Når en blindgyde er nået, går algoritmen tilbage til det tidligere beslutningspunkt og udforsker en anden vej, indtil en løsning er fundet, eller alle muligheder er udtømt.

Hvordan virker en backtracking-algoritme?

EN backtracking algoritme fungerer ved rekursivt at udforske alle mulige løsninger på et problem. Den starter med at vælge en indledende løsning, og derefter undersøger den alle mulige udvidelser af den løsning. Hvis en udvidelse fører til en løsning, returnerer algoritmen denne løsning. Hvis en udvidelse ikke fører til en løsning, går algoritmen tilbage til den tidligere løsning og prøver en anden udvidelse.

Følgende er en generel oversigt over, hvordan en backtracking-algoritme fungerer:

  1. Vælg en indledende løsning.
  2. Udforsk alle mulige udvidelser af den nuværende løsning.
  3. Hvis en udvidelse fører til en løsning, returner den løsning.
  4. Hvis en udvidelse ikke fører til en løsning, skal du gå tilbage til den tidligere løsning og prøve en anden udvidelse.
  5. Gentag trin 2-4, indtil alle mulige løsninger er blevet undersøgt.

Eksempel på backtracking-algoritme

Eksempel: At finde den korteste vej gennem en labyrint

Input: En labyrint repræsenteret som et 2D-array, hvor 0 repræsenterer et åbent rum og 1 repræsenterer en mur.

Algoritme:

  1. Start ved udgangspunktet.
  2. For hver af de fire mulige retninger (op, ned, venstre, højre), prøv at bevæge dig i den retning.
  3. Hvis bevægelse i den retning fører til slutpunktet, skal du returnere den valgte sti.
  4. Hvis bevægelse i den retning ikke fører til slutpunktet, skal du gå tilbage til den forrige position og prøve en anden retning.
  5. Gentag trin 2-4, indtil slutpunktet er nået, eller alle mulige stier er blevet udforsket.

Hvornår skal man bruge en backtracking-algoritme?

Backtracking-algoritmer bruges bedst til at løse problemer, der har følgende egenskaber:

  • Der er flere mulige løsninger på problemet.
  • Problemet kan opdeles i mindre delproblemer.
  • Delproblemerne kan løses selvstændigt.

Anvendelser af Backtracking Algorithm

Backtracking-algoritmer bruges i en lang række applikationer, herunder:

  • Løsning af gåder (f.eks. Sudoku, krydsord)
  • At finde den korteste vej gennem en labyrint
  • Planlægningsproblemer
  • Problemer med ressourceallokering
  • Netværksoptimeringsproblemer

Grundlæggende om backtracking-algoritme:

  • Forskellen mellem Backtracking og Branch-N-Bound teknik
  • Hvad er forskellen mellem Backtracking og Recursion?

Standardproblemer på tilbagesporingsalgoritme:

  • Ridderens turproblem
  • Rotte i en labyrint
  • N Queen Problem | Backtracking-3
  • Subset Sum problem
  • m Farveproblem
  • Hamiltonsk cyklus
  • Sudoku | Backtracking-7
  • Magnet puslespil
  • Fjern ugyldige parenteser
  • En backtracking tilgang til at generere n bit grå koder
  • Skriv et program til at udskrive alle permutationer af en given streng

Nemme problemer med tilbagesporingsalgoritme:

  • Backtracking for at finde alle undergrupper
  • Tjek om en given streng er sum-streng
  • Tæl alle mulige veje mellem to hjørner
  • Find alle distinkte delmængder af et givet sæt
  • Find om der er en sti på mere end k længde fra en kilde
  • Udskriv alle stier fra en given kilde til en destination
  • Print alle mulige strenge, der kan laves ved at placere mellemrum

Mellemstore problemer med tilbagesporingsalgoritme:

  • Tovtrækning
  • 8 dronning problem
  • Kombinationssum
  • Warnsdorffs algoritme til Knights turproblem
  • Find stier fra hjørnecelle til midtercelle i labyrint
  • Find det maksimale antal muligt ved at lave højst K bytte
  • Rotte i en labyrint med flere trin eller hoppe tilladt
  • N Dronning i O(n) rum

Svære problemer med tilbagesporingsalgoritme:

  • Power Set i leksikografisk rækkefølge
  • Word Break Problem ved hjælp af Backtracking
  • Opdeling af en mængde i K delmængder med samme sum
  • Længst mulige rute i en matrix med forhindringer
  • Find den korteste sikre rute på en sti med landminer
  • Udskriv alle palindromiske partitioner af en streng
  • Udskrivning af alle løsninger i N-Queen Problem
  • Udskriv alle længste almindelige undersekvenser i leksikografisk rækkefølge

Hurtige links :

  • Lær datastruktur og algoritmer | DSA Tutorial
  • Top 20 interviewspørgsmål til backtracking-algoritme
  • 'Videoer' på Backtracking