Algoritmi/"Bektreking"

Bektreking je opšta tehnika u algoritmima koja dovodi u obzir sve moguće kombinacije kako bi rešila problem optimizacije. Bektreking je takođe poznat po nazivu prvo-u-dubinu ili separacija i evaluacija. Imajući više znanja o problemu, binarno stablo pretrage može biti uprošćeno, kako bi se zaobišli slučajevi koji ne izgledaju obećavajuće. Dok je bektreking koristan za teške probleme, za koje ne zahtevamo efikasnija rešenja, ono je loše rešenje za svakodnevne probleme koje druge tehnike mnogo bolje rešavaju. Međutim, dinamičko programiranje i pohlepi algoritmi se mogu posmatrati kao optimizacija kod bektrekinga, tako da opšta tehnika bektrekinga je korisna za razumevanje ovih naprednijih koncepata. Učenje i razumevanje bektreking tehnike pre svega daje dobar "prvi korak unapred" do tih naprednijih tehnika, jer onda ne morate da učite svih par novih koncepata odjednom.

Metod bektreking Sagledati uzimanje rešenja kao sekvencu izbora Za svaki izbor, sagledati svaku opciju rekurzivno Vratiti najbolje pronađeno rešenje

Ova metodologija je dovoljno generička da se može primeniti u većini problema. Međutim, čak i da hoćemo da unapredimo bektreking algoritam, idalje bi se izvršavao u eksponencialnom vremenu pre nego u polinoialnom vremenu. Uz to, analiziranje tačnog vremena bektreking algoritma može biti jako komplikovano: umesto toga, date su jednostavnije gornje granice koje nisu čvrste.

Najduža zajednička podsekvenca (iscrpna verzija)

Primetiti da je rešenje problema najduže zajedničke podsekvence (NZP) nije dovoljno efikasan. Međutim, korisno je za razumevanje dinamičkog programiranja. NZP problem je sličan onom koji Unix "diff" program radi. Diff komanda u Unix-u uzima dva tekstualna fajla A i B, kao ulaz i izlazi razlikuju liniju po liniju od A i B. Na primer, diff može pokazati da linije koje nedostaju iz fajla A treba dodati u fajl B i linije prikazane u fajlu A treba obrisati iz fajla B. Cilj je dobiti listu dodavanja i brisanja koja bi se mogla iskoristiti kako bismo transformisali fajl A u fajl B. Previše konzervativno rešenje ovog problema bi bilo da se sve linije iz fajla A obrišu i da se sve linije iz fajla B dodaju. Dok ovo rešava problem na sirov način, nas zanima minimalan broj dodavanja i brisanja kako bismo uspešno dostigli transformaciju. Sami razmislite kako biste implementirali rešenje ovog problema.

NZP problem, umesto što deli linije u tekstualnim fajlovima,se smatra i da pronalazi zajedničke elemente između dva različita niza. Na primer,

let a := array {"The", "great", "square", "has", "no", "corners"}
let b := array {"The", "great", "image", "has", "no", "form"}

Želimo da nađemo najdužu podsekvencu moguću od elemenata koje su pronašli i u nizu a i u nizu b u istom redosledu. NZP od a i b je

"The", "great", "has", "no"

Sada posmatrajmo dve nove sekvence:

let c := array {1, 2, 4, 8, 16, 32}
let d := array {1, 2, 3, 32, 8}

Ovde postoje dve najduže zajedničke podsekvence niza c i niza d:

1, 2, 32; and

1, 2, 8

Primetiti da:

1, 2, 32, 8

nije zajednička podsekvenca, jer je validna podsekvenca samo niza d, a ne niza c (jer c ima 8 pre 32). Tako možemo da zaključimo da za neke slučajeve, rešenja NZP problema nisu jedinstvena. Ako bismo imali više informacija o dostupnim sekvencama, više bismo voleli jednu podsekvencu u odnosu na drugu: na primer, ako su sekvence linije tekstova u računarskom programu, možda bismo izabrali podsekvencu koja bi zadržala definiciju funkcije.

