☰

» »

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
Skero

phyro ::

če imaš drevo je itak sam ena pot in kar dfs-jaš.
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
Skero

Zgodovina sprememb…

  • spremenil: detroit ()

phyro ::

detroit je izjavil:

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 3050 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
Skero

Zgodovina sprememb…

  • spremenil: detroit ()

Isotropic ::

kaj pa delas to, kaj v autocadu slucajno?

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

Sc0ut je izjavil:

Iščeš najkrajšo pot? Nisem iz faha, sem pa že sprogramiral to:

to je swarm intelligence, hevristika, torej ne zagotavlja optimalne rešitve

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

Rokm ::

Podatkovna struktura je navadno drevo, ali imaš tudi informacijo o staršu?

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


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

detroit ::

hvala fantje, bom mal poimplementiral ko pride čas.

Hvala za pomoč!
Skero

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Ne-rekurzivno iskanje po rekurzivni podatkovni strukturi

Oddelek: Programiranje		51137 (983) blaz_
»

Za programerske teoretike

Oddelek: Programiranje		478798 (5600) Jerry000
»

[Algoritem] Kako do najkrajše poti na med točkami

Oddelek: Programiranje		213247 (2835) Spura
»

Naloga [iz EU topologije]

Oddelek: Znanost in tehnologija		192038 (1579) Thomas
»

[C++] BST - poti do listov

Oddelek: Programiranje		6973 (886) Superboyy

Več podobnih tem