Backtracking-algoritme

Wat is het backtracking-algoritme?

Backtracking is een algoritme dat zoekt naar mogelijke combinaties om problemen op te lossen rekenkundige problemen. Het bouwt stapsgewijs kandidaten op en verwijdert degenen die niet voldoen aan de gegeven beperkingen. Deze techniek is erg handig in situaties waarin u een haalbare oplossing moet kiezen uit meerdere mogelijke resultaten.

Dit algoritme wordt als beter en efficiënter beschouwd dan de Brute Force-aanpak. In tegenstelling tot Bruteforce, dat alle mogelijke oplossingen probeert, richt Backtracking zich op het vinden van slechts één uiteindelijke oplossing volgens gegeven schaarste. Het bespaart ook tijd en geheugen door de laatste stap (backtrack) ongedaan te maken en een andere optie te proberen nadat u een doodlopende weg hebt bereikt. Bovendien stopt het zodra er een geldige oplossing is gevonden.

Backtracking is een veelgebruikte techniek omdat het complexe problemen kan oplossen zonder uitputtend resourceverbruik. Het is met name handig voor problemen waarbij aan talloze beperkingen moet worden voldaan, zoals Sudoku, n queen-probleem en planning. Door intelligent door mogelijke oplossingen te navigeren, kan backtracking een antwoord vinden dat aan alle voorwaarden voldoet. Dit maakt het van onschatbare waarde voor taken die zowel precisie als efficiëntie vereisen.

Hoe werkt het backtracking-algoritme?

Backtracking-algoritmen zijn een probleemoplossingstechniek die bestaat uit het stap voor stap vinden van geldige oplossingen. Als de beperkingen van een stap niet aan bepaalde voorwaarden voldoen, keert het algoritme terug naar de vorige stap.

Vervolgens gaat het verder met andere mogelijke combinaties die voldoen aan de gegeven beperkingen. Omdat er talloze mogelijke combinaties bestaan, selecteert het een van de meest bevredigende opties en lost het het probleem sequentieel op. Deze algoritmische techniek is handig wanneer u een of meer mogelijke opties moet oplossen. Terugtrekken betekent dat u uw keuze annuleert wanneer er een situatie ontstaat die geen geldige oplossing oplevert.

Het backtracking-algoritme kent over het algemeen de volgende stappen om een probleem op te lossen:

Stap 1) Initialisatie: Begin met een lege/gedeeltelijke oplossing.

Stap 2) Selectie: Selecteer op basis van specifieke criteria en beperkingen een optie om de huidige oplossing uit te breiden.

Stap 3) Verkenning: Los het probleem recursief op door rekening te houden met de gekozen kandidaat en door te gaan met het probleemoplossingsproces.

Stap 4) Beperkingscontrole: Controleer of de huidige gedeeltelijke oplossing bij elke stap beperkingen schendt. Als dat het geval is, ga dan terug naar de vorige stap en probeer een andere kandidaat.

Stap 5) Beëindiging:Het backtrackingproces stopt wanneer er een geldige oplossing is gevonden of wanneer alle combinaties zijn uitgeput.

Stap 6) Teruggaan: Als de huidige optie het gegeven probleem niet oplost, keert het terug naar de vorige staat. Vervolgens overweegt het de nieuwe optie om het gegeven probleem op te lossen.

Stap 7) Herhaal: Ga door met deze stappen totdat het probleem is opgelost of alle opties zijn onderzocht.

Recursieve aard van het backtracking-algoritme

Backtracking-algoritmen zijn recursief van aard. Dit betekent dat het algoritme zichzelf aanroept met verschillende parameters totdat het een oplossing vindt of alle mogelijkheden heeft getest:

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)

Algemene termen gerelateerd aan backtracking-problemen

Dit zijn enkele basisbegrippen die verband houden met de Backtracking-techniek:

Oplossingsvector: Geeft oplossingen weer als n-tupels, zoals (X1, X2, …, Xn).
beperkingen: Regels die X-waarden beperken, impliciet en expliciet.
Oplossingsruimte: Alle geldige X-waarden die voldoen aan expliciete beperkingen.
Staatsruimteboom: Geeft de oplossingsruimte weer als een boom.
Staatsruimte: Beschrijft paden in een toestandsruimteboom.
Probleemstatus: Knooppunten in de zoekboom die gedeeltelijke oplossingen voorstellen.
Oplossingsstaten: Staten die geldige oplossingstupels vormen in S.
Antwoord Staten: Voldoen aan impliciete beperkingen en gewenste oplossingen opleveren.
Veelbelovende Node: Leidt tot gewenste oplossingen en blijft haalbaar.
Niet-belovende knoop: Leidt tot onhaalbare toestanden, die niet verder onderzocht worden.
Levende Knoop: Gemaakt met onontdekte kinderen.
E-knooppunt: Live node met voortdurende onderliggende generatie.
Dode Knoop: Geen verdere uitbreiding van alle gegenereerde kinderen.
Diepte-eerst knooppuntgeneratie: Gebruikt het laatste actieve knooppunt als het volgende E-knooppunt.
Begrenzende functie: Maximaliseert of minimaliseert B(x1, x2, …, Xa) voor optimalisatie.
Statische bomen: Boomformulering onafhankelijk van het probleemexemplaar.
Dynamische Bomen: De formulering van de boom varieert afhankelijk van het probleem.

Wanneer moet je een backtracking-algoritme gebruiken?

We kunnen de Backtracking-techniek gebruiken om een complex probleem op te lossen wanneer:

