[es] - pathfinding problem

peromalosutra
Ivan Rajkovic
Banjaluka

Član broj: 54774
Poruke: 390
*.dialup.blic.net.

Jabber: peromalosutra@elitesecurity.org
Sajt: computer-stuff.freehostia..

Profil

pathfinding problem

^{12.07.2006. u 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!

ivan@ivan-desktop:~$ ./encrypt.run
*** stack smashing detected ***: ./encrypt.run terminated
Aborted (core dumped)

^{12.07.2006. u 11:03}

Au197/79
NBGD

Član broj: 3556
Poruke: 619
195.252.90.*

Profil

Re: pathfinding problem

^{12.07.2006. u 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.

Bolje džaba ležat nego džaba radit.

^{12.07.2006. u 11:43}

NrmMyth
Split, Kaštela

Član broj: 63456
Poruke: 839
*.cmu.carnet.hr.

Profil

Re: pathfinding problem

^{12.07.2006. u 14:05}

Moglo bi se i dinamicki, pogledat cu pa se javit.

http://www.last.fm/user/NrmMyth/

^{12.07.2006. u 14:05}

amel
Bosna

Član broj: 9063
Poruke: 41
*.informatik.tu-muenchen.de.

Profil

Re: pathfinding problem

^{14.07.2006. u 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

Scanner

^{14.07.2006. u 08:27}

peromalosutra
Ivan Rajkovic
Banjaluka

Član broj: 54774
Poruke: 390
*.dialup.blic.net.

Jabber: peromalosutra@elitesecurity.org
Sajt: computer-stuff.freehostia..

Profil

Re: pathfinding problem

^{15.07.2006. u 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.

ivan@ivan-desktop:~$ ./encrypt.run
*** stack smashing detected ***: ./encrypt.run terminated
Aborted (core dumped)

^{15.07.2006. u 09:59}

RooTeR
Rajko Nenadov
Detelinara, NS

Član broj: 2386
Poruke: 385
*.ADSL.neobee.net.

Profil

Re: pathfinding problem

^{15.07.2006. u 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)

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

^{15.07.2006. u 16:12}

peromalosutra
Ivan Rajkovic
Banjaluka

Član broj: 54774
Poruke: 390
*.dialup.blic.net.

Jabber: peromalosutra@elitesecurity.org
Sajt: computer-stuff.freehostia..

Profil

Re: pathfinding problem

^{15.07.2006. u 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.

ivan@ivan-desktop:~$ ./encrypt.run
*** stack smashing detected ***: ./encrypt.run terminated
Aborted (core dumped)

^{15.07.2006. u 21:31}

amel
Bosna

Član broj: 9063
Poruke: 41
*.dip.t-dialin.net.

Profil

Re: pathfinding problem

^{21.07.2006. u 21:04}

Bas sam naisao na ovo

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

interesantno rijesenje
za ovaj problem

Scanner

^{21.07.2006. u 21:04}