Technikák összehasonlítása I.
Backtraking / Divide et impera
Feladatok:
1. Adott egy labirintus, melyet egy a[1..n][1..m] bináris mátrixxal  (1-fal, 0-szabad )modellezünk, valamint adottak egy egér (xe, ye) és egy darab sajt (xs, ys) koordinátái ebben a mátrixban. Feltételezve, hogy a feladatnak mindig van megoldása, írjunk programot, mely meghatározza az egértől a sajthoz vezető legrövidebb utat , tudva azt, hogy a labirintusban négy irányba ( fel, le, jobbra, balra ) lehet közlekedni.

Backtracking kód: kigeneráljuk az összes hurokmentes utat, amely az egértől a sajthoz vezet, majd kiválasztjuk közülük a legrövidebbet.

back_egér(x,y,k)
  út[k].x = x
  út[k].y = y
  ha x == xs és y == ys akkor     // a sajthoz érkeztünk
    ha k < kmin akkor             // rövidebb utat találtunk, mint az eddigi legjobb
      kmin = k
      minden i = 1, k végezd
        útmin[i] = út[i]
      vége minden
    vége ha
  különben
    a[x][y] = 1                  // a hurkok elkerülése végett
    ha a[x-1][y] == 0 akkor back_egér(x-1,y,k+1)
    vége ha
    ha a[x][y+1] == 0 akkor back_egér(x,y+1,k+1)
    vége ha
    ha a[x+1][y] == 0 akkor back_egér(x+1,y,k+1)
    vége ha
    ha a[x][y-1] == 0 akkor back_egér(x,y-1,k+1)
    vége ha
    a[x][y] = 0                   // visszalépés előtt visszaállítjuk a szabad utat
  vége ha
vége back_egér

Divide et impera kód: Az egértől a sajthoz vezető legrövidebb út meghatározása visszavezethető az egérrel szomszédos szabad pozíciókból induló – sajthoz vezető – leg­rö­videbb utak megtalálására. Miután ezek rendelkezésre állnak, a legrövidebbhez hozzá­adva egyet meg is van a keresett út hossza.

divide_egér (x, y)
  ha x == xs és y == ys akkor
    return 0                          // a sajthoz érkeztünk
  vége ha
  h[1] = h[2] = h[3] = h[4] = n*m
  a[x][y] = 1                         // a hurkok elkerülése végett
  ha a[x-1][y] == 0 akkor h[1]=divide_egér(x-1,y)
  vége ha
  ha a[x][y+1] == 0 akkor h[2]=divide_egér(x,y+1)
  vége ha
  ha a[x+1][y] == 0 akkor h[3]=divide_egér(x+1,y)
  vége ha
  ha a[x][y-1] == 0 akkor h[4]=divide_egér(x,y-1)
  vége ha
  a[x][y] = 0                         // visszalépés előtt visszaállítjuk a szabad utat
  min_irány = minimum(h)              // eltároljuk az addigi legkisebb irányt,
  ha h[min_irány] < n*m akkor
    irány[x][y] = min_irány
  különben
    irány[x][y] = -1                  // zsákutcába értünk
  vége ha
  return h[min_irány] +1
vége divide_egér

minimum ( h[])
    mini = 0
    minden i = 1,4 vegezd
        ha (h[i] < h[mini]) mini = i;
    return mini;
vege minimum