[ peromalosutra @ 12.07.2006. 11:03 ] @
Mozete li me uputiti na algoritam koji bi moga iskorsititi za rjesavanje sledeceg tipa zadataka:

Citat:

U matrici (n*m) svako polje ima odredjenu vrijednost (v). Naci putanju izmedju 2 tacke u matrici
tako da je zbir vrijednosti svih polja na toj putanji najmanji.


Ocigledno ovdje ne pomaze greedy algoritam, ali mozda u nekoj kombinaciji sa rekurzijom?
... mada me ovo sve podsjeca na a-star algoritam.

Hvala!
[ Au197/79 @ 12.07.2006. 11:43 ] @
Dijkstra za puteve, ako hoćeš najkraći put između svakog čvora onda je to ili višestruki dijkstra ili flojdov algoritam. Imaš objašnjenje na http://www.laboi.fon.bg.ac.yu/...Predmeti%2FMetOpt%2FLiteratura Odaberi lokacijske probleme ili probleme na mrežama, nisam siguran u kojem delu je algoritam.
[ NrmMyth @ 12.07.2006. 14:05 ] @
Moglo bi se i dinamicki, pogledat cu pa se javit.
[ amel @ 14.07.2006. 08:27 ] @
Dijkstra Algoritam ti je najbolji.

A mozda bi moglo i ovako

definisi matricu a[m][n], tacke v i v' gdje su v pocetna tacka i v' krajnja tacka
E sad postoji problem kako se kretati.
Jednostavno mozes rijesiti sa definiranim funkcijama kretanja (naravno koje ces isto napraviti):
idi_gore : a[m-1][n]
idi_ldole: a[m+1][n]
idi_lijevo: a[m][n-1]
idi_desno: a[m][n+1]

Takodje postoji problem dali kreces odozdo prema gore, ili odozgo prema dole (dijagonala)
to ces uraditi ovako:
Napravi funkciju koja trazi tacku v (njihova kordinata a[j]) i tacku v' a[i'][j']. Uporedjivanjem tih tacaka mozes skontati u kojem se pravcu kreces.
i < i' znaci da ides dole
i > i' ides prema gore
itd.

Evo primjer kako bi to moglo da izgleda


3 x 3

1 5 6
7 4 9
3 2 8

trazimo rastojanje izvedju
v = 1 i v'= 9
Pronadjemo kordinate tacke v i kordinate v'
Provjeri kojim pravcem

onda slijedi:

pocetak: a[j]
x: = idi_dole
y: = idi_desno
if (a[j] + x) > (a[j] + y)
pocetak := x
i tako dok ne dodjes do tacke koju si trazio/la

u ovom slucaju najkraci put ti je
5+4 = 9

To je sve grubo objasnjeno
Uradit cu to u javi ili c
pa cu loadat ovdje

Trenutno nemam vremena
pocele su mi vjezbe prije 10 minuta






[ peromalosutra @ 15.07.2006. 09:59 ] @
Hvala na odgovorima, ja sam malo razmisljao i dosao do sledeceg algoritma:
Dok ne postoji put sastavljen od nula izmadju dve tacke, svaki clan matrice razlicit od nule umanji za 1. Nakon toga jednostavno flood fill-om nadjemo put izmedju dve tacke. dakle pseudo kod ide nekako ovako:

Code:

while (!spojen(A,B))
{
   for (int i=0; i<m; i++)
      for (int j=0; j<n; j++)
          if (mat[i][j]!=0)
             mat[i][j]--;
}

Gdje funkcija spojen vraca 1 ako postoji put sastavljen od nula izmedju tacke A i B, u suprotnom 0. Nakon ovogo samo opisemo taj put (tu koristimo flood fill algoritam). Nisam jos otkucao kod ali ovo garantovano radi.

Ovo mozemo zamisliti na sledeci nacin:
Ako zamislimo da se iz svakog polja matrice izdize stub visine koja odgovara vrijednosti tog polja i onda takav "model" polako potapamo u vodu, prvi kanal koji se na taj nacin stvori izmedju nase dve tacke predstavlja trazeni put.
[ RooTeR @ 15.07.2006. 16:12 ] @
Tvoj algoritam je netachan.
Evo ti primer :

matrica izgleda ovako :
1 10 1
5 5 5

i trazi se minimalno rastojanje od polja (1,1) do polja (1,3). Tvoj algoritam bi izabrao
put 1 - 5 - 5 - 5 - 1, dok je optimalan put 1 - 10 - 1 ...

tako da mislim da je dijkstra najbolje reshenje ( + ima manju vremensku slozenost od tvog algoritma)
[ peromalosutra @ 15.07.2006. 21:31 ] @
RooTeR
Citat:
Tvoj algoritam je netachan.

Da, nazalost u pravu si. Bas sam se i konektovao izmedju ostalog i da postujem da algoritam nije dobar. Sa njim bi jedino mogli naci put sa najmanjim maksimumom, tj. put ciji je najveci clan manji od najveceg clana bilo kog drugog puta, ali to se ovdje ne trazi.

Nista, onda dijkstra, hvala svima na odgovorima.
[ amel @ 21.07.2006. 21:04 ] @
Bas sam naisao na ovo

http://ranger.uta.edu/~cook/aa/lectures/applets/lcs/lcs.html

interesantno rijesenje
za ovaj problem