algoritmul backtracking enumeră un set de candidați parțiali care, în principiu, ar putea fi finalizați în diferite moduri pentru a oferi toate soluțiile posibile la problema dată. Finalizarea se face incremental, printr-o secvență de pași de extindere a candidatului.
conceptual, candidații parțiali sunt reprezentați ca noduri ale unei structuri arborescente, arborele potențial de căutare. Fiecare candidat parțial este părintele candidaților care diferă de acesta printr-o singură etapă de extindere; frunzele copacului sunt candidații parțiali care nu pot fi prelungiți mai departe.
algoritmul de backtracking traversează acest arbore de căutare recursiv, de la rădăcină în jos, în profunzime-primul ordin. La fiecare nod c, algoritmul verifică dacă c poate fi completat la o soluție validă. Dacă nu poate, întregul sub-copac înrădăcinat la c este omis (tăiat). În caz contrar, algoritmul (1) verifică dacă C în sine este o soluție validă și, dacă da, o raportează utilizatorului; și (2) enumeră recursiv toți subarborii lui c. cele două teste și copiii fiecărui nod sunt definiți prin proceduri date de utilizator.
prin urmare, arborele de căutare real care este traversat de algoritm este doar o parte a arborelui potențial. Costul total al algoritmului este numărul de noduri ale arborelui real ori costul obținerii și procesării fiecărui nod. Acest fapt trebuie luat în considerare atunci când alegeți arborele potențial de căutare și implementați testul de tăiere.
PseudocodeEdit
pentru a aplica backtracking la o anumită clasă de probleme, trebuie să furnizați datele P pentru instanța particulară a problemei care trebuie rezolvată și șase parametri procedurali, root, reject, accept, first, next și output. Aceste proceduri ar trebui să ia datele instanței P ca parametru și ar trebui să facă următoarele:
- rădăcină (p): returnați candidatul parțial la rădăcina arborelui de căutare.
- reject(P,c): returnează true numai dacă candidatul parțial c nu merită completat.
- accept (P, c): returnați true dacă c este o soluție de P și false altfel.
- first(P,c): generați prima extensie a candidatului c.
- next(P,s): generați următoarea extensie alternativă a unui candidat, după extensia s.
- output(P,c): utilizați soluția c A Lui P, după caz, pentru aplicație.
algoritmul backtracking reduce problema la apelul backtrack(root (P)), unde backtrack este următoarea procedură recursivă:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
considerații de Utilizareedit
procedura de respingere ar trebui să fie o funcție cu valoare booleană care returnează true numai dacă este sigur că nicio extensie posibilă A c nu este o soluție validă pentru P. dacă procedura nu poate ajunge la o concluzie definitivă, ar trebui să returneze false. Un rezultat adevărat incorect poate determina procedura bt să rateze unele soluții valide. Procedura poate presupune că respingerea (P,t) a revenit Fals pentru fiecare strămoș t al c din arborele de căutare.
pe de altă parte, eficiența algoritmului de backtracking depinde de respingerea returnării true pentru candidații care sunt cât mai aproape de rădăcină posibil. Dacă reject returnează întotdeauna false, algoritmul va găsi în continuare toate soluțiile, dar va fi echivalent cu o căutare cu forță brută.
procedura de acceptare ar trebui să returneze true dacă c este o soluție completă și validă pentru instanța de problemă P și false altfel. Se poate presupune că candidatul parțial c și toți strămoșii săi din copac au trecut testul de respingere.
pseudo-codul general de mai sus nu presupune că soluțiile valide sunt întotdeauna frunze ale arborelui potențial de căutare. Cu alte cuvinte, admite posibilitatea ca o soluție validă pentru P să poată fi extinsă în continuare pentru a produce alte soluții valide.
prima și următoarea procedură sunt utilizate de algoritmul de backtracking pentru a enumera copiii unui nod c al arborelui, adică candidații care diferă de c printr-un singur pas de extensie. Primul apel (P, c)ar trebui să producă primul copil al lui c, într-o anumită ordine; și apelul următor (P,s) ar trebui să returneze următorul frate al nodului s, în această ordine. Ambele funcții ar trebui să returneze un candidat distinctiv „nul”, dacă copilul solicitat nu există.
împreună, funcțiile root, first și next definesc setul de candidați parțiali și arborele potențial de căutare. Acestea ar trebui alese astfel încât fiecare soluție de P să apară undeva în copac și niciun candidat parțial să nu apară de mai multe ori. Mai mult, ar trebui să admită un predicat de respingere eficient și eficient.
early stopping variantsEdit
pseudo-codul de mai sus va apela ieșire pentru toți candidații care sunt o soluție la instanța dată P. algoritmul poate fi modificat pentru a opri după găsirea primei soluții, sau un număr specificat de soluții; sau după testarea unui număr specificat de candidați parțiale, sau după ce a petrecut o anumită cantitate de timp CPU.