Ce este backtracking-ul?

Ce este backtracking-ul?

Ce este backtracking-ul?

Backtracking-ul este o metodă de rezolvare a problemelor care construiește soluția pas cu pas, alegând la fiecare pas o valoare posibilă. Dacă la un moment dat ne blocăm, ne întoarcem la pasul anterior și încercăm altă valoare.

Notă: Gândește-te la un labirint: mergi înainte până te lovești de un zid, apoi te întorci și încerci altă direcție.

Cei 3 pași ai backtracking-ului

• Alege o valoare pentru poziția curentă
• Verifică dacă valoarea este validă (respectă condițiile)
• Avansează la poziția următoare sau întoarce-te dacă nu mai ai valori valide

Ce trebuie să știi pentru BAC

La BAC, exercițiile de backtracking cer să generezi soluții care respectă anumite constrângeri — de exemplu, un anumit cost total, o anumită ordine a elementelor sau o anumită proprietate a cifrelor. Backtracking-ul încearcă toate variantele posibile și le păstrează doar pe cele care satisfac condițiile.

Notă: De obicei ți se dau primele câteva soluții generate și ți se cere să identifici o altă soluție sau să numeri ceva legat de ele.

Notă: Nu trebuie să scrii codul de backtracking la Subiectul I sau II. Trebuie doar să înțelegi ordinea în care soluțiile sunt generate și să le poți număra.

Cum se generează soluțiile

Backtracking-ul generează soluțiile în ordine sistematică, de la stânga la dreapta:

• fixează prima poziție cu prima valoare posibilă
• pentru fiecare valoare de pe prima poziție, parcurge toate valorile posibile pentru a doua poziție
• și tot așa, până completează toate pozițiile

Asta înseamnă că soluțiile apar într-o ordine lexicografică (ca în dicționar).

Exemplu 1 — Testul 3, 2021

Se generează toate modalitățile de a selecta un grup de 4 muzee din {MAVA, MCA, MCFR, MNHCV, MNLR, MNT}.

Primele 5 soluții sunt:

• (MAVA, MCA, MCFR, MNHCV)
• (MAVA, MCA, MCFR, MNLR)
• (MAVA, MCA, MCFR, MNT)
• (MAVA, MCA, MNHCV, MNLR)
• (MAVA, MCA, MNHCV, MNT)

Care este o soluție validă?

(MCA, MNHCV, MNLR, MNT)

De ce? Pentru că după ce se epuizează toate combinațiile care încep cu MAVA, backtracking-ul trece la MCA ca primul element, și generează în ordine toate combinațiile care încep cu MCA.

Exemplu 2 — Testul 1, 2021

Se generează toate numerele din intervalul [100,999] cu cifrele în ordine crescătoare, de paritate diferită pe poziții consecutive, cu suma egală cu 14.

Regulile de generare:

• cifra 1 < cifra 2 < cifra 3
• cifra 1 și cifra 2 au parități diferite
• cifra 2 și cifra 3 au parități diferite
• cifra 1 + cifra 2 + cifra 3 = 14

Backtracking-ul încearcă cifrele de la 1 la 9 pentru prima poziție, de la cifra1+1 la 9 pentru a doua, și așa mai departe.

| c1 | c2 | c3 | Par? | Sumă? |

|----|----|----|------|-------|

| 1 | 4 | 9 | impar-par-impar | 14 ✓ |

| 1 | 6 | 7 | impar-par-impar | 14 ✓ |

| 2 | 3 | 9 | par-impar-par | 14 ✓ |

| 3 | 4 | 7 | impar-par-impar | 14 ✓ |

| 3 | 6 | 5 | ordine? 5 < 6 | ✗ |

| 5 | 4 | 5 | ordine? 4 < 5 | ✗ |

| 5 | 6 | 3 | ordine? 3 < 6 | ✗ |

Numerele generate în ordine: 149, 167, 239, 347