logo

TechCodeview

Atkāpšanās algoritms

Atkāpšanās algoritmi ir kā problēmu risināšanas stratēģijas, kas palīdz izpētīt dažādas iespējas, lai atrastu labāko risinājumu. Viņi strādā, izmēģinot dažādus ceļus, un, ja viens nedarbojas, viņi atkāpjas un mēģina citu, līdz atrod īsto. Tas ir kā mīklas risināšana, pārbaudot dažādus gabalus, līdz tie lieliski sader kopā.

ātrā šķirošana

Atkāpšanās

Satura rādītājs



Kas ir atkāpšanās algoritms?

Atkāpšanās ir problēmu risināšanas algoritmisks paņēmiens, kas ietver risinājuma atrašanu pakāpeniski, mēģinot dažādas iespējas un atsaukšana tos, ja tie noved pie a strupceļš .

To parasti izmanto situācijās, kad jums ir jāizpēta vairākas problēmas risināšanas iespējas, piemēram, meklējot ceļu labirintā vai risinot mīklas, piemēram, Sudoku . Kad tiek sasniegts strupceļš, algoritms atgriežas iepriekšējā lēmuma pieņemšanas punktā un pēta citu ceļu, līdz tiek atrasts risinājums vai visas iespējas ir izsmeltas.

saglabātās programmas vadība

Kā darbojas atkāpšanās algoritms?

A atkāpšanās algoritms darbojas, rekursīvi izpētot visus iespējamos problēmas risinājumus. Tas sākas, izvēloties sākotnējo risinājumu, un pēc tam tiek izpētīti visi iespējamie šī risinājuma paplašinājumi. Ja paplašinājums noved pie risinājuma, algoritms atgriež šo risinājumu. Ja paplašinājums nenoved pie risinājuma, algoritms atgriežas pie iepriekšējā risinājuma un mēģina izmantot citu paplašinājumu.

Tālāk ir sniegts vispārējs atkāpšanās algoritma darbības apraksts.

  1. Izvēlieties sākotnējo risinājumu.
  2. Izpētiet visus iespējamos pašreizējā risinājuma paplašinājumus.
  3. Ja paplašinājums noved pie risinājuma, atgrieziet šo risinājumu.
  4. Ja paplašinājums nenodrošina risinājumu, atgriezieties pie iepriekšējā risinājuma un izmēģiniet citu paplašinājumu.
  5. Atkārtojiet 2.-4. darbību, līdz ir izpētīti visi iespējamie risinājumi.

Atkāpšanās algoritma piemērs

Piemērs: Īsākā ceļa atrašana caur labirintu

Ievade: Labirints, kas attēlots kā 2D masīvs, kur 0 apzīmē atvērtu telpu un 1 attēlo sienu.

Algoritms:

  1. Sāciet no sākuma punkta.
  2. Katrā no četriem iespējamajiem virzieniem (augšup, lejup, pa kreisi, pa labi) mēģiniet pārvietoties šajā virzienā.
  3. Ja kustība šajā virzienā ved uz beigu punktu, atgriezieties pa izvēlēto ceļu.
  4. Ja kustība šajā virzienā nenoved uz beigu punktu, atgriezieties iepriekšējā pozīcijā un mēģiniet citu virzienu.
  5. Atkārtojiet 2.-4. darbību, līdz ir sasniegts beigu punkts vai visi iespējamie ceļi ir izpētīti.

Kad izmantot atkāpšanās algoritmu?

Atkāpšanās algoritmus vislabāk izmantot, lai atrisinātu problēmas, kurām ir šādas īpašības:

  • Problēmai ir vairāki iespējamie risinājumi.
  • Problēmu var sadalīt mazākās apakšproblēmās.
  • Apakšproblēmas var atrisināt neatkarīgi.

Atkāpšanās algoritma pielietojumi

Atkāpšanās algoritmi tiek izmantoti dažādās lietojumprogrammās, tostarp:

java atlases kārtošana
  • Mīklu risināšana (piem., Sudoku, krustvārdu mīklas)
  • Īsākā ceļa atrašana caur labirintu
  • Plānošanas problēmas
  • Problēmas ar resursu piešķiršanu
  • Tīkla optimizācijas problēmas

Atkāpšanās algoritma pamati:

  • Atšķirība starp Backtracking un Branch-N-Bound tehniku
  • Kāda ir atšķirība starp Backtracking un Recursion?

Standarta problēmas atkāpšanās algoritmā:

  • Bruņinieka tūres problēma
  • Žurka labirintā
  • N Karalienes problēma | Atkāpšanās — 3
  • Apakškopas summas problēma
  • m Krāsošanas problēma
  • Hamiltona cikls
  • Sudoku | Atkāpšanās — 7
  • Magnēta Puzle
  • Noņemiet nederīgās iekavas
  • Atkāpšanās pieeja n bitu pelēko kodu ģenerēšanai
  • Uzrakstiet programmu, lai izdrukātu visas dotās virknes permutācijas

Vienkāršas problēmas atkāpšanās algoritmā:

  • Atkāpšanās, lai atrastu visas apakškopas
  • Pārbaudiet, vai dotā virkne ir summa-virkne
  • Saskaitiet visus iespējamos ceļus starp divām virsotnēm
  • Atrodiet visas noteiktās kopas atšķirīgās apakškopas
  • Atrodiet, vai ceļš no avota ir garāks par k
  • Drukāt visus ceļus no dotā avota uz galamērķi
  • Izdrukājiet visas iespējamās virknes, ko var izveidot, ievietojot atstarpes

Vidējas problēmas atkāpšanās algoritmā:

  • Virves vilkšana
  • 8 karalienes problēma
  • Kombinētā summa
  • Vornsdorfa algoritms Naita ceļojuma problēmai
  • Atrodiet ceļus no stūra šūnas uz vidējo šūnu labirintā
  • Atrodiet maksimālo iespējamo skaitu, veicot ne vairāk kā K mijmaiņas darījumus
  • Žurka labirintā ar vairākiem soļiem vai lēcienu atļauts
  • N Karaliene O(n) telpā

Grūtās problēmas atkāpšanās algoritmā:

  • Jaudas komplekts leksikogrāfiskā secībā
  • Vārdu pārtraukuma problēma, izmantojot Backtracking
  • Kopas sadalīšana K apakškopās ar vienādu summu
  • Garākais iespējamais maršruts matricā ar šķēršļiem
  • Atrodiet īsāko drošo ceļu ceļā ar kājnieku mīnām
  • Drukājiet visus virknes palindromiskos nodalījumus
  • Visu N-Queen problēmas risinājumu drukāšana
  • Drukājiet visas garākās kopīgās apakšsecības leksikogrāfiskā secībā

Ātrās saites :

  • Uzziniet datu struktūru un algoritmus | DSA apmācība
  • 20 populārākie intervijas jautājumi par atkāpšanās algoritmu
  • “Video” par Backtracking