Struttura dati per modellare un edificio su più piani

3 Risposte

• M

  migliorabile

  Super Famoso

  Iscritto da

  apr, 2013

  Messaggi:

  5875

  Re: Struttura dati per modellare un edificio su più piani

  05 set 2017, 06:06

  La tua domanda NON HA SENSO:
  NON ESISTE LA struttura dati per descrivere un oggetto. Le strutture DIPENDONO AL 1000% dal tipo di problema che devi risolvere, e da COME lo vuoi risolvere.
  
  1) un grafo e' una gran struttura dati, e va usata QUANDO ha senso usarla, anche perche' per maneggiarla e' necessario avere CHIARO come si maneggia
  2) un grafo gerarchico, detto anche ALBERO, e' un caso particolare di grafo, ed anche lui e' una gran struttura dati, ma va usato quando HA SENSO. Di sicuro NON HA SENSO nel tuo caso, a meno che il tuo edificio non sia una delle piramidi d'Egitto.
  3) le risorse per implementare un grafo sono infinitesimali: NON E' il grafo, il problema, ma quello che ci vuoi fare.
  
  Insomma, sconfonditi
• F

  Frank_Vi

  Pochi posts

  Iscritto da

  mag, 2016

  Messaggi:

  23

  Re: Struttura dati per modellare un edificio su più piani

  05 set 2017, 18:30

  Mi spiego, ho un insieme di beacon posti su due piani di un edificio.
  Pensavo di utilizzare un grafo in cui i nodi sono i beacon, gli archi il percorso tra due beacon, e il peso esprime la distanza in metri.
  Inoltre, per la ricerca del cammino minimo avevo pensato di usare l'algoritmo A* ma, dato che utilizza come euristica la distanza in linea d'aria tra due nodi, mi son chiesto: non può capitare che venga considerato un percorso che in linea d'aria è minore rispetto ad un altro, ma in realtà il percorso completo (tramite i vari nodi) è più lungo?
  Quindi, inizialmente, avevo pensato di considerare il grafo gerarchico, ora sto valutando invece di cambiare euristica, ad esempio ho visto un progetto che utilizza l'algoritmo A* con l'euristica di Manhattan.
  Non conoscono l'euristica di Manhattan (se non in generale) perchè ho studiato semplici grafi con l'algoritmo di Dijkstra; solo ora sto ampliando le mie conoscenze da solo, ma ho alcune difficoltà.
• D

  dvaosta

  Molto attivo

  Iscritto da

  lug, 2012

  Messaggi:

  962

  Re: Struttura dati per modellare un edificio su più piani

  05 set 2017, 19:24

  Il fatto che l'euristica sia una stima per difetto della distanza effettiva è ciò che rende A* ammissibile. La distanza Manattan è quella calcolata sommando gli spostamenti lungo due assi ortogonali (il nome deriva dal fatto che Manattan è percorsa da strade perpendicolari le une alle altre, per cui per calcolare la distanza stradale dal punto A al punto B basta fare (xb - xa) + (yb - xa), evitando quindi prodotti e radici quadrate), ma ha senso solo se effettivamente ti puoi muovere solo in 2 direzioni, altrimenti non hai più la garanzia che si tratti di una stima per difetto.