Srodne teme
Kliknite za generisanje liste srodnih tema...
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Lavirinti

[es] :: Art of Programming :: Lavirinti

[ Pregleda: 6571 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

PeraT

Član broj: 3403
Poruke: 43
*.ptt.yu



Profil

icon Lavirinti17.04.2002. u 04:33 - pre 239 meseci
Dal se jos neko ovde slucajno bakce sa lavirintima?
Ako da jel neko ima slucajno ideju kako odredjivati najkraci put
u lavirintu "ne fiksirane" dimenzije i "ne fiksiranog" formata tako
da se f-ja pronadjinajkraciput() ponasa kao O(duzinaputa)
Vazno!!!! dimenzija i format lavirinta nisu fiksirani tj mogu biti i 25 i 25000
inace:kod lavirinta 25x25 dimenzija je 2 a format 25
 
Odgovor na temu

PeraT

Član broj: 3403
Poruke: 43
*.ptt.yu



Profil

icon Re: Lavirinti17.04.2002. u 04:35 - pre 239 meseci
Ah da kao sto ste primetili nemam ideju ni kako da predstavim lavirint
Mozda kao n-arno drvo???
 
Odgovor na temu

01011011
Avanade
CHICAGO, USA

Član broj: 561
Poruke: 2341
*.proxy.aol.com

ICQ: 45747235
Sajt: www.snailtrail.net


+2 Profil

icon Re: Lavirinti17.04.2002. u 09:19 - pre 239 meseci
Zavisi na sta mislis, npr, ja sam za jedan cas morao da napisem program po slici. Profesor nam je dao sliku lavirinta i sir na jednoj strani i Mis na drugoj strani. Sve je zivo bilo If else...

SA DECISION MAKING tehnikom. Znaci ides uglavnom sa bool true false, ukoliko je true ides dalje, ukoliko je false pokusavas nesto drugo itd.
 
Odgovor na temu

PeraT

Član broj: 3403
Poruke: 43
*.ptt.yu



Profil

icon Re: Lavirinti17.04.2002. u 22:39 - pre 239 meseci
Problem nije u algoritmu za matricu vec kako tako nesto primeniti na
n-arno drvo!-ako tako predstavimo bazu. -n nije fiksirano
Tj malo mi je trulo da kada pristupam svakom elementu (da bi proverio jel
bool ili false) moram da izgubim dobro vreme na odredjivanje mesta u drvcetu
gde se nalazi (prolasku kroz drvo)
Opet ako bazu predstavim kao dzinovski niz, pa elementu (i,j) npr pristupam sa
imeniza[format*i+j]-ovako nesto, ima gomila sabiranja mnozenja ...
Znaci hocu da napravis neki model lavirinta u kojem mozes svakom elementu
pristupiti u "relativno kratkom vremenskom intervalu!"
Usput jel znas algoritam za racunanje najkraceg puta u matrici koji je u najgorem slucaju ~O(n)?

Nego sta je to Decision making?
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.221.EUnet.yu



+3 Profil

icon Re: Lavirinti18.04.2002. u 16:44 - pre 239 meseci

a sto se patis sa n-arnim drvetom?!? zasto jednostavno ne pamtis sve to kao
int **p ? tako nisi ogranicen na dimenzije i uvek mozes da alociras dodatnu memoriju a elemtnima pristupas trenutno. a za najkraci put nema sanse da nadjes algoritam koji ce ti biti O(n) nego moze samo O(n^2) sto si i lepo napisao u prvom tvom postu jer je duzina puta O(n^2)
 
Odgovor na temu

PeraT

Član broj: 3403
Poruke: 43
*.ptt.yu



Profil

icon Re: Lavirinti18.04.2002. u 22:01 - pre 239 meseci
Jes' ako pricamo o matrici (lavirint dimenzije 2) ali ako posmatramo
lavirint dimenzije 3, 4, 5, ... ?-sto je i bilo pitanje
Ponavljam pod formatom ne podrazumevam isto sto i pod dimenzijom!
lavirint 10x10 je formata 10x10 ali dimenzije 2
tako da sa bool ** mogu maksimalno da napravim 2-d lavirint (mada jes
neogranicenog formata)
 
Odgovor na temu

amidar

Član broj: 648
Poruke: 68
*.ptt.yu



Profil

icon Re: Lavirinti19.04.2002. u 01:42 - pre 239 meseci
Elem,
imash li ti mozhda neki source za generisanje lavirinta "ne fiksirane" dimenzije i "ne fiksiranog" formata i to takvog da u njemu nema zatvorenih polja/sektora ? Ili makar fiksiranih dimenzija i to 2 i 3.

Pozdrav
 
Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.132.EUnet.yu



+3 Profil

icon Re: Lavirinti19.04.2002. u 01:45 - pre 239 meseci

ok. onda definisi samo bool *p i alociraj memoriju n^d i pristupaj nizu preko formula.
recimo lavirint ti je formata 10*10*10 (n=10) i hoces da pristupis elemntu (2,4,6) pristupis elemtnu p+2*n^2+4^n+6. sta mislis o tome?
algoritam ce ti resavati sa vremenom O(n^(d+1)) gde ti je n format a d dimenzija.
bio sam se zeznuo u prethodnom postu. ako ti je recimo dimeznija lavirinta 2 a format 100*100 onda ce ti algoritam biti O(100^3)

 
Odgovor na temu

prompt
Student matematičkog fakulteta
Univerziteta u Beogradu
Beograd

Član broj: 11814
Poruke: 9
*.rcub.bg.ac.yu

ICQ: 49488234


Profil

icon Re: Lavirinti03.07.2003. u 12:47 - pre 224 meseci
Izgleda da ćeš morati da se odlučiš za varijantu "manje zlo" koja god to bila. Pretpostavljam da si ti tražio neko do sada već formulisano rešenje za taj n-dimenzioni lavirint, ali sa tom uopštenošću ne verujem da možeš da pobegneš iz okvira o kome ste diskutiovali ti i srki, dakle stablo ili 1-dimenzioni niz koji čuva sve dimenzije pa preko formula... vidi šta ima manje operacija.

Takođe, kasnije u razvoju ćeš imati situacije da se neke stvari lakše realizuju preko niza a druge preko stabla. Moje mišljenje je da je stablo nekako "finije" rešenje ali nisam siguran da i sam ne bi uradio to sa nizom kad bih počeo da se zapetljavam sa stablom :)

