Backtracking-algoritm

Vad är Backtracking Algorithm?

Backtracking är en algoritm som söker efter möjliga kombinationer att lösa beräkningsproblem. Den bygger stegvis upp kandidater och tar bort de som inte uppfyller givna begränsningar. Denna teknik är mycket användbar i situationer där du måste välja en genomförbar lösning bland flera möjliga resultat.

Denna algoritm anses vara bättre och mer effektiv än Brute Force-metoden. Till skillnad från Bruteforce, som provar alla möjliga lösningar, fokuserar Backtracking på att endast hitta en slutlig lösning enligt given begränsningar. Det sparar också tid och minne genom att ångra det sista steget (backtrack) och prova ett annat alternativ efter att ha nått en återvändsgränd. Dessutom stoppas det så snart en giltig lösning hittas.

Backtracking är en mycket använd teknik eftersom den kan lösa komplexa problem utan uttömmande resursförbrukning. Det är särskilt användbart för problem där många begränsningar måste uppfyllas, såsom Sudoku, n queen-problem och schemaläggning. Genom att intelligent navigera genom potentiella lösningar kan backtracking hitta ett svar som uppfyller alla villkor. Detta gör den ovärderlig för uppgifter som kräver både precision och effektivitet.

Hur fungerar backtracking-algoritmen?

Backtracking-algoritmer är en problemlösningsteknik som går ut på att hitta giltiga lösningar steg för steg. Om begränsningarna för ett steg inte uppfyller vissa villkor, återgår algoritmen till föregående steg.

Den fortsätter sedan med andra möjliga kombinationer som uppfyller de givna begränsningarna. Eftersom det finns många möjliga kombinationer, väljer den ett av de mest tillfredsställande alternativen och löser problemet sekventiellt. Denna algoritmiska teknik är användbar när du behöver lösa ett eller flera möjliga alternativ. Uttag innebär att du avbryter ditt val när en situation uppstår som inte ger en giltig lösning.

Backtracking-algoritmen har följande steg i allmänhet för att lösa ett problem:

Steg 1) Initiering: Börja med en initial tom/dellösning.

Steg 2) Urval: Baserat på specifika kriterier och begränsningar, välj ett alternativ för att utöka den nuvarande lösningen.

Steg 3) Utforskning: Lös rekursivt genom att överväga den valda kandidaten och gå vidare i problemlösningsprocessen.

Steg 4) Kontroll av begränsningar: Kontrollera om den aktuella dellösningen bryter mot några begränsningar vid varje steg. Om den gör det, gå tillbaka till föregående steg och försök med en annan kandidat.

Steg 5) Uppsägning: Backtracking-processen stoppas när antingen en giltig lösning hittas eller alla kombinationer har förbrukats.

Steg 6) Backtracking: Om det aktuella alternativet inte löser det givna problemet, återgår det till det tidigare tillståndet. Den överväger sedan det nya alternativet för att lösa det givna problemet.

Steg 7) Upprepa: Fortsätt med dessa steg tills problemet är löst eller alla alternativ har utforskats.

Rekursiv karaktär av backtracking-algoritm

Backtracking-algoritmer är rekursiva till sin natur. Det betyder att algoritmen anropar sig själv med olika parametrar tills den hittar en lösning eller har testat alla möjligheter:

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)

Vanliga termer relaterade till bakåtspårningsproblem

Det här är några grundläggande termer relaterade till Backtracking-tekniken:

• Lösningsvektor: Representerar lösningar som n-tupler, som (X1, X2, …, Xn).
• begränsningar: Regler som begränsar X-värden, implicita och explicita.
• Lösningsutrymme: Alla giltiga X-värden som uppfyller explicita begränsningar.
• Statens rymdträd: Representerar lösningsutrymmet som ett träd.
• State Space: Beskriver sökvägar i ett tillståndsrymdträd.
• Problemtillstånd: Noder i sökträdet som representerar dellösningar.
• Lösningsstater: Stater som bildar giltiga lösningstupler i S.
• Svar stater: Tillfredsställa implicita begränsningar och ge önskade lösningar.
• Lovande nod: Leder till önskade lösningar och förblir genomförbara.
• Icke-lovande nod: Leder till omöjliga tillstånd, inte undersökt vidare.
• Live Node: Genereras med outforskade barn.
• E-nod: Live nod med pågående barngenerering.
• Död nod: Ingen ytterligare expansion av alla barn genereras.
• Djup-första nodgenerering: Använder den senaste livenoden som nästa E-nod.
• Begränsande funktion: Maximerar eller minimerar B(x1, x2, …, Xa) för optimering.
• Statiska träd: Trädformulering oberoende av probleminstansen.
• Dynamiska träd: Trädets formulering varierar med probleminstansen.

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

