Tagajärgimise algoritm

Mis on taganemisalgoritm?

Backtracking on algoritm, mis otsib lahendamiseks võimalikke kombinatsioone arvutusprobleemid. See loob järk-järgult kandidaate ja eemaldab need, mis ei vasta antud piirangutele. See tehnika on väga kasulik olukordades, kus peate mitme võimaliku tulemuse hulgast valima teostatava lahenduse.

Seda algoritmi peetakse paremaks ja tõhusamaks kui Brute Force'i lähenemine. Erinevalt Bruteforce'ist, mis proovib kõiki võimalikke lahendusi, keskendub Backtracking ainult ühe lõpplahenduse leidmisele vastavalt etteantud tingimustele. piiranguid. Samuti säästab see aega ja mälu, tühistades viimase sammu (tagasiminek) ja proovides pärast ummikusse jõudmist mõnda muud võimalust. Lisaks peatub see kohe, kui leitakse sobiv lahendus.

Backtracking on laialdaselt kasutatav tehnika, kuna see suudab lahendada keerulisi probleeme ilma ammendava ressursside tarbimiseta. See on eriti kasulik probleemide puhul, kus tuleb täita mitmeid piiranguid, näiteks Sudoku, n queen probleem ja ajakava. Potentsiaalsetes lahendustes nutikalt navigeerides võib tagasiliikumine leida vastuse, mis vastab kõigile tingimustele. See muudab selle hindamatuks ülesannete jaoks, mis nõuavad nii täpsust kui ka tõhusust.

Kuidas Backtracking Algoritm töötab?

Tagastamisalgoritmid on probleemide lahendamise tehnika, mis hõlmab õigete lahenduste leidmist samm-sammult. Kui sammu piirangud ei vasta teatud tingimustele, naaseb algoritm eelmise sammu juurde.

Tagajärgimise algoritm

Seejärel jätkatakse muude võimalike kombinatsioonidega, mis vastavad antud piirangutele. Kuna võimalikke kombinatsioone on palju, valib see ühe kõige rahuldavama valiku ja lahendab probleemi järjestikku. See algoritmiline tehnika on kasulik, kui peate lahendama ühe või mitu võimalikku valikut. Taganemine tähendab oma valiku tühistamist, kui tekib olukord, mis ei anna kehtivat lahendust.

Tagasiliikumise algoritmis on probleemi lahendamiseks üldiselt järgmised sammud.

1. samm) Initsialiseerimine: Alustage esialgse tühja/osalise lahendusega.

Samm 2) Valik: konkreetsete kriteeriumide ja piirangute põhjal valige praeguse lahenduse laiendamiseks üks suvand.

3. etapp) uurimine: lahendage rekursiivselt valitud kandidaati kaaludes ja probleemide lahendamise protsessis edasi liikudes.

4. samm) Piirangute kontroll: Kontrollige igal sammul, kas praegune osalahendus rikub mingeid piiranguid. Kui jah, minge tagasi eelmise sammu juurde ja proovige teist kandidaati.

Samm 5) Lõpetamine: Taganemisprotsess peatub, kui leitakse sobiv lahendus või kõik kombinatsioonid on ammendatud.

6. samm) Tagasiminek: kui praegune valik antud probleemi ei lahenda, naaseb see eelmisele olekule. Seejärel kaalutakse uut võimalust antud probleemi lahendamiseks.

Samm 7) Korrake: jätkake nende sammudega, kuni probleem on lahendatud või kõik valikud on uuritud.

Backtracking algoritmi rekursiivne olemus

Backtracking algoritmid on oma olemuselt rekursiivsed. See tähendab, et algoritm kutsub ennast erinevate parameetritega, kuni leiab lahenduse või on katsetanud kõiki võimalusi:

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)

Üldised terminid, mis on seotud taganemisprobleemidega

Need on mõned põhiterminid, mis on seotud Backtracking tehnikaga:

  • Lahenduse vektor: Esitab lahendusi n-korteritena, näiteks (X1, X2, …, Xn).
  • Piirangud: X väärtusi piiravad reeglid, kaudsed ja otsesed.
  • Lahendusruum: kõik kehtivad X-väärtused, mis vastavad selgetele piirangutele.
  • Osariigi kosmosepuu: kujutab lahendusruumi puuna.
  • Riigi ruum: kirjeldab teid olekuruumi puus.
  • Probleemne olek: sõlmed otsingupuus, mis esindavad osalahendusi.
  • Lahendusriigid: olekud, mis moodustavad S-is kehtivaid lahenduskortereid.
  • Vastuse osariigid: täitke kaudsed piirangud ja andke soovitud lahendused.
  • Paljutõotav sõlm: Viib soovitud lahendusteni ja jääb teostatavaks.
  • Mittetõotav sõlm: Viib teostamatutesse olekutesse, mida edasi ei uurita.
  • Reaalajas sõlm: Loodud uurimata lastega.
  • E-sõlm: reaalajas sõlm koos käimasoleva lapse põlvkonnaga.
  • Surnud sõlm: Kõiki lapsi ei laiendata.
  • Sügavuse esimese sõlme genereerimine: kasutab järgmise E-sõlmena uusimat aktiivset sõlme.
  • Piirdefunktsioon: Maksimeerib või minimeerib B(x1, x2, …, Xa) optimeerimiseks.
  • Staatilised puud: puu formuleering, mis ei sõltu probleemi esinemisest.
  • Dünaamilised puud: puu koostis varieerub olenevalt probleemist.

Millal kasutada taganemisalgoritmi?

