Backtracking - Permutări în Pascal

1. Algoritm

Algoritmul pentru determinarea permutărilor reprezintă unul dintre cele mai ușoare metode de prezentare ale backtracking-ului.

2. Executare

3. Discuție

Algoritmul de backtracking este cel de sus, din ultimul ecran luat din Borland Pascal. Ce merită discutat sunt funcțiile și procedurile sale.

Mai întâi un algoritm de backtracking se bazează pe 3 variabile: stiva, un index pentru nivelul curent al stivei (aici e folosită variabila k) și, în acest caz, un nivel maxim de elemente (dat de variabila n).

Doar atât.

Să luăm metodele pe rând:

1. inițializarea. Aici sub numele de init, atribuie nivelului curent o valoare care, trecută prin funcția de determinare a succesorului, ne dă o valoare validă. Fiindcă mulțimea permutărilor o începem cu elementul 1, această valoare de inițializare va fi 0. De ce? Vedem la funcția succesor.
2. succesorul, aici sub numele next, are rolul de a determina următoarea valoare corectă a nivelului curent al stivei și de a ne spune dacă e valid sau nu. În cazul nostru dacă valoarea e mai mare decât n atunci clar nu este un succesor valid. Succesorul se află ușor, pur și simplu incrementând valoarea curentă cu 1. Sau folosind funcția predefinită inc din Pascal.
3. valid, funcție cu acelaș nume, ne spune dacă mulțimea pe care o avem este validă. În acest caz, ea trebuind să aibă elemente distincte. Astfel se ia ultima valoare și se compară cu restul valorile din stivă. Dacă ea mai există, evident nu va fi validă.
4. soluție. În această funcție determinăm dacă mulțimea este o soluție pentru problemă. Iar pentru această problemă, condiția ca o mulțime să fie soluție, este ca ea să aibă n elemente.
5. tipărire. Dată de procedura print, ea pur și simplu tipărește conținutul stivei.

Algoritmul va trece prin toate combinațiile:

1. {1}
2. {1, 1}
3. {1, 1, 1}
4. {1, 1, 2}
5. {1, 1, 3}
6. {1, 2}
7. {1, 2, 1}
8. {1, 2, 2}
9. {1, 2, 3}
10. {1, 3}
11. {1, 3, 1}
12. {1, 3, 2}
13. {1, 3, 3}
14. {2}
15. {2, 1}
16. {2, 1, 1}
17. {2, 1, 2}
18. {2, 1, 3}
19. ...
20. ...
21. ...
22. {3, 3, 3}

ca apoi nivelul stivei să devină 0, astfel știind că am epuizat toate variantele.

După cum am afirmat, algoritmul de backtracking este încet fiindcă trece prin absolut toate variantele posibile. Din mulții pași exemplificați mai sus, abia 3 fiind soluții pentru problemă.