Sestopanje

Iz MaFiRaWiki

Sestopanje ali vračanje (backtracking) je pristop v programiranju, kjer sistematično pregledujemo vse možnosti rešitve. Sestopanje lahko ponazorimo z drevesom stanj, kjer rešitev najdemo v listih drevesa ali pa je rešitev pot od korena do lista.

Slika:Sestopanje.png

Ko neka pot od korena do lista ni več obetavna, se vrnemo nazaj in poskusimo po drugi poti.

Vsebina

Postopek

  • na i -tem koraku naj bo Si množica možnih odločitev
  • iščemo rešitev x = (x1,x2,...,xn), pri čemer je xi \isin Si odločitev na i -tem koraku
  • če na i -tem koraku ni več dopustnih odločitev, se vrnemo korak nazaj in izberemo drug xi − 1.

Slika:Sestopanje1.png

Časovna zahtevnost

V najslabšem primeru moramo pri sestopanju pregledati celotno drevo. Smiselno je zato čim prej zavreči vse poti, ki ne morejo pripeljati do rešitve. Ko zavržemo kakšno odločitev, zavržemo celotno poddrevo te odločitve in si tako krajšamo pregledovanje. Hitrost pregledovanja je torej odvisna od tega, koliko poti v drevesu zavržemo na račun pogojev. Sestopanje v splošnem ne vrne rešitve v polinomskem času.

Algoritem

Primer zapisa z rekuzijo v javi:

  1. public void sestopiR(n, S, k, x, resitev) {
  2. // n globina drevesa
  3. // S množica odločitev, S[k] možne odločitve na k-tem koraku
  4. // k trenutni korak
  5. // x vektor, ki vsebuje naše dosedanje odločitve
  6. // x[0] je odločitev na prvem koraku,
  7. // x[1] na drugem...
  8. // rešitev je množica rešitev
  9. for (i = 0; i < S[k].length; i++) {
  10. x = S[k][i]; // i-ti element množice S[k]
  11. if lahkoVodiKCilju(k, x) { // tole moramo znati sprogramirati
  12. // odvisno od problema
  13. if (k == n) { // list
  14. resitev.dodajNovoResitev(x); // x je množica odlocitev;
  15. // ker smo v listu, smo nasli
  16. // novo rešitev in jo dodamo
  17. } // obstoječi množici rešitev
  18. else {
  19. // gremo na naslednji nivo z odločitvijo x[i] = S[k][i]
  20. // na k-tem nivoju
  21. sestopiR(n, S, k + 1, x, resitev);
  22. }
  23. }
  24. }
  25. } // sestopiR


Primeri uporabe

Osebna orodja