[es] - Lavirinti

Srodne teme

Kliknite za generisanje liste srodnih tema...

Navigacija

Brisanje liste

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

PeraT

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

Profil

Lavirinti

^{17.04.2002. u 04:33}

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

^{17.04.2002. u 04:33}

PeraT

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

Profil

Re: Lavirinti

^{17.04.2002. u 04:35}

Ah da kao sto ste primetili nemam ideju ni kako da predstavim lavirint
Mozda kao n-arno drvo???

^{17.04.2002. u 04:35}

01011011
Nikola Ivetić
CHICAGO, USA

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

ICQ: 45747235
Sajt: www.memorizeme.net

Profil

Re: Lavirinti

^{17.04.2002. u 09:19}

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.

Za druge se navija, Partizan se VOLI.
http://www.tipliga.com | http://www.pljuga.com | http://www.inno-studio.com | http://www.memorizeme.net

^{17.04.2002. u 09:19}

PeraT

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

Profil

Re: Lavirinti

^{17.04.2002. u 22:39}

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?

^{17.04.2002. u 22:39}

srki
Srdjan Mitrovic
Auckland, N.Z.

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

Profil

Re: Lavirinti

^{18.04.2002. u 16:44}

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)

^{18.04.2002. u 16:44}

PeraT

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

Profil

Re: Lavirinti

^{18.04.2002. u 22:01}

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)

^{18.04.2002. u 22:01}

amidar

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

ICQ: 4427607

Profil

Re: Lavirinti

^{19.04.2002. u 01:42}

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

^{19.04.2002. u 01:42}

srki
Srdjan Mitrovic
Auckland, N.Z.

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

Profil

Re: Lavirinti

^{19.04.2002. u 01:45}

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)

^{19.04.2002. u 01:45}

prompt
Student matematičkog fakulteta Univerziteta u Beogradu
Beograd

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

ICQ: 49488234

Profil

Re: Lavirinti

^{03.07.2003. u 12:47}

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 :))

^{03.07.2003. u 12:47}

BATE
Predrag Biskupovic
Kotor

Član broj: 4159
Poruke: 24
195.66.182.*

Profil

Re: Lavirinti

^{03.07.2003. u 13:24}

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 :)

^{03.07.2003. u 13:24}

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

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

Sajt: localhost

Profil

Re: Lavirinti

^{04.07.2003. u 04:38}

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

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

^{04.07.2003. u 04:38}

BATE
Predrag Biskupovic
Kotor

Član broj: 4159
Poruke: 24
195.66.182.*

Profil

Re: Lavirinti

^{04.07.2003. u 11:01}

jedina slicnost je sto se koristi "tezina" polja. :) i hvala na "linku", ima dobrih algoritama tamo. Pozdrav

^{04.07.2003. u 11:01}

Lale23
Milos Lazarevic
Nis

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

ICQ: 145628651

Profil

Re: Lavirinti

^{06.07.2003. u 00:11}

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...)

^{06.07.2003. u 00:11}