Backtracking BAC: ordine lexicografică și restricții

Ordinea lexicografică a soluțiilor de backtracking depinde de ordinea candidaților și de felul în care sunt explorate prefixele. La BAC, o restricție suplimentară elimină unele ramuri, dar nu justifică schimbarea arbitrară a ordinii soluțiilor rămase. Trebuie să urmărești construcția exactă.

Lecția privește backtrackingul de la matematică-informatică. Vom genera alegeri de k numere din mulțimea de la unu la n, scrise crescător, astfel încât două numere alese să nu fie consecutive. Exemplul leagă ordinea de afișare de validarea prefixului și de eliminarea ramurilor imposibile. Aplică aceleași întrebări când analizezi un subiect de BAC.

De ce impunem ordinea crescătoare în soluție

Alegerea numerelor unu și trei reprezintă același grup ca alegerea numerelor trei și unu. Pentru a nu afișa același grup în mai multe ordini, păstrăm o singură reprezentare: valorile strict crescătoare.

Restricția de a nu avea numere consecutive cere mai mult decât creștere strictă. După valoarea unu, următoarea trebuie să fie cel puțin trei. După trei, următoarea trebuie să fie cel puțin cinci.

Astfel, candidatul minim pentru o poziție este valoarea precedentă plus doi. Pentru prima poziție, candidatul minim este unu. Nu avem nevoie de un tablou de marcaje, deoarece creșterea impusă exclude deja repetarea valorilor.

Ordinea în interior și ordinea între soluții

Faptul că fiecare soluție este crescătoare nu garantează singur că lista soluțiilor este ordonată lexicografic. Ai putea afișa grupul doi, patru înaintea grupului unu, cinci, deși ambele sunt crescătoare în interior.

Pentru ordinea lexicografică, compari două soluții la prima poziție la care diferă. Soluția cu valoarea mai mică pe acea poziție trebuie să apară prima. Restul pozițiilor nu mai influențează comparația după găsirea primei diferențe.

Algoritmul va încerca valorile candidate crescător și va termina toate completările unui prefix înainte să treacă la următorul. Această organizare produce ordinea cerută fără o sortare ulterioară a listei.

Un exemplu complet

Pentru n egal cu cinci și k egal cu doi, soluțiile sunt următoarele:

1 3
1 4
1 5
2 4
2 5
3 5

Perechea unu, doi este exclusă deoarece numerele sunt consecutive. Perechea trei, unu nu apare deoarece același grup este reprezentat deja crescător ca unu, trei. Lista are șase soluții distincte.

Observă că toate soluțiile care încep cu unu apar înaintea celor care încep cu doi. În interiorul unui prefix fix, a doua valoare crește. Aceasta este o verificare directă a ordinii lexicografice.

Eliminarea unui prefix care nu mai poate fi completat

Să presupunem că mai trebuie alese două valori după candidatul curent. Din cauza distanței minime de doi, ele trebuie să fie cel puțin candidatul plus doi și candidatul plus patru. Ultima trebuie să rămână cel mult n.

În general, dacă după poziția curentă mai rămân r poziții, candidatul nu poate depăși n minus de două ori r. O valoare mai mare ar lăsa prea puțin spațiu pentru completare, chiar dacă prefixul actual nu încalcă încă restricția locală.

n	Poziții rămase după alegere	Cel mai mare candidat posibil
7	0	7
7	1	5
7	2	3

Aceasta este o regulă de eliminare anticipată a ramurilor imposibile. Nu elimină soluții valide, deoarece orice completare trebuie să respecte distanțele minime dintre valorile alese.

Program C++ complet

Programul citește n și k, cu n între unu și cincisprezece și k între unu și n. Afișează fiecare soluție pe o linie, în ordine lexicografică. Dacă nu există nicio soluție, afișează mesajul NU EXISTA.

#include <iostream>
using namespace std;

int n, k, x[16];
bool exista = false;

void genereaza(int pozitie, int minim) {
    if (pozitie > k) {
        exista = true;
        for (int i = 1; i <= k; ++i) {
            if (i > 1) cout << ' ';
            cout << x[i];
        }
        cout << '\n';
        return;
    }
    int maxim = n - 2 * (k - pozitie);
    for (int valoare = minim; valoare <= maxim; ++valoare) {
        x[pozitie] = valoare;
        genereaza(pozitie + 1, valoare + 2);
    }
}