Vi kan välja Backtracking-tekniken för att lösa ett komplext problem när:

• Det finns många val: Backtracking är lämpligt om det finns många alternativ vid varje steg i problemlösningsprocessen. Dessa alternativ kan relatera till valet av föremål och drag.
• Inget klart bästa val: När det inte finns tillräcklig information för att bestämma det bästa valet bland tillgängliga alternativ, kan en Backtracking-algoritm användas.
• Beslutet leder till fler val: Du kan välja backtracking-teknik för att se över val systematiskt.
• Behöver utforska alla möjliga lösningar: Backtracking utforskar systematiskt alla lösningar genom att fatta en rad beslut som bygger på varandra.

Typer av bakåtspårningsproblem

Det finns tre typer av problem i backtracking-algoritmer: beslutsproblem, optimeringsproblem och uppräkningsproblem. Låt oss lära oss om dem nedan.

1. Beslutsproblem: I denna typ av problem är målet att avgöra om det finns en genomförbar lösning. Vi kontrollerar "ja" och "nej" svaren. Till exempel problemet med n-queens. Det är ett beslutsproblem som undersöker sannolikheten för att placera n damer på ett n × n schackbräde utan att attackera varandra.
2. Optimeringsproblem: I optimeringsproblem är målet att hitta den bästa möjliga lösningen bland många alternativ. Detta kan innebära att bestämma maximi- och minimivärdena för en viss funktion eller variabel. Tänk till exempel på ryggsäcksproblemet, där målet är att maximera det totala värdet av föremålen i väskan samtidigt som viktgränsen respekteras.
3. Uppräkningsproblem: Dess mål är att hitta alla möjliga lösningar på ett givet problem. Vi listar alla giltiga alternativ utan några utelämnanden. Ett exempel skulle vara att generera alla möjliga bokstavskombinationer från en given uppsättning tecken.

Tillämpningar av backtracking & exempel

Det finns olika tillämpningar av Backtracking. Några av dem förklaras nedan med sin pseudokod.

1. Sudoku Solver: Det här problemet innehåller ett 3×3-undernät med dubbletter av nummer. Backtracking-tekniken visar att lösningen returnerar falskt, vilket indikerar behovet av en annan 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-metoden avgör hur damer ska presenteras på ett N × N schackbräde så att ingen av dem hotar varandra.

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. Delmängd Summa Problem: Den används för att hitta delmängden av tal från en given uppsättning som summerar till en viss målsumma.

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. Hamiltons cykelproblem: Backtracking kan användas för att hitta en sluten tur i en graf som besöker varje vertex exakt en gång.
5. Problem med råtta i labyrint: Backtracking-tekniken används för att hitta vägen för en råtta från startpunkten för labyrinten till utgången.

Fördelar och nackdelar med Backtracking Algorithm

Fördelar med Backtracking Algorithm

Backtracking-tekniker används för att lösa komplexa problem. Det har många fördelar som:

• Backtracking-tekniken är effektiv för att hantera begränsningar.
• Denna metod är bra för att lösa optimeringsproblem.
• Tekniken fungerar för olika typer av problem.
• Denna procedur kan hjälpa till att granska alla möjliga lösningar.
• Eftersom den backar sparar den mer minne än Bruteforce-tekniken.

Nackdelar med Backtracking Algorithm

Backtracking-tekniker har också vissa begränsningar, såsom tidskomplexitet. Denna teknik har följande nackdelar:

• Det finns ingen garanterad lösning.
• Det är långsammare på grund av många kombinationer.
• Det har hög tidskomplexitet på grund av många möjligheter.
• Det är olämpligt för realtidsbegränsningar eftersom det kan ta lång tid att hitta den bästa lösningen.
• Effektiviteten beror på problemets komplexitetsnivå.

Skillnaden mellan backtracking och rekursion

Slutsats

Backtracking är en användbar algoritmisk strategi för att lösa komplexa problem genom att systematiskt utforska genomförbara lösningar och backtracka vid behov. Vi kan förvänta oss att bakåtspårningstekniker förbättras med förbättringar i beräkningskraft och algoritmisk effektivitet. Dessa framsteg gör det möjligt för dem att tackla större och mer komplexa problem effektivt.

Dessutom kan maskininlärningsmodeller vägleda bakåtspårningsbeslut baserat på tidigare inlärda mönster.

Alla dessa tekniska innovationer kommer att revolutionera backtracking-algoritmer, vilket gör dem till ett kraftfullt och mångsidigt verktyg för att ta itu med komplicerade problem inom olika domäner.