Na gornjem nivou, naš problem je implementirati sledeću funkcju:

// lcs -- враћа најдужу заједничку подсеквенцу од a и b
function lcs(array a, array b): array

koja uzima dva niza kao ulaz i podsekvence niza kao izlaz.

Kako rešavate ovaj problem? Možete početi od toga da primetite da li dve sekvence počinju istom rečju, onda najduža zajednička podsekvenca uvek sarži tu reč. Automatski možete da stavite tu reč u listu i tako biste skratili problem nalaženja najduže zajedničke podsekvence ostatka dveju listi. Tako je problem postao manji, što je dobro, jer pokazuje da postoji neki napredak.

Ali ako dve liste ne počinju istom rečju, onda jedna, ili obe od prvog elementa iz niza ili prvog elemementa iz niza ne pripadaju najdužoj zajedničkoj podsekvenci. Ali ipak, jedan od njih može biti. Kako određujete koji ćete, ako neki jeste, da dodate?

Rešenje možete posmatrati u dva smisla bektreking metode: Probajte ova načina i vidite! Svakako, dva podproblema su manipulisanje manjim listama, kako biste znali da će se rekurzija kad tad završiti. Čiji god je rezultat procesa najduža zajednička podsekvenca je pobednik. Umesto što biste "izbacili" element brisanjem iz niza, koristite parče niza. Na primer, parče:

a[1,..,5]

predstavlja elemente:

{a[1], a[2], a[3], a[4], a[5]}

niza kao posebnog niza. Ako Vaš programski jezik ne podržava parčiće, onda morate da prođete početak i/ili kraj indeksa kroz ceo niz. Ovde su parčići jedino u formi:

a[1,..]

koja kada koristite 0 kao indeks prvog elementa u nizu, rezultira da u nizu parčića ne postoji nulti element. (Tako, verzija ovog algoritma koja nema parčiće mora proći početak validnog indeksa i vrednost bi trebalo biti oduzeta od cele dužine niza kako biste dobili dužinu pseudo-parčadi.)

// lcs -- враћа најдужу заједничку подсеквенцу од a и b
function lcs(array a, array b): array
  if a.length == 0 OR b.length == 0:
    // ако смо на крају било било које листе, онда је lcs празан
    
    return new array {}
  else-if a[0] == b[0]:
    // ако је почетни елемент исти у оба низа, онда је на lcs,
    // тако да само рекурзивно вратимо остатке обе листе.
    
    return append(new array {a[0]}, lcs(a[1,..], b[1,..]))
  else
    // не знамо која листу треба да одбацимо. Пробајте оба начина,
    // изаберите онај који је бољи.
    
    let discard_a := lcs(a[1,..], b)
    let discard_b := lcs(a, b[1,..])
    
    if discard_a.length > discard_b.length:
      let result := discard_a
    else
      let result := discard_b
    fi
    return result
  fi
end

Problem najkraćeg puta

Da se poboljša Dajkstrin algoritam u sledećem poglavlju.

Granično pretraživanje

Ako ste već našli nešto "bolje" i da ako ste na grani koja nikada neće biti dobra kao ona koju ste već videli, možete prekinuti ranije tu granu. (Primer za korišćenje: zbir brojeva počevši od 1 2, a zatim svaki broj koji sledi je zbir bilo kojeg broja plus proslednji broj. Pokažite poboljšanja performansi..)

Ograničeno 3-bojenje

Ovaj problem ne liči neposredno na samog sebe, tako da mora prbo biti uopšten. Metodologija: Ako problem ne liči na samog sebe, pokušajte da ga uopštite dok ne počne da liči.

Problem trgovačkog putnika

Ovde je bektreking tehnika najbolje moguće rešenje.