Forum » Programiranje » algoritm za pot med dvema točkama
algoritm za pot med dvema točkama
detroit ::
Kateri algoritm se uporablja za iskanje po drevesu (najkrajša pot je v bistvu tudi edina pot ker ni zank)
Sm mislil dijktro samo se mi zdi da brez veze komplicira globokim iskanjem najkrajših ker rabim samo pot. Edino pot (ker ni zank, si predstavljam da je samo ena pot)
lp matej
Sm mislil dijktro samo se mi zdi da brez veze komplicira globokim iskanjem najkrajših ker rabim samo pot. Edino pot (ker ni zank, si predstavljam da je samo ena pot)
lp matej
Skero
phyro ::
če imaš drevo je itak sam ena pot in kar dfs-jaš.
to sm na hitro spacal in nism siguren da deluje, ampak ideja je neki takega
Note: glede na to da maš drevo, bi lahko pazu da se ne ciklaš že sam s tem da bi si podal vertex s katerega si pršu in ne bi rabu been tabele
Note2: če maš enosmerne povezave, pol ne rabš sploh gledat kjer si bil in kje nisi bil
for all tocka -> been[tocka] = 0
dfs(cur, end):
if been[cur] == 1 then
return (False, [])
if cur == end then
return (True, [cur])
been[cur] = 1
for sosed in sosedi[cur]:
obstaja, pot = dfs(sosed, end)
if obstaja then
return (True, cur + pot)
return (False, [])
obstaja, najkrajsa_pot = dfs(a, b) #od a do b
print najkrajsa_pot
to sm na hitro spacal in nism siguren da deluje, ampak ideja je neki takega
Note: glede na to da maš drevo, bi lahko pazu da se ne ciklaš že sam s tem da bi si podal vertex s katerega si pršu in ne bi rabu been tabele
Note2: če maš enosmerne povezave, pol ne rabš sploh gledat kjer si bil in kje nisi bil
Zgodovina sprememb…
- spremenil: phyro ()
detroit ::
sm z rekurzijo že naredu en pseudo sam baje bo zmanjkal rama, ker pridobivanje točke in linije ni tako enostavna zadeva, ke rni nobenih relacij med njima, samo "geometry" se prekriva. Tako da bom še tvojo mal prešnofal:) hvala
p.s. kaj je dfs
p.s. kaj je dfs
Skero
Zgodovina sprememb…
- spremenil: detroit ()
phyro ::
sm z rekurzijo že naredu en pseudo sam baje bo zmanjkal rama, ker pridobivanje točke in linije ni tako enostavna zadeva, ke rni nobenih relacij med njima, samo "geometry" se prekriva. Tako da bom še tvojo mal prešnofal:) hvala
p.s. kaj je dfs
dfs je depth first search, najbolj obično iskanje. A rabiš samo koliko je dolga pot, ali tudi dejansko pot dobit?
kako velik graf pa maš?
detroit ::
samo pot dobit (torej featurje ki bojo zgradil pot). In ne rabim dolžine (noben weight mi ne koristi) samo pot. Graf je lahko tudi več tisoč nodov.
Skero
Blinder ::
dve točke identificirajo eno premico ampak premica jih lahko toži za kršenje zasebnega življenja.
99.991% of over-25 population has tried kissing.
If you're one of the 0.009% who hasn't, copy & paste this in your Signature.
Intel i3-12100f gtx 1080 Pismo smo stari v bozjo mater. Recesija generacija
If you're one of the 0.009% who hasn't, copy & paste this in your Signature.
Intel i3-12100f gtx 1080 Pismo smo stari v bozjo mater. Recesija generacija
detroit ::
Sicer ne razumem kam si ciljal:D
ampak to zasebno življenje je določeno le na grafičnem/geometry nivoju
Rezultat bo tako in tako polyline
ampak to zasebno življenje je določeno le na grafičnem/geometry nivoju
Rezultat bo tako in tako polyline
Skero
Zgodovina sprememb…
- spremenil: detroit ()
phyro ::
tudi če je več tisoč node-ov, dfs ma linearno kompleksnost, edin problem bi lahko bil da greš pregloboko v rekurzijo, v tem primeru pač implementiraš iterativno stvar
Sc0ut ::
Iščeš najkrajšo pot? Nisem iz faha, sem pa že sprogramiral to:
1231 v3, Z97 A, 16GB ram 1600mhz, 3070 RTX, HX850
phyro ::
detroit ::
ne iščem najkrajšo pot, iščem edino pot. Najkrajša je dijstkra ez. Se mi zdi da je že phyro odgovoru. Bom pa vidu ko pridem do problema:) Če ne bom pa kako svojo sklamfal:)
Skero
detroit ::
Nobenih relacij razen grafičnih. Torej se lahko dobi samo točko in priležne daljice (z geometrično funkcijo, ki je povrh vsega še zahtevna:). No saj iz tega lahko tudi starša nekako dobim takorekoč
Skero
Rokm ::
Če iščeš pot med točkama A in B, in lahko dobiš starša v nekem doglednem času, potem je verjetno ena izmed lažjih rešitev tale (ne vem, če je algoritem optimalen za iskanje poti v drevesu z relacijo starš):
Stvar je tako odvisna od višine drevesa in seveda težavnosti izračuna starša (oziroma razmerjem med težavnostjo izračuna sosedov in težavnostjo izračuna starša). Odvisno od tega kolikokrat boš ponavljal to operacijo je ali se ti izplača vnaprej izdelati strukturo kjer boš imel že ustvarjeno relacijo na starša.
- Za vsako izmed točk A in B, poiščeš pot me korenom in to točko. To storiš tako da začneš pri točki, pogledaš njenega starša, pogledaš starša od starša in nadaljuješ dokler ne prideš do korena drevesa.
- Zdaj imaš dve poti, npr: [A, M, N, U, P, R, Koren] ter [B, C, K, U, P, R, Koren]. Seznama primerjaš od zadaj in vidiš, da je najnižji skupni prednik U, torej bo pot enaka [A, M, N, U, K, C, B].
Stvar je tako odvisna od višine drevesa in seveda težavnosti izračuna starša (oziroma razmerjem med težavnostjo izračuna sosedov in težavnostjo izračuna starša). Odvisno od tega kolikokrat boš ponavljal to operacijo je ali se ti izplača vnaprej izdelati strukturo kjer boš imel že ustvarjeno relacijo na starša.
Spura ::
Za iskanje nodeov imas tri opcije: depth first search, breath first search, iterative deepening depth first search. Ko/ce tocke imas pa to kar je Rokm napisu.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Ne-rekurzivno iskanje po rekurzivni podatkovni strukturiOddelek: Programiranje | 1046 (892) | blaz_ |
| » | Za programerske teoretikeOddelek: Programiranje | 8514 (5316) | Jerry000 |
| » | [Algoritem] Kako do najkrajše poti na med točkamiOddelek: Programiranje | 3031 (2619) | Spura |
| » | Naloga [iz EU topologije]Oddelek: Znanost in tehnologija | 1983 (1524) | Thomas |
| » | [C++] BST - poti do listovOddelek: Programiranje | 918 (831) | Superboyy |