Tilbagesporingsalgoritme

Hvad er Backtracking Algorithm?

Backtracking er en algoritme, der søger efter mulige kombinationer at løse beregningsmæssige problemer. Det opbygger gradvist kandidater og fjerner dem, der ikke opfylder givne begrænsninger. Denne teknik er meget nyttig i situationer, hvor du skal vælge en gennemførlig løsning blandt flere mulige resultater.

Denne algoritme anses for at være bedre og mere effektiv end Brute Force-tilgangen. I modsætning til Bruteforce, der forsøger alle mulige løsninger, fokuserer Backtracking på kun at finde én endelig løsning i henhold til given begrænsninger. Det sparer også tid og hukommelse ved at fortryde det sidste trin (backtrack) og prøve en anden mulighed efter at have nået en blindgyde. Derudover stopper den, så snart en gyldig løsning er fundet.

Backtracking er en meget brugt teknik, fordi den kan løse komplekse problemer uden udtømmende ressourceforbrug. Det er især nyttigt til problemer, hvor adskillige begrænsninger skal være opfyldt, såsom Sudoku, n queen problem og planlægning. Ved intelligent at navigere gennem potentielle løsninger kan backtracking finde et svar, der opfylder alle betingelser. Dette gør den uvurderlig til opgaver, der kræver både præcision og effektivitet.

Hvordan fungerer tilbagesporingsalgoritme?

Backtracking-algoritmer er en problemløsningsteknik, der involverer at finde valide løsninger trin for trin. Hvis begrænsningerne for et trin ikke opfylder visse betingelser, vender algoritmen tilbage til det forrige trin.

Det fortsætter derefter med andre mulige kombinationer, der opfylder de givne begrænsninger. Da der findes mange mulige kombinationer, vælger den en af ​​de mest tilfredsstillende muligheder og løser problemet sekventielt. Denne algoritmiske teknik er nyttig, når du skal løse en eller flere mulige muligheder. Tilbagetrækning betyder, at du annullerer dit valg, når der opstår en situation, som ikke giver en gyldig løsning.

Tilbagesporingsalgoritmen har følgende trin generelt for at løse et problem:

Trin 1) Initialisering: Start med en indledende tom/delvis opløsning.

Trin 2) Udvælgelse: Baseret på specifikke kriterier og begrænsninger, vælg én mulighed for at udvide den nuværende løsning.

Trin 3) Udforskning: Løs rekursivt ved at overveje den valgte kandidat og komme videre i problemløsningsprocessen.

Trin 4) Kontrol af begrænsninger: Tjek, om den aktuelle delvise løsning overtræder nogen begrænsninger ved hvert trin. Hvis det gør det, skal du gå tilbage til det forrige trin og prøve en anden kandidat.

Trin 5) Opsigelse: Tilbagesporingsprocessen stopper, når enten en gyldig løsning er fundet, eller alle kombinationer er opbrugt.

Trin 6) Backtracking: Hvis den aktuelle indstilling ikke løser det givne problem, vender den tilbage til den tidligere tilstand. Den overvejer derefter den nye mulighed for at løse det givne problem.

Trin 7) Gentag: Fortsæt med disse trin, indtil problemet er løst, eller alle muligheder er undersøgt.

Rekursiv karakter af tilbagesporingsalgoritme

Tilbagesporingsalgoritmer er af rekursive natur. Det betyder, at algoritmen kalder sig selv med forskellige parametre, indtil den finder en løsning eller har testet alle muligheder:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Almindelige vilkår relateret til problemer med tilbagesporing

Disse er nogle grundlæggende udtryk relateret til Backtracking-teknikken:

• Løsningsvektor: Repræsenterer løsninger som n-tupler, som (X1, X2, …, Xn).
• Begrænsninger: Regler, der begrænser X-værdier, implicit og eksplicit.
• Løsningsplads: Alle gyldige X-værdier, der opfylder eksplicitte begrænsninger.
• Statens rumtræ: Repræsenterer løsningsrummet som et træ.
• Statens Rum: Beskriver stier i et tilstandsrumtræ.
• Problemtilstand: Noder i søgetræet, der repræsenterer delløsninger.
• Løsningsstater: Stater, der danner gyldige løsningstupler i S.
• Svar stater: Opfyld implicitte begrænsninger og giv ønskede løsninger.
• Lovende knude: Fører til ønskede løsninger og forbliver gennemførlige.
• Ikke-lovende node: Fører til uigennemførlige tilstande, ikke udforsket yderligere.
• Live Node: Genereret med uudforskede børn.
• E-knude: Live node med igangværende børnegenerering.
• Død knude: Ingen yderligere udvidelse af alle børn genereret.
• Dybde-første knudegenerering: Bruger den seneste live node som den næste E-node.
• Afgrænsningsfunktion: Maksimerer eller minimerer B(x1, x2, …, Xa) for optimering.
• Statiske træer: Træformulering uafhængig af probleminstansen.
• Dynamiske træer: Træets formulering varierer med problemforekomsten.

Hvornår skal man bruge en backtracking-algoritme?