Kompleksse probleemi lahendamiseks saame valida Backtracking tehnika, kui:

  • Valikuid on palju: Tagasiminek on sobiv, kui probleemi lahendamise protsessi igas etapis on palju võimalusi. Need valikud võivad olla seotud esemete ja käikude valikuga.
  • Selge parim valik puudub: kui saadaolevate valikute hulgast parima valiku määramiseks ei ole piisavalt teavet, võib kasutada Backtracking algoritmi.
  • Otsus toob kaasa rohkem valikuid: Võite valida taganemistehnika valikute süstemaatiliseks ülevaatamiseks.
  • Tuleb uurida kõiki võimalikke lahendusi: Backtracking uurib süstemaatiliselt kõiki lahendusi, tehes üksteisele tuginevaid otsuseid.

Taganemisprobleemide tüübid

Tagasiliikumise algoritmides on kolme tüüpi probleeme: otsustusprobleemid, optimeerimisprobleemid ja loendusprobleemid. Tutvume nendega allpool.

  1. Otsuse probleem: Seda tüüpi probleemi puhul on eesmärk kindlaks teha, kas on olemas teostatav lahendus. Kontrollime "jah" ja "ei" vastuseid. Näiteks n-kuningannade probleem. See on otsustusprobleem, mis uurib tõenäosust paigutada n emandat n × n malelauale ilma üksteist rünnata.
  2. Optimeerimise probleem: Optimeerimisülesannetes on eesmärgiks leida paljude valikute seast parim võimalik lahendus. See võib hõlmata teatud funktsiooni või muutuja maksimaalse ja minimaalse väärtuse määramist. Näiteks kaaluge seljakoti probleemi, mille eesmärk on maksimeerida kotis olevate esemete koguväärtust, järgides samal ajal selle kaalupiirangut.
  3. Loendamise probleem: Selle eesmärk on leida antud probleemile kõik võimalikud lahendused. Loetleme kõik kehtivad valikud ilma väljajätmisteta. Näide oleks kõigi võimalike tähekombinatsioonide genereerimine antud märgikomplektist.

Backtracking rakendused ja näited

Backtrackingu rakendusi on erinevaid. Mõned neist on allpool selgitatud nende pseudokoodiga.

  1. Sudoku Solver: See probleem sisaldab 3 × 3 alamvõrku, millel on dubleerivad numbrid. Tagasijätmise tehnika näitab, et lahendus tagastab vale, mis viitab vajadusele teistsuguse numbripaigutuse järele.
  2. 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
    
  3. N-Queen probleem: Backtracking lähenemisviis määrab, kuidas esitada emandasid N × N malelaual nii, et ükski neist ei ohustaks üksteist.
  4. 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
    
  5. Alamhulga summa ülesanne: seda kasutatakse antud komplektist arvude alamhulga leidmiseks, mis annab kokku kindla sihtsumma.
  6. 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)
    
  7. Hamiltoni tsükli probleem: Tagurdamist saab rakendada, et leida graafikult suletud ringkäik, mis külastab iga tippu täpselt üks kord.
  8. Rott labürindis probleem: Backtracking tehnikat kasutatakse selleks, et leida roti tee labürindi alguspunktist väljapääsuni.

Backtracking algoritmi eelised ja puudused

Backtracking algoritmi eelised

Keeruliste probleemide lahendamiseks kasutatakse taganemistehnikaid. Sellel on palju eeliseid, näiteks:

  • Tagasijätmise tehnika on piirangute käsitlemisel tõhus.
  • See meetod sobib hästi optimeerimisprobleemide lahendamiseks.
  • Tehnika töötab erinevat tüüpi probleemide korral.
  • See protseduur võib aidata üle vaadata kõik võimalikud lahendused.
  • Kuna see taandub, säästab see rohkem mälu kui Bruteforce'i tehnika.

Tagastamisalgoritmi puudused

Tagasijätmise tehnikatel on ka mõned piirangud, näiteks ajaline keerukus. Sellel tehnikal on järgmised puudused:

  • Garanteeritud lahendust pole.
  • See on paljude kombinatsioonide tõttu aeglasem.
  • See on paljude võimaluste tõttu ajaliselt keeruline.
  • See ei sobi reaalajas piirangute jaoks, kuna parima lahenduse leidmine võib võtta kaua aega.
  • Tõhusus sõltub probleemi keerukusest.

Erinevus tagasisõidu ja rekursiooni vahel

Rekursiooni Tagasitõmbumine
Helistab ise, kuni jõutakse baasjuhtumini. Kasutab rekursiooni, et vaadata üle kõik võimalused, kuni leitakse parim teostatav tulemus.
Alt-üles lähenemine. Ülevalt alla lähenemine.
Ühtegi väärtust ei jäeta kõrvale. Mitteelujõulised lahendused lükatakse tagasi.

Järeldus

Backtracking on kasulik algoritmiline strateegia keeruliste probleemide lahendamiseks, uurides süstemaatiliselt teostatavaid lahendusi ja vajaduse korral tagasi liikumise. Võime eeldada, et tagasiliikumise tehnikad paranevad arvutusvõimsuse ja algoritmilise tõhususe paranemisega. Need edusammud võimaldavad neil tõhusalt lahendada suuremaid ja keerukamaid probleeme.

Lisaks võivad masinõppemudelid suunata tagasipöördumisotsuseid, mis põhinevad varem õpitud mustritel.

Kõik need tehnoloogilised uuendused muudavad tagasikäigu algoritmid revolutsiooniliselt, muutes need võimsaks ja mitmekülgseks tööriistaks keeruliste probleemide lahendamiseks erinevates valdkondades.