Lavirinti

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

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

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.

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?

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)

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)

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

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)

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

jednom sam naiso na takav problem, razbijao glavu i rjesio ga NEVJEROVATNO jednostavno. Prvo napravis matricu ... moze i dinamicki ako je takav zahtjev . 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 :)

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

Potpis

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

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