Er zijn veel keuzes: Backtracking is geschikt als er bij elke stap van het probleemoplossingsproces veel opties bestaan. Deze opties kunnen betrekking hebben op de selectie van items en zetten.
Geen duidelijke beste keuze:Wanneer er onvoldoende informatie is om de beste keuze te maken uit de beschikbare opties, kan een Backtracking-algoritme worden gebruikt.
Het besluit leidt tot meer keuzes: U kunt kiezen voor backtracking-techniek om keuzes systematisch te evalueren.
Het is noodzakelijk om alle mogelijke oplossingen te onderzoeken: Bij backtracking worden alle oplossingen systematisch onderzocht door een reeks beslissingen te nemen die op elkaar zijn gebaseerd.

Soorten backtrackingproblemen

Er zijn drie soorten problemen in backtracking-algoritmen: beslissingsproblemen, optimalisatieproblemen en enumeratieproblemen. Laten we er hieronder meer over leren.

Beslissingsprobleem: Bij dit type probleem is het doel om te bepalen of er een haalbare oplossing bestaat. We controleren 'ja' en 'nee' antwoorden. Bijvoorbeeld, het n-koninginnenprobleem. Het is een beslissingsprobleem dat de waarschijnlijkheid onderzoekt om n koninginnen op een n × n schaakbord te plaatsen zonder elkaar aan te vallen.
Optimalisatieprobleem: Bij optimalisatieproblemen is het doel om de best mogelijke oplossing te vinden uit vele opties. Dit kan het bepalen van de maximum- en minimumwaarden van een bepaalde functie of variabele inhouden. Denk bijvoorbeeld aan het rugzakprobleem, waarbij het doel is om de totale waarde van de items in de tas te maximaliseren terwijl de gewichtslimiet wordt aangehouden.
Opsommingsprobleem: Het doel is om alle mogelijke oplossingen voor een bepaald probleem te vinden. We vermelden elke geldige optie zonder enige weglating. Een voorbeeld zou zijn om alle mogelijke lettercombinaties te genereren uit een gegeven set tekens.

Toepassingen van Backtracking en voorbeelden

Er zijn verschillende toepassingen van Backtracking. Enkele daarvan worden hieronder uitgelegd met hun pseudocode.

Sudoku Solver: Dit probleem bevat een 3×3 subgrid met dubbele getallen. De backtracking-techniek zal laten zien dat de oplossing false retourneert, wat aangeeft dat er een andere nummerplaatsing nodig is.

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

N-Queen-probleem:De backtracking-benadering bepaalt hoe de dames op een N × N schaakbord worden gepresenteerd, zodat geen van hen elkaar bedreigt.

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

Subsetsomprobleem: Wordt gebruikt om de deelverzameling getallen uit een gegeven reeks te vinden die samen een bepaalde doelsom opleveren.

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)

Hamiltoniaanse Cyclus Probleem:Backtracking kan worden toegepast om een gesloten tour in een grafiek te vinden die elk hoekpunt precies één keer bezoekt.
Rat in doolhofprobleem:De backtracking-techniek wordt gebruikt om het pad van een rat te vinden vanaf het beginpunt van het doolhof naar de uitgang.

Voordelen en nadelen van het backtracking-algoritme

Voordelen van het backtracking-algoritme

Backtracking-technieken worden gebruikt om complexe problemen op te lossen. Het heeft veel voordelen, zoals:

De backtrackingtechniek is efficiënt voor het omgaan met beperkingen.
Deze methode is geschikt voor het oplossen van optimalisatieproblemen.
De techniek is toepasbaar bij verschillende soorten problemen.
Met deze procedure kunt u alle mogelijke oplossingen bekijken.
Omdat het terugdraait, bespaart het meer geheugen dan de Bruteforce-techniek.

Nadelen van het backtracking-algoritme

Backtracking-technieken hebben ook enkele beperkingen, zoals tijdcomplexiteit. Deze techniek heeft de volgende nadelen:

Er is geen gegarandeerde oplossing.
Het is langzamer omdat er veel combinaties zijn.
Het heeft een hoge tijdscomplexiteit vanwege de vele mogelijkheden.
Het is niet geschikt voor realtime beperkingen, omdat het vinden van de beste oplossing veel tijd kan kosten.
Efficiëntie hangt af van de mate van complexiteit van het probleem.

Verschil tussen backtracking en recursie

Recursie	Terugkeren
Roept zichzelf aan totdat het basisgeval is bereikt.	Gebruikt recursie om alle mogelijkheden te beoordelen totdat het best haalbare resultaat is gevonden.
Bottom-up-benadering.	Top-downbenadering.
Er wordt geen waarde weggegooid.	Niet-levensvatbare oplossingen worden afgewezen.

Conclusie

Backtracking is een nuttige algoritmische strategie voor het oplossen van complexe problemen door systematisch haalbare oplossingen te verkennen en indien nodig backtracking toe te passen. We kunnen verwachten dat backtrackingtechnieken zullen verbeteren met verbeteringen in rekenkracht en algoritmische efficiëntie. Deze ontwikkelingen zullen hen in staat stellen om grotere en complexere problemen efficiënt aan te pakken.

Bovendien kunnen machine learning-modellen backtracking-beslissingen sturen op basis van eerder geleerde patronen.

Al deze technologische innovaties zullen een revolutie teweegbrengen in backtrackingalgoritmen en ze tot een krachtig en veelzijdig hulpmiddel maken voor het aanpakken van complexe problemen in verschillende domeinen.