int main() {
    cin >> n >> k;
    genereaza(1, 1);
    if (!exista) cout << "NU EXISTA";
    return 0;
}

Parametrul minim reprezintă cel mai mic candidat permis de prefix. Limita maximă reprezintă cel mai mare candidat care mai lasă loc unei completări. Dacă minimul depășește maximul, bucla nu execută niciun pas și ramura se încheie fără soluție.

Când există cel puțin o soluție

Cea mai compactă alegere posibilă este unu, trei, cinci și așa mai departe. Pentru k valori, ultima este de două ori k minus unu. Există o soluție dacă această valoare nu depășește n.

Pentru n egal cu patru și k egal cu trei, ar fi necesare cel puțin valorile unu, trei, cinci. Ultima depășește limita, deci nu există soluții. Programul detectează situația prin limitele candidaților, fără să afișeze prefixe incomplete.

Pentru n egal cu cinci și k egal cu trei, există exact soluția unu, trei, cinci. Orice creștere a uneia dintre alegeri ar obliga valorile următoare să depășească limita.

Verificarea numărului de soluții

Pentru un control independent, poți transforma valorile alese. Din prima nu scazi nimic, din a doua scazi unu, din a treia scazi doi și continui astfel. Distanța minimă de doi devine creștere strictă obișnuită.

Rezultă o alegere de k valori dintr-o mulțime cu n minus k plus unu elemente. Numărul soluțiilor este numărul acestor combinări, atunci când există suficient spațiu. Pentru n egal cu cinci și k egal cu doi, alegi două valori din patru, obținând șase.

Formula verifică totalul, dar nu verifică ordinea afișării. Pentru aceasta trebuie comparată lista sau urmărită ordinea explorării. Două programe pot avea același număr de soluții și ordini diferite.

Greșeli care schimbă mulțimea soluțiilor

Dacă următorul candidat pornește de la valoarea precedentă plus unu, permiți numere consecutive. Dacă pornește de la aceeași valoare, permiți și repetări. Dacă pornește de la unu la fiecare nivel, trebuie adăugate alte verificări pentru a evita numeroase variante nevalide și dubluri.

O limită maximă prea mică poate elimina soluții valide. O limită prea mare poate păstra corectitudinea dacă există verificări ulterioare, dar irosește explorări. Formula limitei trebuie justificată prin numărul pozițiilor rămase, nu memorată izolat.

Scrie lângă fiecare parametru ce informație transmite prefixul. Această practică sprijină înțelegerea backtrackingului și face mai ușoară adaptarea distanței minime la alte restricții.

Eficiență și memorie

Algoritmul vizitează prefixele care pot fi completate și afișează toate soluțiile. Numărul lor poate fi mare, iar costul afișării crește și cu lungimea fiecărei soluții. Eliminarea anticipată a ramurilor nu transformă automat generarea într-un algoritm liniar.

Memoria suplimentară este proporțională cu k: vectorul păstrează soluția curentă, iar stiva are cel mult un nivel pentru fiecare poziție. Nu memorăm lista completă a soluțiilor, deoarece fiecare este afișată imediat.

Exerciții cu răspunsuri

n este șase și k este trei. Soluțiile sunt 1 3 5, 1 3 6, 1 4 6, 2 4 6, în această ordine.

n este trei și k este doi. Singura soluție este 1 3.

k este unu. Fiecare valoare de la unu la n formează o soluție. Nu există o pereche de valori alese care să încalce restricția.

Întrebări frecvente

Este necesar un tablou de valori folosite?

Nu aici. Creșterea strictă impusă prin limita inferioară exclude repetarea valorilor și oferă o reprezentare unică a fiecărui grup.

Dacă inversez ordinea candidaților, obțin alte soluții?

Mulțimea soluțiilor rămâne aceeași dacă păstrezi limitele și restricțiile, dar ordinea afișării se schimbă. O cerință despre prima soluție depinde de această ordine.

Cum verific o restricție nouă?

Separă condiția locală de posibilitatea completării și testează cazuri mici enumerate manual. Pentru feedback pe ordinea soluțiilor, poți consulta un profesor de informatică.