A most következo anyag minden bizonnyal az egyik legnehezebb része a félévnek, mégis azt mondom hogy ez az egyik legjobb része. Azt állítom hogyha valaki ezt a részt megérti, akkor nagyon egyszeru dolga lesz, mert csak két dolgot kell módosítani és muködnek is majd a programok.

Persze elotte meg kell érteni, hogy egyáltalán mire használjuk ezt az algoritmust. Nézzünk rá egy példát. Van egy építési vállalkozó. N munkára keres embert. A munkára pontosan n ember jelentkezik. Minden ember más mennyiségu munkát tud ellátni. Egy munkára csak egy ember kaphat állást, és egy ember csak egy munkára jelentkezhet. A feladat annak eldöntése hogy létezik e olyan csoportosítás hogy mindenkinek legyen munkája.

Nézzük meg ennek megoldását lépésrol – lépésre. Tehát vegyük az elso munkás elso munkáját. Eloször is megnézzük, hogy kell egyáltalán az adott meló ha kell akkor ezt válasszuk eloször. Utána a második embert válasszuk. Onála is az elso munkát nézzük. Eloször megnézzük hogy jó e. Ha igen akkor azt is meg kell nézni hogy a korábban kiválasztott ember munkája nem e ugyanez. Ha nem akkor ez lesz a jó választás. Mi történik akkor ha a munka valamiért nem jó (nem kell ilyen munka, korábban már volt), akkor mindig az i. ember következo melóját nézzük. Ha eljutottunk az adott ember utolsó munkájához, akkor a korábbi választások sem voltak jók. Tehát vissza kell ugrani egy embert. Ennek nem jó az adott munkája, tehát a következo munkáját kell választani. Az egész folyamat addig tart, amíg az utolsó embernek is találtunk munkát, vagy amíg az elso emberhez nem tartozik megfelelo meló. (Hiszen ha az elso emberig visszaugrunk, és ott sem lesz jó megoldás, akkor nincs megoldás)

Na nézzük meg milyen adatszerkezetek szerepelnek. Van egy sorozatunk. Ebben tároljuk a munkákat amikre szükségünk van. Van egy másik n elemu sorozat. Ezek a munkára jelentkezo emberek. Mindegyik maga is egy sorozat, mert tároljuk bennük az o munkáikat.

Kell majd egy függvény ami megmondja hogy az i. ember j. munkája kell e egyáltalán (pl.: Pékségbe nem kell informatikus). Ezt hívjuk majd ft függvénynek. Kell egy mási függvény ami azt mondja meg hogyha kell is egy meló, korábbi embernél nem választottuk e ki. Ezt nevezzük majd fk függvénynek. És persze azt is el kell dönteni hogy mi legyen a kimenet. Nos a kimenet legyen egy sorozat, amiben az i. elem helyén azt a számot tároljuk, hogy az i. sorozatból melyik munka kell. Pl.: 112 kimenet azt jelenti hogy az elso embernek az elso munkája, a második embernek elso munkája kell, és a harmadik ember 2. munkája kell.

Akkor deklaráljuk is ezeket:

Típus Tkimenet: tömb[1..Nmax: egész]
      Tsorozat: tömb [1..Nmax: Telem]
      Th&aacu;nytagu: tömb[1..Nmax: egész]

  Ez jelöli, hogy az i. sorozat hány tagú

  .

  Változó x : Tkimenet

  S: Tsorozat

  M. Thanytagu

  

  Eljárás backtrack (x,s,)

  X := 0

  Ciklus amíg i <= n és i>0

  Jóvalasztaskeres (x,i,siker,melyik,s)

  Ha siker akkor 

  X[i] := s[melyik]

  I:=i+1

  Különben

  X[i]:=0

  I:=i-1

  Elágazás vége

Ciklus vége
Van:= (i <= n)
Ha van akkor ki x
Eljárás vége
Ez még csak az algoritmus elso fele. A kimenetünket (x) eloször 
  is kinullázzuk. Az i-vel jelöljük majd azt hogy hányadik 
  sorozatnál járunk. A „melyik” változó 
  fogja jelölni, hogy az i. sorozat, hányadik elemét vizsgáljuk.

  A jóválaztkeresés függvény fogja megmondani 
  az i. sorozatból ki tudunk e választani jó elemet, és 
  ha igen akkor melyik az. 

  Ha ki tudtuk választani (ezt jelöli a siker) akkor ezt beírjuk 
  a kimenetbe, és a következo sorozatra ugrunk. 

  Ha sikerült végigmenni akkor kiíratjuk a végeredményt.
Most akkor nézzük meg a jóválasztkeres függvényt.
Eljárás jóválasztkeres(x, 
  i, siker, melyik, s)
Melyik := X[i]+1

  Ciklus amíg melyik < n és rosszválaszt (i,melyik,x,s)

  Melyik := melyik +1

  Ciklus vége
Siker := (melyik <m[i] )

  Eljárás vége
Ebben az eljárásban kiválasztjuk, hogy az i. sorozat melyik 
  eleme lesz a jó. Amikor a sorozatra ugrunk, akkor már azt az elemet 
  nem kell vizsgálni amin állunk, és az elotte levoket sem. 
  Ezért kezdjük az utána levokkel. Ezt ciklikusan csináljuk. 
  Ehhez még meg kell írni a rosszválaszt függvényt. 
  Ebben fogjuk végrehajtani a tényleges elem vizsgálatot, 
  tehát az i. sorozat, j. elemének vizsgálatát. 
Függvény rosszvalaszt(i,melyik,x,s) 
Ha ft() akkor 

  L:=1

  Ciklus amíg (l < i) és fk(l,x[l],i,melyik)

  L:=l+1

  c.v

  rosszvalaszt := (l <i)
függvény vége
Nos ebben a függvényben eloször is elkérjük az 
  elemrol hogy kell e. Ezt teszi meg az ft függvény. A ciklusban egy 
  l számot 1-re állítunk, majd ezt egyesével növeljük. 
  Ez az l szám azért kell hogy a korábbi sorozatokon végig 
  menjünk. Az fk függvény fogja az l. sorozat x[l] elemét 
  összehasonlítani a vizsgált sorozat melyikedik elemével.
Az ft és fk függvényeket nem írom meg, mert az programonként 
  értelemszeruen más. Azonban azt remélem lehet látni, 
  hogy a backtrack, lehet hogy egy hosszú algoritmus de valójában 
  csak egyszer kell megírni, és onnantól kezdve elég 
  csak az ft és fk függvényeket jól megírni. 
  A példaprogramok letölthetok innen.
A backtrack algoritmushoz itt találtok példát. A példák 
  leírásai még készüloben vannak, hamarosan elérhetoek 
  lesznek.