Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

pathfinding problem

[es] :: Art of Programming :: pathfinding problem

[ Pregleda: 3815 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

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



+148 Profil

icon pathfinding problem12.07.2006. u 11:03 - pre 215 meseci
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!


 
Odgovor na temu

Au197/79
Zlatan Kadragić
Minhen

Član broj: 3556
Poruke: 772
195.252.90.*

Sajt: aurelije.blogspot.com


+47 Profil

icon Re: pathfinding problem12.07.2006. u 11:43 - pre 215 meseci
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.
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

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

Sajt: www.dump.hr


Profil

icon Re: pathfinding problem12.07.2006. u 14:05 - pre 215 meseci
Moglo bi se i dinamicki, pogledat cu pa se javit.
 
Odgovor na temu

amel
Bosna

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



Profil

icon Re: pathfinding problem14.07.2006. u 08:27 - pre 215 meseci
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
 
Odgovor na temu

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

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



+148 Profil

icon Re: pathfinding problem15.07.2006. u 09:59 - pre 215 meseci
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.

 
Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

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



Profil

icon Re: pathfinding problem15.07.2006. u 16:12 - pre 215 meseci
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!
 
Odgovor na temu

peromalosutra
Ivan Rajkovic
Software engineer
Luxoft
Berlin

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



+148 Profil

icon Re: pathfinding problem15.07.2006. u 21:31 - pre 215 meseci
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.

 
Odgovor na temu

amel
Bosna

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



Profil

icon Re: pathfinding problem21.07.2006. u 21:04 - pre 215 meseci
Bas sam naisao na ovo

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

interesantno rijesenje
za ovaj problem
Scanner
 
Odgovor na temu

[es] :: Art of Programming :: pathfinding problem

[ Pregleda: 3815 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.