Tema
Boje
Pismo
Registracija

Novo

Forum kao aplikacija na telefonu

Dodajte forum na početni ekran i koristite ga kao aplikaciju, sa menijem na dnu ekrana.

Kako se dodaje

pathfinding problem

Odgovori Nova tema
Štampanje RSS teme Kopiraj vezu do teme Podeli na Facebook-u Podeli na X-u (Twitter) Idi na poslednju poruku
  • 7 odgovora
  • 5.276 pregleda

Najnovija ↓

pathfinding problem 12.07.2006. u 12:03 · pre 247 meseci #1
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!
Re: pathfinding problem 12.07.2006. u 12:43 · pre 247 meseci #2
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.
Potpis
Bolje džaba ležat nego džaba radit.
Re: pathfinding problem 14.07.2006. u 09:27 · pre 247 meseci #4
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






Potpis
Scanner
Re: pathfinding problem 15.07.2006. u 10:59 · pre 247 meseci #5
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.
Re: pathfinding problem 15.07.2006. u 17:12 · pre 247 meseci #6
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)
Potpis
mmmmmm.. aahhhhhh..
e, nije sex nego serem!
Re: pathfinding problem 15.07.2006. u 22:31 · pre 247 meseci #7
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.
Odgovori
Prijavite se da biste odgovorili u ovoj temi.PrijavaRegistracija

Premeštanje teme