.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi] Progetto "RICHIAMI" (http://www.dsy.it/forum/showthread.php?threadid=17192)
Posted by p2p on 17-02-2005 09:50:
ragazzi, voi operate su una lista x vedere tra tutti gli automi che raggiungono... bla bla quelli con distanza minima da spostare? o altre strutture??
altra domanda: ma esiste percorso e tortuosita' fanno il discorso del prefisso o prendono il nome di un automa??
Posted by mattcobain on 17-02-2005 12:21:
Originally posted by p2p
...ma esiste percorso e tortuosita' fanno il discorso del prefisso o prendono il nome di un automa??
prendono il nome dell'automa, non è considerato come prefisso, anche perché nella descrizione delle 2 funzioni sembra abbastanza chiaro si riferiscano all'automa di nome N passato alla funzione (che se non esiste viene stampato NO oppure -1 a seconda della funzione)
Posted by Skilotto83 on 17-02-2005 12:42:
Originally posted by LjL
Se il compilatore/OS alloca [molto] più heap (non stack ;-) di quanto ne hai chiesto, fondamentalmente è colpa sua. Non ritengo che sia una cosa di cui si debba preoccupare molto il programmatore.
Il fatto che ti dia roba "sparsa in giro" non vedo perché dovrebbe essere un problema.
Il fatto che ci mette del tempo ad eseguire l'operazione è vero, ma considera che ci vuole del tempo anche per eseguire la realloc() -- e si tratta di *parecchio* tempo, nel caso in cui il sistema sia costretto a copiare tutto il tuo blocco di memoria da un'altra parte.
A volte usare array che possono crescere di dimensione (realloc()) non è una cattiva idea, quindi se tu ritieni che nel tuo caso sia una buona idea, fallo - può darsi che tu abbia ragione. Io ci penserei su un paio di volte però.
il metodo dell'array che uso ha dei vantaggi enormi su tutte le altre strutture:
con un array si accede direttamente ad una posizione, proprio perchè nn sono sparse in memoria...
Quando calcolo se esiste un percorso se mi scontro su un ostacolo so quale ostacolo è, lo indicizzo, e poi ripeto la ricorsione solo su quello e non su tutti gli ostacoli della lista...
lo stesso vale per automa, ho trovato forse il modo di ordinare i nomi degli automi nell'array...quando mi viene chiesto il prefisso degli automi da considerare io accedo direttamente allla posizione corrsipondente al "path" dato..e da li' vado avanti...
Con una lista in tuti i casi devo scorrere dall'inizio, anche se poi il discorso una volta trovato il "path" è lo stesso che con array...
e se devo inserire un automa o un ostacolo devo controllare che la posizione/i nn siano occupate da automi o ostacoli...qui allora devo scorrere tutto l'array..ma scorrere tutto un array o tutta una lista, o tutto un albero è lo stesso..no??__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by Skilotto83 on 17-02-2005 12:45:
Originally posted by p2p
ragazzi, voi operate su una lista x vedere tra tutti gli automi che raggiungono... bla bla quelli con distanza minima da spostare? o altre strutture??
altra domanda: ma esiste percorso e tortuosita' fanno il discorso del prefisso o prendono il nome di un automa??
io uso un array, cosi' come ho fatto per ostacoli e automi, quindi se hai usato una lista usa ancora una lista....
Tortuosita' e esiste percorso operano solo sul nome dell'automa...
Infatti in teoria sono i piu' semplici...
E' il comando segnale che è complesso, perchè su ogni automa che è compreso nel prefisso sceglie quello a distanza minima, poi chiami il calcolo di percorso libero, e poi su quelli chiedi di restituire quello con tortuosita' minima..in pratika devi memorizzare i passaggi in due liste...no??__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by Motomax on 17-02-2005 13:02:
Ciao please potete aiutarmi che sto diventando pazzo!!!!
ma avete trovato una soluzione per il Percorso e la tortuosità?
Posted by wingzero on 17-02-2005 13:04:
Originally posted by Skilotto83
il metodo dell'array che uso ha dei vantaggi enormi su tutte le altre strutture:
con un array si accede direttamente ad una posizione, proprio perchè nn sono sparse in memoria...
Quando calcolo se esiste un percorso se mi scontro su un ostacolo so quale ostacolo è, lo indicizzo, e poi ripeto la ricorsione solo su quello e non su tutti gli ostacoli della lista...
lo stesso vale per automa, ho trovato forse il modo di ordinare i nomi degli automi nell'array...quando mi viene chiesto il prefisso degli automi da considerare io accedo direttamente allla posizione corrsipondente al "path" dato..e da li' vado avanti...
Con una lista in tuti i casi devo scorrere dall'inizio, anche se poi il discorso una volta trovato il "path" è lo stesso che con array...
e se devo inserire un automa o un ostacolo devo controllare che la posizione/i nn siano occupate da automi o ostacoli...qui allora devo scorrere tutto l'array..ma scorrere tutto un array o tutta una lista, o tutto un albero è lo stesso..no??
Ma parli di un array di char? Perchè è nulla più di una stringa in pratica in C. Per avere una mappatura corretta con array devi averli multdimensionali. Oppure usare strutture con struct ed a quel punto si usano le liste di norma.
Il grosso problema con l'uso di array, multidimensionali poi (quindi matrici che il professore non vuole che si usino poichè si lavora con una mappa di dimensioni infinite), è che non c'è un modo tanto banale di crearne una rappresentazione compatta. In effetti non c'è neanche con le liste di adiacenza che per una mappa senza limiti (a parte gli interi a 32bit) ed oggetti sparsi ovunque nella mappa rappresenta un grosso problema.
Posted by wingzero on 17-02-2005 13:07:
Originally posted by Motomax
Ciao please potete aiutarmi che sto diventando pazzo!!!!
ma avete trovato una soluzione per il Percorso e la tortuosità?
Personalmente no. Ed inizio a rinunciare al fatto di poter consegnare il programma funzionante. Ho dei bei problemi a gestire le liste evitando memory leak di suo, ma poi ad usarle concatenate ancora peggio. E comunque non ho idea di come impostare il calcolo della tortuosità nelle combinazioni di liste di adiacenza, che viste le dimensioni infinite possono diventare onerose da gestire e tendere a crash del programma se il codice non è ben debuggato. E non ho il tempo materiale per debuggarlo.
Spero almeno di poter riusare buona parte delle funzioni che sto creando per il prossimo progetto, sperando sia qualcosa di più semplice.
Posted by superfabius on 17-02-2005 13:16:
int main (void) ?!
Posted by LjL on 17-02-2005 13:52:
Originally posted by superfabius
int main (void) ?!
int main(void) {
return EXIT_FAILURE;
}__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by Skilotto83 on 17-02-2005 13:55:
Originally posted by wingzero
Ma parli di un array di char? Perchè è nulla più di una stringa in pratica in C. Per avere una mappatura corretta con array devi averli multdimensionali. Oppure usare strutture con struct ed a quel punto si usano le liste di norma.
Il grosso problema con l'uso di array, multidimensionali poi (quindi matrici che il professore non vuole che si usino poichè si lavora con una mappa di dimensioni infinite), è che non c'è un modo tanto banale di crearne una rappresentazione compatta. In effetti non c'è neanche con le liste di adiacenza che per una mappa senza limiti (a parte gli interi a 32bit) ed oggetti sparsi ovunque nella mappa rappresenta un grosso problema.
uso un array in cui metto le strutture....
non è vero che si usano le liste di norma...questo è quello che ti ha fatto credere nel suo corso..
ripeto..con le liste allocate dinamicamente le singole celle della lista sono sparse in memoria e non vi si puo' accedere direttamente senza ripetere tutta la ricerca..io invece accedo direttamente a ogni singolo automa o ostacolo che mi serve per il calcolo della tortuosita'...e ti garantisko ke il mio tempo di esecuzione su un metodo come "segnale" (dove senza array ripassi la stessa lista di ostacoli per migliaia di volte) è ottimo...__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by Skilotto83 on 17-02-2005 13:57:
Originally posted by wingzero
Personalmente no. Ed inizio a rinunciare al fatto di poter consegnare il programma funzionante. Ho dei bei problemi a gestire le liste evitando memory leak di suo, ma poi ad usarle concatenate ancora peggio. E comunque non ho idea di come impostare il calcolo della tortuosità nelle combinazioni di liste di adiacenza, che viste le dimensioni infinite possono diventare onerose da gestire e tendere a crash del programma se il codice non è ben debuggato. E non ho il tempo materiale per debuggarlo.
Spero almeno di poter riusare buona parte delle funzioni che sto creando per il prossimo progetto, sperando sia qualcosa di più semplice.
se usi gli array come me risolvi il problema...__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)
MSN andrea.poretti(at)hotmail.it
Posted by wingzero on 17-02-2005 14:16:
Originally posted by Skilotto83
se usi gli array come me risolvi il problema...
Non vedo come il tuo metodo di risoluzione possa essere valido. Secondo me tralasci una parte del problema.
Posted by wingzero on 17-02-2005 14:18:
Originally posted by Skilotto83
uso un array in cui metto le strutture....
non è vero che si usano le liste di norma...questo è quello che ti ha fatto credere nel suo corso..
ripeto..con le liste allocate dinamicamente le singole celle della lista sono sparse in memoria e non vi si puo' accedere direttamente senza ripetere tutta la ricerca..io invece accedo direttamente a ogni singolo automa o ostacolo che mi serve per il calcolo della tortuosita'...e ti garantisko ke il mio tempo di esecuzione su un metodo come "segnale" (dove senza array ripassi la stessa lista di ostacoli per migliaia di volte) è ottimo...
Non mi è molto chiaro.. un array in cui metti le strutture.. ma parli di array monodimensionale ? E come puoi tenere traccia della mappa bidimensionale a dimensioni infinite con array monodimensionali ? Gli array sono strutture dati di loro. Usi puntatori a puntatori per creare una catena analoga alle liste?
Scusa ma qui non è che dipenda da come il professore abbia impostato il corso, basta leggersi qualsiasi libro sugli algoritmi come Dijkstra per vedere che si usano le liste di adiacenza. Oppure matrici di adiacenza. Ma comunque sono array multidimensionali da gestire e non è che bastino quelli, nè in ogni caso basta una singola struttura per risolvere il problema.
Anche se si sa a priori che tutti i percorsi hanno la stessa distanza minima il problema delle combinazioni da scoprire per trovare la migliore resta riguardo la tortuosità ed è molto più difficile da impostare che non il problema del percorso minimo.
Poi non è vero che non accedi direttamente usando le liste. Le liste di adiacenza servono per calcolare le combinazioni in un digrafo/rete. Sono difficili da usare e creano molti problemi su un mondo a dimensione infinita. Problemi che in 15gg totali non sono risolvibili.
Posted by LjL on 17-02-2005 18:09:
Originally posted by Skilotto83
il metodo dell'array che uso ha dei vantaggi enormi su tutte le altre strutture:
Il fatto è che non credo di aver veramente capito dove, come e quando usi array invece di liste. Vediamo un attimo...
con un array si accede direttamente ad una posizione, proprio perchè nn sono sparse in memoria...
Questo dipende. Si accede "direttamente" (cioè in tempo O(1)) se gli indici dell'array *sono la tua chiave di ricerca*. Se non lo sono, ti tocca o scandirti tutto l'array (esattamente come se fosse una lista) o, solo se gli elementi sono ordinati per chiave, fare qualcosa come una ricerca binaria.
Quindi, tu come indicizzi gli array? Nel caso degli automi,
- Se hai un array di automi in cui ogni indice corrisponde all'ascissa (o all'ordinata) dell'automa, sprechi un sacco di spazio.
- Se hai un array ordinato per ascissa (o per ordinata), puoi fare una ricerca binaria, ma una volta trovata l'ascissa che ti serve vedi comunque trovare l'ordinata. Cosa fai a questo punto, usi un array di array?
- Se hai un array ordinato per nome dell'automa, puoi fare una ricerca binaria per individuare gli automi col prefisso che ti interessa. Vero. Ma per far questo direi che il metodo dell'albero è migliore, anche perché tu così ogni volta che aggiungi un automa devi spostare tutti i successivi elementi dell'array (questo vale anche per il caso precedente!)
Quando calcolo se esiste un percorso se mi scontro su un ostacolo so quale ostacolo è, lo indicizzo, e poi ripeto la ricorsione solo su quello e non su tutti gli ostacoli della lista...
Ecco, qui non capisco. Stai dicendo che, oltre all'array di automi, hai anche un array di ostacoli, giusto?
Di nuovo, come sono ordinati gli ostacoli? Qui è anche un filino più complicato perché gli ostacoli hanno *due* coppie di coordinate.
Perché dici "se mi scontro su un ostacolo so quale ostacolo è"? Per *sapere* subito, a colpo sicuro, in tempo O(1), se c'è un ostacolo in un certo punto del piano, dovresti rappresentare il piano come matrice, cosa chiaramente non fattibile. Facendo in un altro modo (salvo cose strane tipo hash) non vedo modo di sapere "a colpo sicuro" se in un certo punto c'è un ostacolo.
O forse intendi dire che, quando ti scontri con un ostacolo (e comunque in che modo controlli se ti sei scontrato?) vai a vedere che punti del piano copre quell'ostacolo, e te li "segni da qualche parte"? È questo che intendi quando dici "lo indicizzo"?
Poi, cosa vuol dire che ripeti la ricorsione solo su quello? Dovrai pur considerare anche gli *altri* ostacoli inscritti nella zona di piano che ti interessa, no? (certo, dipende da cosa fa la tua ricorsione)
lo stesso vale per automa, ho trovato forse il modo di ordinare i nomi degli automi nell'array...
Ah, questo prima mi era sfuggito, e quindi la prima parte della mia risposta è inutile, ma l'ho lasciata giusto perché mi spiaceva cancellarla...
Rimane il fatto che mi pare che, per ogni nuovo automa, tu debba spostare tutti gli elementi dell'array successivi alla posizione che dovrà essere occupata dal nuovo automa.
quando mi viene chiesto il prefisso degli automi da considerare io accedo direttamente allla posizione corrsipondente al "path" dato..e da li' vado avanti...
Come fai ad accedere *direttamente* a quella posizione senza fare almeno una ricerchina binaria? Non vedo modo per cui tu, per *ogni* possibile prefisso, possa sapere qual è la posizione nell'array dove gli automi cominciano ad avere quel prefisso.
Con una lista in tuti i casi devo scorrere dall'inizio, anche se poi il discorso una volta trovato il "path" è lo stesso che con array...
Si, con una lista devi sempre scorrere dall'inizio. Con un albero no però...
e se devo inserire un automa o un ostacolo devo controllare che la posizione/i nn siano occupate da automi o ostacoli...qui allora devo scorrere tutto l'array..ma scorrere tutto un array o tutta una lista, o tutto un albero è lo stesso..no??
Sì, direi di sì. Credo che a questo sia molto, molto difficile scampare, a meno di non usare strutture piuttosto complesse che permettano una ricerca veloce di automi e ostacoli usando come chiavi le coordinate: ad esempio si potrebbe usare un hash di hash, ma anche volendo spararsi una roba del genere, come si farebbe a sapere se il punto (x,y) appartiene ad un ostacolo? Cerchi x nel primo hash, cerchi y nell'hash di x... e non trovi niente, perché l'ostacolo aveva coordinate (x-a, y-b), (x+c, y+d).
Comunque riguardando il tuo messaggio iniziale rimango piuttosto perplesso: lì dicevi che tu
- crei un array di dimensione fissa contenente, per ogni elemento, i dati di un automa. E ok.
- assegni valori di testa e coda all'array e lo gestisci come una lista. Questa mi sfugge proprio: posso ancora capire il valore di "coda" (più comunemente noto come "numero di elementi nell'array)... ma il valore di "testa"? O sono puntatori? E se sono puntatori, a che ti servono?
Dicevi che, in pratica, usi delle liste, ma non sono "liste dinamiche" nel senso comune del termine, ma "array trattati come liste". E qui non capisco cosa tu intenda con "trattare un array come una lista".
Ogni elemento dentro l'array per caso ha un puntatore all'elemento seguente? Se sì, allora forse ho capito cosa fai -- semplicemente usi delle liste dinamiche ma ti sei in pratica scritto il tuo allocatore di memoria personale invece di usare malloc(). Ma se è così, tu stai effettivamente usando delle liste e non degli array, con tutti i vantaggi e gli svantaggi che ne derivano -- compreso il *non* poter accedere "direttamente" agli elementi.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by ZeroByte on 17-02-2005 19:11:
Qualcuno di voi ha un'idea diversa da alberi o liste di adiacenza per implementare esistePercorso? A me sembrano le due uniche strutture accettabili per una cosa simile. Ma soprattutto, c'è qualcuno che è in grado di consegnare in tempo questo progetto? E' solo una mia impressione ma il tempo concesso è davvero poco?
__________________
Un computer ti fa fare più errori e più velocemente di qualunque altra invenzione dell'uomo - con l'eccezione forse delle armi da fuoco e della tequila (Mitch Ratcliffe)
