Algoritam povratnog praćenja

Što je algoritam za praćenje unatrag?

Backtracking je algoritam koji traži moguće kombinacije za rješavanje računalni problemi. Postupno gradi kandidate i uklanja one koji ne zadovoljavaju zadana ograničenja. Ova tehnika je vrlo korisna u situacijama kada morate odabrati izvedivo rješenje između više mogućih rezultata.

Ovaj se algoritam smatra boljim i učinkovitijim od pristupa Brute Force. Za razliku od Bruteforcea, koji isprobava sva moguća rješenja, Backtracking se fokusira na pronalaženje samo jednog konačnog rješenja prema zadanom ograničenja. Također štedi vrijeme i memoriju poništavanjem posljednjeg koraka (povratak) i pokušajem druge opcije nakon što dođete do slijepe ulice. Osim toga, zaustavlja se čim se pronađe valjano rješenje.

Praćenje unatrag široko je korištena tehnika jer može riješiti složene probleme bez iscrpljujućeg trošenja resursa. Osobito je koristan za probleme u kojima se moraju zadovoljiti brojna ograničenja, kao što su Sudoku, problem s kraljicom i raspored. Inteligentnim kretanjem kroz potencijalna rješenja, praćenje unatrag može pronaći odgovor koji zadovoljava sve uvjete. To ga čini neprocjenjivim za zadatke koji zahtijevaju i preciznost i učinkovitost.

Kako radi algoritam povratnog praćenja?

Algoritmi povratnog praćenja tehnika su rješavanja problema koja uključuje pronalaženje valjanih rješenja korak po korak. Ako ograničenja koraka ne zadovoljavaju određene uvjete, algoritam se vraća na prethodni korak.

Zatim se nastavlja s drugim mogućim kombinacijama koje zadovoljavaju zadana ograničenja. Budući da postoje brojne moguće kombinacije, odabire jednu od najzadovoljavajućih opcija i rješava problem redom. Ova algoritamska tehnika korisna je kada trebate riješiti jednu ili više mogućih opcija. Odustajanje znači poništavanje vašeg izbora kad god se pojavi situacija koja ne donosi valjano rješenje.

Algoritam povratnog praćenja općenito ima sljedeće korake za rješavanje problema:

Korak 1) Inicijalizacija: Počnite s početnim praznim/djelomičnim rješenjem.

Korak 2) Odabir: Na temelju specifičnih kriterija i ograničenja odaberite jednu opciju za proširenje trenutnog rješenja.

Korak 3) Istraživanje: Rekurzivno rješavanje uzimajući u obzir odabranog kandidata i napredujući u procesu rješavanja problema.

Korak 4) Provjera ograničenja: Provjerite krši li trenutno djelomično rješenje ograničenja u svakom koraku. Ako se dogodi, vratite se na prethodni korak i pokušajte s drugim kandidatom.

Korak 5) Raskid: Proces vraćanja unatrag se zaustavlja kada se pronađe valjano rješenje ili su sve kombinacije iscrpljene.

Korak 6) Povratak: Ako trenutna opcija ne riješi zadani problem, vraća se na prethodno stanje. Zatim razmatra novu opciju za rješavanje zadanog problema.

Korak 7) Ponovite: Nastavite s ovim koracima dok se problem ne riješi ili dok se ne istraže sve mogućnosti.

Rekurzivna priroda algoritma za praćenje unatrag

Algoritmi povratnog praćenja su rekurzivne prirode. To znači da algoritam sam sebe poziva s različitim parametrima dok ne pronađe rješenje ili dok ne testira sve mogućnosti:

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)

Uobičajeni pojmovi koji se odnose na probleme povratnog praćenja

Ovo su neki osnovni pojmovi koji se odnose na tehniku povratnog praćenja:

Vektor rješenja: Predstavlja rješenja kao n-torke, poput (X1, X2, …, Xn).
ograničenja: Pravila koja ograničavaju vrijednosti X, implicitne i eksplicitne.
Prostor rješenja: Sve važeće X vrijednosti koje zadovoljavaju eksplicitna ograničenja.
Državno svemirsko stablo: Predstavlja prostor rješenja kao stablo.
Državni prostor: Opisuje staze u stablu prostora stanja.
Stanje problema: Čvorovi u stablu pretraživanja koji predstavljaju djelomična rješenja.
Stanja rješenja: Stanja koja tvore valjane torke rješenja u S.
Odgovor države: Zadovoljite implicitna ograničenja i dajte željena rješenja.
Obećavajući čvor: Dovodi do željenih rješenja i ostaje izvedivo.
Neobećavajući čvor: Vodi do neizvedivih stanja, ne istražuje se dalje.
Živi čvor: Generirano s neistraženom djecom.
E-čvor: Živi čvor s generiranjem potomaka u tijeku.
Mrtav čvor: Nema daljnjeg proširenja svih generiranih potomaka.
Generacija prvog čvora dubine: Koristi najnoviji aktivni čvor kao sljedeći E-čvor.
Ograničavajuća funkcija: Maksimizira ili minimizira B(x1, x2, …, Xa) za optimizaciju.
Statično drveće: Formulacija stabla neovisna o instanci problema.
Dinamička stabla: Formulacija stabla varira ovisno o instanci problema.

Kada koristiti algoritam za praćenje unatrag?

