Grįžimo algoritmai yra tarsi problemų sprendimo strategijos, padedančios ištirti įvairias galimybes ieškant geriausio sprendimo. Jie dirba bandydami skirtingus kelius, o jei vienas neveikia, jie atsitraukia ir bando kitą, kol randa tinkamą. Tai tarsi galvosūkio sprendimas išbandant skirtingus gabalus, kol jie puikiai sutampa.
Atsitraukimas
pasirinkimas rūšiuoti java
Turinys
- Kas yra grįžimo algoritmas?
- Kaip veikia grįžimo algoritmas?
- Grįžimo algoritmo pavyzdys
- Kada naudoti atgalinį algoritmą?
- Grįžimo algoritmo taikymai
- Grįžimo algoritmo pagrindas
- Standartinės problemos dėl grįžimo algoritmo
- Lengvos grįžimo algoritmo problemos
- Vidutinės grįžimo algoritmo problemos
- Sunkios problemos dėl grįžimo algoritmo
Kas yra grįžimo algoritmas?
Atsitraukimas yra problemų sprendimo algoritminė technika, kuri apima sprendimo ieškojimą laipsniškai bandant skirtingų variantų ir atšaukimas juos, jei jie veda į a aklavietė .
Jis dažniausiai naudojamas situacijose, kai reikia ištirti kelias problemas išspręsti, pvz., ieškant kelio labirinte arba sprendžiant galvosūkius, pvz. Sudoku . Pasiekus aklavietę, algoritmas grįžta į ankstesnį sprendimo tašką ir tiria kitą kelią, kol randamas sprendimas arba išnaudojamos visos galimybės.
Kaip veikia grįžimo algoritmas?
A grįžimo algoritmas veikia rekursyviai tyrinėdamas visus galimus problemos sprendimus. Pirmiausia jis pasirenka pradinį sprendimą, o tada išnagrinėja visus galimus to sprendimo plėtinius. Jei plėtinys veda į sprendimą, algoritmas grąžina tą sprendimą. Jei plėtinys nesukelia sprendimo, algoritmas grįžta prie ankstesnio sprendimo ir bando naudoti kitą plėtinį.
Toliau pateikiamas bendras atgalinio sekimo algoritmo veikimo aprašymas:
tcp ip modelis
- Pasirinkite pradinį sprendimą.
- Ištirkite visus galimus dabartinio sprendimo plėtinius.
- Jei išplėtimas veda prie sprendimo, grąžinkite tą sprendimą.
- Jei plėtinys nepadeda rasti sprendimo, grįžkite prie ankstesnio sprendimo ir bandykite kitą plėtinį.
- Kartokite 2–4 veiksmus, kol bus išnagrinėti visi galimi sprendimai.
Grįžimo algoritmo pavyzdys
Pavyzdys: Rasti trumpiausią kelią per labirintą
Įvestis: Labirintas, pavaizduotas kaip 2D masyvas, kur 0 reprezentuoja atvirą erdvę ir 1 reprezentuoja sieną.
Algoritmas:
- Pradėkite nuo pradžios taško.
- Kiekvienai iš keturių galimų krypčių (aukštyn, žemyn, kairėn, dešinėn) pabandykite judėti ta kryptimi.
- Jei judant ta kryptimi veda į pabaigos tašką, grįžkite pasirinktu keliu.
- Jei judant ta kryptimi nepasiekiamas galutinis taškas, grįžkite į ankstesnę padėtį ir bandykite kita kryptimi.
- Kartokite 2–4 veiksmus, kol pasieksite pabaigos tašką arba ištirsite visus galimus kelius.
Kada naudoti atgalinį algoritmą?
Atbulinės eigos algoritmai geriausiai naudojami sprendžiant problemas, kurios turi šias charakteristikas:
- Yra keli galimi problemos sprendimai.
- Problemą galima suskirstyti į smulkesnes dalis.
- Subproblemas galima išspręsti savarankiškai.
Grįžimo algoritmo taikymai
Grįžimo algoritmai naudojami įvairiose programose, įskaitant:
- Galvosūkių (pvz., Sudoku, kryžiažodžių) sprendimas
- Rasti trumpiausią kelią per labirintą
- Planavimo problemos
- Išteklių paskirstymo problemos
- Tinklo optimizavimo problemos
Grįžimo algoritmo pagrindas:
- Skirtumas tarp Backtracking ir Branch-N-Bound technikos
- Kuo skiriasi „Backtracking“ ir „Recursion“?
Standartinės grįžimo algoritmo problemos:
- Riterio kelionės problema
- Žiurkė labirinte
- N Karalienės problema | Grįžimas atgal-3
- Pogrupio sumos problema
- m Spalvinimo problema
- Hamiltono ciklas
- Sudoku | Grįžimas atgal-7
- Magnetinis galvosūkis
- Pašalinkite netinkamus skliaustus
- Atgalinis metodas generuoti n bitų pilkus kodus
- Parašykite programą, kuri spausdintų visas nurodytos eilutės permutacijas
Lengvos problemos, susijusios su grįžimo algoritmu:
- Grįžkite atgal, kad surastumėte visus poaibius
- Patikrinkite, ar nurodyta eilutė yra sumos eilutė
- Suskaičiuokite visus galimus kelius tarp dviejų viršūnių
- Raskite visus atskirus tam tikros aibės poaibius
- Raskite, ar kelias nuo šaltinio yra ilgesnis nei k
- Spausdinkite visus kelius nuo nurodyto šaltinio iki paskirties vietos
- Atspausdinkite visas įmanomas eilutes, kurias galima padaryti tarpų
Vidutinės grįžimo algoritmo problemos:
- Virvės vilkimas
- 8 karalienės problema
- Kombinuota suma
- Warnsdorffo algoritmas Riterio kelionės problemai spręsti
- Raskite kelius nuo kampinio langelio iki vidurio labirinto langelio
- Raskite didžiausią galimą skaičių atlikdami ne daugiau kaip K apsikeitimo sandorius
- Žiurkė labirinte su keliais žingsniais arba šuoliu leidžiama
- N Karalienė O(n) erdvėje
Sunkios problemos dėl grįžimo algoritmo:
- Maitinimo rinkinys leksikografine tvarka
- Word Break problema naudojant Backtracking
- Aibės padalijimas į K poaibius su lygia suma
- Ilgiausias įmanomas maršrutas matricoje su kliūtimis
- Raskite trumpiausią saugų maršrutą kelyje su minomis
- Spausdinkite visas palindromines eilutės skaidinius
- Spausdinami visi N-Queen problemos sprendimai
- Spausdinkite visas ilgiausias įprastas posekcijas leksikografine tvarka
Greitos nuorodos :
- Sužinokite duomenų struktūrą ir algoritmus | DSA mokymo programa
- 20 populiariausių interviu klausimų apie grįžimo algoritmą
- „Vaizdo įrašai“ apie „Backtracking“.