Vi kan vælge Backtracking-teknikken til at løse et komplekst problem, når:

• Der er mange valgmuligheder: Backtracking er velegnet, hvis der findes mange muligheder på hvert trin i problemløsningsprocessen. Disse muligheder kan relatere til udvælgelsen af ​​emner og træk.
• Intet klart bedste valg: Når der er utilstrækkelig information til at bestemme det bedste valg blandt tilgængelige muligheder, kan en Backtracking-algoritme bruges.
• Beslutningen fører til flere valg: Du kan vælge backtracking-teknik til at gennemgå valg systematisk.
• Har brug for at udforske alle mulige løsninger: Backtracking udforsker systematisk alle løsningerne ved at træffe en række beslutninger, der bygger på hinanden.

Typer af tilbagesporingsproblemer

Der er tre typer problemer i backtracking-algoritmer: beslutningsproblemer, optimeringsproblemer og optællingsproblemer. Lad os lære om dem nedenfor.

1. Beslutningsproblem: I denne type problemer er målet at afgøre, om der findes en gennemførlig løsning. Vi tjekker "ja" og "nej" svarene. For eksempel n-queens-problemet. Det er et beslutningsproblem, der undersøger sandsynligheden for at placere n dronninger på et n × n skakbræt uden at angribe hinanden.
2. Optimeringsproblem: Ved optimeringsproblemer er målet at finde den bedst mulige løsning blandt mange muligheder. Dette kan involvere at bestemme maksimum- og minimumværdierne for en bestemt funktion eller variabel. Overvej for eksempel rygsækproblemet, hvor målet er at maksimere den samlede værdi af genstandene i tasken, samtidig med at dens vægtgrænse overholdes.
3. Optællingsproblem: Dens formål er at finde alle mulige løsninger på et givet problem. Vi lister alle gyldige muligheder uden nogen udeladelser. Et eksempel ville være at generere alle mulige bogstavkombinationer fra et givet sæt af tegn.

Anvendelser af backtracking & eksempler

Der er forskellige anvendelser af Backtracking. Nogle af dem er forklaret nedenfor med deres pseudokode.

1. Sudoku Solver: Dette problem indeholder et 3×3 undergitter med duplikerede numre. Backtracking-teknikken vil vise, at løsningen returnerer falsk, hvilket indikerer behovet for en anden nummerplacering.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

2. N-Queen problem: Backtracking-tilgangen bestemmer, hvordan dronninger skal præsenteres på et N × N skakbræt, så ingen af ​​dem truer hinanden.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

3. Subset Sum Problem: Det bruges til at finde delmængden af ​​tal fra et givet sæt, der summerer til en bestemt målsum.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

4. Hamiltonsk cyklusproblem: Tilbagesporing kan anvendes til at finde en lukket tur i en graf, der besøger hvert hjørne nøjagtigt én gang.
5. Rotte i labyrint-problem: Backtracking-teknikken bruges til at finde en rottes vej fra labyrintens startpunkt til udgangen.

Fordele og ulemper ved Backtracking Algorithm

Fordele ved Backtracking Algorithm

Backtracking-teknikker bruges til at løse komplekse problemer. Det har mange fordele som:

• Backtracking-teknikken er effektiv til håndtering af begrænsninger.
• Denne metode er god til at løse optimeringsproblemer.
• Teknikken virker til forskellige typer problemer.
• Denne procedure kan hjælpe med at gennemgå alle mulige løsninger.
• Da det går tilbage, sparer det mere hukommelse end Bruteforce-teknikken.

Ulemper ved Backtracking Algorithm

Backtracking-teknikker har også nogle begrænsninger, såsom tidskompleksitet. Denne teknik har følgende ulemper:

• Der er ingen garanteret løsning.
• Det er langsommere på grund af mange kombinationer.
• Det har høj tidskompleksitet på grund af mange muligheder.
• Det er uegnet til realtidsbegrænsninger, da det kan tage lang tid at finde den bedste løsning.
• Effektiviteten afhænger af problemets kompleksitetsniveau.

Forskellen mellem tilbagesporing og rekursion

rekursion	backtracking
Kalder sig selv indtil basissagen er nået.	Bruger rekursion til at gennemgå alle muligheder, indtil det bedst mulige resultat er fundet.
Bottom up tilgang.	Top down tilgang.
Ingen værdi kasseres.	Ikke-levedygtige løsninger afvises.

Konklusion

Backtracking er en nyttig algoritmisk strategi til at løse komplekse problemer ved systematisk at udforske gennemførlige løsninger og backtracke, når det er nødvendigt. Vi kan forvente, at tilbagesporingsteknikker forbedres med forbedringer i beregningskraft og algoritmisk effektivitet. Disse fremskridt vil give dem mulighed for at tackle større og mere komplekse problemer effektivt.

Derudover kan maskinlæringsmodeller guide tilbageløbende beslutninger baseret på tidligere lærte mønstre.

Alle disse teknologiske innovationer vil revolutionere backtracking-algoritmer, hvilket gør dem til et kraftfuldt og alsidigt værktøj til at løse komplicerede problemer i forskellige domæner.