Možemo odabrati tehniku povratnog praćenja za rješavanje složenog problema kada:

Postoji mnogo izbora: Praćenje unazad je prikladno ako postoji mnogo opcija u svakom koraku procesa rješavanja problema. Ove se opcije mogu odnositi na odabir stavki i poteza.
Nema jasnog najboljeg izbora: Kada nema dovoljno informacija za određivanje najboljeg izbora među dostupnim opcijama, može se koristiti algoritam povratnog praćenja.
Odluka vodi do više izbora: Možete odabrati tehnika povratnog praćenja za sustavan pregled izbora.
Potrebno je istražiti sva moguća rješenja: Praćenje unatrag sustavno istražuje sva rješenja donošenjem niza odluka koje se nadovezuju jedna na drugu.

Vrste problema povratnog praćenja

Postoje tri vrste problema u algoritmima praćenja unatrag: problemi odlučivanja, problemi optimizacije i problemi nabrajanja. Naučimo o njima u nastavku.

Problem odlučivanja: U ovoj vrsti problema cilj je utvrditi postoji li izvedivo rješenje. Provjeravamo odgovore "da" i "ne". Na primjer, problem n-kraljica. To je problem odlučivanja koji ispituje vjerojatnost postavljanja n kraljica na n × n šahovsku ploču bez međusobnog napada.
Problem optimizacije: U problemima optimizacije cilj je pronaći najbolje moguće rješenje među mnogim opcijama. To može uključivati određivanje maksimalnih i minimalnih vrijednosti određene funkcije ili varijable. Na primjer, razmotrite problem ruksaka, gdje je cilj maksimizirati ukupnu vrijednost predmeta u torbi uz pridržavanje ograničenja težine.
Problem nabrajanja: Cilj mu je pronaći sva moguća rješenja za određeni problem. Navodimo svaku valjanu opciju bez ikakvih propusta. Primjer bi bilo generiranje svih mogućih kombinacija slova iz zadanog skupa znakova.

Primjene povratnog praćenja i primjeri

Postoje različite primjene Backtrackinga. Neki od njih su objašnjeni u nastavku sa svojim pseudo kodom.

Sudoku Solver: Ovaj problem sadrži podmrežu 3×3 s dvostrukim brojevima. Tehnika praćenja unazad pokazat će da rješenje vraća netočno, što ukazuje na potrebu za drugačijim postavljanjem broja.

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

Problem s N-kraljicom: Pristup vraćanja unatrag određuje kako predstaviti kraljice na N × N šahovskoj ploči tako da niti jedna od njih ne prijeti jedna drugoj.

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

Problem zbroja podskupa: Koristi se za pronalaženje podskupa brojeva iz zadanog skupa čiji zbroj daje određeni ciljni zbroj.

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)

Problem Hamiltonovog ciklusa: Praćenje unatrag može se primijeniti za pronalaženje zatvorenog obilaska u grafu koji posjećuje svaki vrh točno jednom.
Problem štakora u labirintu: Tehnika vraćanja unatrag koristi se za pronalaženje staze štakora od početne točke labirinta do izlaza.

Prednosti i nedostaci algoritma povratnog praćenja

Prednosti algoritma povratnog praćenja

Tehnike povratnog praćenja koriste se za rješavanje složenih problema. Ima mnoge prednosti kao što su:

Tehnika povratnog praćenja učinkovita je za rukovanje ograničenjima.
Ova metoda je dobra za rješavanje problema optimizacije.
Tehnika djeluje na različite vrste problema.
Ovaj postupak može pomoći u pregledu svih mogućih rješenja.
Budući da se vraća unatrag, štedi više memorije od tehnike Bruteforce.

Nedostaci algoritma povratnog praćenja

Tehnike povratnog praćenja također imaju neka ograničenja, poput vremenske složenosti. Ova tehnika ima sljedeće nedostatke:

Ne postoji zajamčeno rješenje.
Sporiji je zbog mnogih kombinacija.
Ima veliku vremensku složenost zbog mnogih mogućnosti.
Nije prikladan za ograničenja u stvarnom vremenu jer pronalaženje najboljeg rješenja može potrajati dugo.
Učinkovitost ovisi o razini složenosti problema.

Razlika između povratnog praćenja i rekurzije

Rekurzije	odustajanja
Poziva samu sebe dok se ne dosegne osnovni slučaj.	Koristi rekurziju za pregled svih mogućnosti dok se ne pronađe najbolji mogući rezultat.
Pristup odozdo prema gore.	Pristup odozgo prema dolje.
Niti jedna vrijednost se ne odbacuje.	Neodrživa rješenja se odbijaju.

Zaključak

Traženje unatrag je korisna algoritamska strategija za rješavanje složenih problema sustavnim istraživanjem izvedivih rješenja i vraćanjem unatrag kada je to potrebno. Možemo očekivati da će se tehnike povratnog praćenja poboljšati s poboljšanjima u računskoj snazi i algoritamskoj učinkovitosti. Ova poboljšanja omogućit će im učinkovito rješavanje većih i složenijih problema.

Osim toga, modeli strojnog učenja mogu voditi odluke o povratku na temelju prethodno naučenih obrazaca.

Sve ove tehnološke inovacije revolucionizirat će algoritme za praćenje unatrag, čineći ih moćnim i svestranim alatom za rješavanje kompliciranih problema u različitim domenama.