Za pretragu probaj (ako već nisi) BackTrace algoritam, ja ga ne znam napamet, ako ne grešim radi se o rekurzivnim prolazima kroz lavirint i merenjem SVIH mogućnosti da stigneš do sira (objekta) pa odabiranjem najmanje vrednosti. Mislim da tu ne postoji nikakva fora i da je to jedini način da budeš siguran da si našao baš najkraći put. Stabla su izvanredna za rekurzije...

Mislim da ne moraš toliko da se trudiš oko efikasnosti (opet, svakako da je ne zanemariš) obzirom da takve stvari služe samo za teoretsku ili eksperimentalnu svrhu, nemaju primenu - osim ako ne nameravaš da napraviš n-dimenzioni Tetris ili Pacmen :))
 
Odgovor na temu

BATE

Član broj: 4159
Poruke: 24
195.66.182.*



Profil

icon Re: Lavirinti03.07.2003. u 13:24 - pre 224 meseci
jednom sam naiso na takav problem, razbijao glavu i rjesio ga NEVJEROVATNO jednostavno. Prvo napravis matricu
Code:
int mat[sirina][duzina]
... moze i dinamicki ako je takav zahtjev
Code:
int *mat =new(sirina, duzina);
. Pitas zasto int... e pa bice ti jasno. Na toj matrici polja oznacis sa vrjednoscu 0 sve prepreke ili zidove. Sa vrjednoscu 1 oznacis tacku gdje treba da stignes, a sa vrjednoscu 32000 (ili vecom ako ti je polje bas ogromno) mjesto gdje treba da dodjes. Sada pocni da prelazis matricu kroz neku petlju oznacavajuci svako polje koje se nalazi lijevo, desno, gore, dolje od broja 1 sa brojem 2 a da nije 0 ili 32000... onda sa broja 2 na broj 3 itd (ne znam da li si skontao ovo do sada). Onda kada dodjes do toga da se ovaj broj koji se povecava u tvojoj petlji (1,2,3,4...) dosao do sudara sa poljem 32000 ili mjestom odakle si krenuo onda jednostavno prati polja sa manjim brojem i doci ces do cilja. Ovo je moje autorsko djelo al evo bio sam ljubazan da vam odam algoritam, uzivajte :)
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.dial.InfoSky.Net

Sajt: localhost


+4 Profil

icon Re: Lavirinti04.07.2003. u 04:38 - pre 224 meseci
hm.. možda je to tvoje autorsko delo, ali to je već decenijama star algoritam poznat pod imenom BFS (Breadth First Search).

google: breadth+first+search+algorithm

 
Odgovor na temu

BATE

Član broj: 4159
Poruke: 24
195.66.182.*



Profil

icon Re: Lavirinti04.07.2003. u 11:01 - pre 224 meseci
jedina slicnost je sto se koristi "tezina" polja. :) i hvala na "linku", ima dobrih algoritama tamo. Pozdrav
 
Odgovor na temu

Lale23
Milos Lazarevic
Nis

Član broj: 10921
Poruke: 4
*.rcub.bg.ac.yu

ICQ: 145628651


Profil

icon Re: Lavirinti06.07.2003. u 00:11 - pre 224 meseci
Ovo ti je uobicajan problem nalazenja najkraceg puta u grafu. Za to koristi ovaj navedeni BFS algoritam jer kolko sam razumeo tvoj lavirint on se predstavlja beztezinskim grafom. Pogledaj u neku knjigu o algoritmima ima dosta takmih algoritama za razne najkrace puteve. (Dijkstrin, Flojd-Warsalov,BFS, pa i DFS...)
 
Odgovor na temu

[es] :: Art of Programming :: Lavirinti

[ Pregleda: 6571 | Odgovora: 12 ] > FB > Twit

Postavi temu Odgovori

Srodne teme
Kliknite za generisanje liste srodnih tema...
Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.