.dsy:it. - [Algoritmi] Progetto "RICHIAMI"

Pages (33): « First ... « 13 14 15 16 [17] 18 19 20 21 » ... Last »
Show 150 posts per page

.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 LjL on 17-02-2005 19:14:

Originally posted by wingzero

[snip]

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.

No, aspetta, a me non sembra così ovvio che *debbano* essere usate liste o matrici di adiacenza.

Infatti, in un grafo generico, si hanno nodi (che non sono [necessariamente] identificati da coordinate [cartesiane]) che possono essere adiacenti (cioè collegati da lati) ad un numero arbitrario di altri nodi.

Nel nostro caso, invece, abbiamo nodi identificati da coordinate cartesiane, che possono essere adiacenti ad al massimo altri quattro nodi. E aggiungendoci pure il fatto che ogni automa si può muovere solo *verso* il richiamo, potresti persino dire che ogni nodo è adiacente ad altri *due* nodi, e che il grafo è orientato.

Con questo non voglio dire che il nostro piano *non* va trattato come un grafo (con relative liste o matrici di adiacenza), solo che è un caso molto più specifico rispetto al caso "grafo generico", e che quindi è probabile che anche le strutture dati possano permettersi di essere più specifiche.

Prendi ad esempio il caso in cui abbiamo un automa in (0,0) e la sorgente in (9,9). Ci vien fuori un grafo con 10*10=100 nodi e 9*10+9*10=180 lati.
Ma se supponiamo che non ci siano ostacoli, per i nostri scopi (calcolo della tortuosità) questo grafo è perfettamente equivalente al semplice grafo con 4 vertici e 4 lati:

o----o
| |
o----X

Infatti di tutti gli altri lati e vertici non ci importa niente, dato che passarci causerebbe solo un aumento della tortuosità.

Certo, in questo caso è semplice, mentre con gli ostacoli di mezzo non riuscirei più a ridurre il grafo così semplicemente. Ma secondo me il punto sta proprio qui: bisognerebbe trovare un algoritmo capace di semplificare i nostri grafi *tenendo conto degli ostacoli*, o meglio ancora fare in modo che, ogni volta che viene creato un automa/ostacolo, questo sia *già* inserito in un grafo semplificato.

Come riuscirci non l'ho ancora capito, ma l'idea di base sarebbe: ogni volta che nel grafo non-semplificato c'è una sequenza di passi (lati) aventi tutti lo stesso orientamento (orizzontale vs verticale), tale sequenza può essere "condensata" (semplificata) in un unico lato con due vertici.

A questo punto, chiaramente, non esisterebbe più la garanzia che da ogni vertice partano al massimo quattro lati.
Ma proprio il fatto che cada questa garanzia potrebbe secondo me permetterci di usare un algoritmo "prefabbricato" a nostra scelta su un "normale" grafo molto più piccolo di quello iniziale.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by wingzero on 17-02-2005 19:18:

Originally posted by ZeroByte
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?

Per quanto mi riguarda posso dire solo che se avessi avuto almeno il doppio del tempo, un 30gg, probabilmente sarei riuscito a finirlo e consegnarlo, ma in queste condizioni al momento quasi sicuramente non ci riuscirò. Spero solo che il prossimo appello presenti un problema più semplice che non mi metta così tanto in difficoltà o non arriverò mai all'orale..

Posted by wingzero on 17-02-2005 19:27:

Originally posted by LjL
No, aspetta, a me non sembra così ovvio che *debbano* essere usate liste o matrici di adiacenza.

Infatti, in un grafo generico, si hanno nodi (che non sono [necessariamente] identificati da coordinate [cartesiane]) che possono essere adiacenti (cioè collegati da lati) ad un numero arbitrario di altri nodi.

Nel nostro caso, invece, abbiamo nodi identificati da coordinate cartesiane, che possono essere adiacenti ad al massimo altri quattro nodi. E aggiungendoci pure il fatto che ogni automa si può muovere solo *verso* il richiamo, potresti persino dire che ogni nodo è adiacente ad altri *due* nodi, e che il grafo è orientato.

Con questo non voglio dire che il nostro piano *non* va trattato come un grafo (con relative liste o matrici di adiacenza), solo che è un caso molto più specifico rispetto al caso "grafo generico", e che quindi è probabile che anche le strutture dati possano permettersi di essere più specifiche.

Prendi ad esempio il caso in cui abbiamo un automa in (0,0) e la sorgente in (9,9). Ci vien fuori un grafo con 10*10=100 nodi e 9*10+9*10=180 lati.
Ma se supponiamo che non ci siano ostacoli, per i nostri scopi (calcolo della tortuosità) questo grafo è perfettamente equivalente al semplice grafo con 4 vertici e 4 lati:

o----o
| |
o----X

Infatti di tutti gli altri lati e vertici non ci importa niente, dato che passarci causerebbe solo un aumento della tortuosità.

Certo, in questo caso è semplice, mentre con gli ostacoli di mezzo non riuscirei più a ridurre il grafo così semplicemente. Ma secondo me il punto sta proprio qui: bisognerebbe trovare un algoritmo capace di semplificare i nostri grafi *tenendo conto degli ostacoli*, o meglio ancora fare in modo che, ogni volta che viene creato un automa/ostacolo, questo sia *già* inserito in un grafo semplificato.

Come riuscirci non l'ho ancora capito, ma l'idea di base sarebbe: ogni volta che nel grafo non-semplificato c'è una sequenza di passi (lati) aventi tutti lo stesso orientamento (orizzontale vs verticale), tale sequenza può essere "condensata" (semplificata) in un unico lato con due vertici.

A questo punto, chiaramente, non esisterebbe più la garanzia che da ogni vertice partano al massimo quattro lati.
Ma proprio il fatto che cada questa garanzia potrebbe secondo me permetterci di usare un algoritmo "prefabbricato" a nostra scelta su un "normale" grafo molto più piccolo di quello iniziale.

Sì, bhè, è un grafo orientato (digrafo = digraph dall'inglese = directed graph = grafo orientato), che è un modo per disegnare una rete con archi orientati.

Il grosso problema sta nell'impostare la tortuosità che non so come usarla per calcolare la minore. Ed ho problemi a programmare senza memory leak delle liste di adiacenza.. non riuscirò mai a farle funzionare in tempo per la consegna.. e se anche ci riuscissi poi non saprei come usarle per risolvere il tutto al momento. Quindi ritengo di non essere in grado di consegnare, purtroppo per me.

Posted by wingzero on 17-02-2005 19:30:

Originally posted by LjL
No, aspetta, a me non sembra così ovvio che *debbano* essere usate liste o matrici di adiacenza.

Infatti, in un grafo generico, si hanno nodi (che non sono [necessariamente] identificati da coordinate [cartesiane]) che possono essere adiacenti (cioè collegati da lati) ad un numero arbitrario di altri nodi.

Nel nostro caso, invece, abbiamo nodi identificati da coordinate cartesiane, che possono essere adiacenti ad al massimo altri quattro nodi. E aggiungendoci pure il fatto che ogni automa si può muovere solo *verso* il richiamo, potresti persino dire che ogni nodo è adiacente ad altri *due* nodi, e che il grafo è orientato.

Puoi dirlo in caso di mappa priva da ostacoli magari, ma con gli ostacoli il discorso cambia perchè dei percorsi liberi bisognerà far scegliere all'automa quello con minore tortuosità.
Ciò non toglie che è comunque un grafo orientato.

Posted by Skilotto83 on 17-02-2005 21:19:

Originally posted by LjL
Il fatto è che non credo di aver veramente capito dove, come e quando usi array invece di liste. Vediamo un attimo...

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

qui ti sei gia' risposto piu' aventi...ho trovato il modo di ordinarli...ma in effetti kmq devo partire dall'inizio...anche se alemno cosi' so' quando finire...il ke mi sembra pari all'uso di un alebro come soluzione...se ho tempo implemento una ricerca dicotomica cosi' da migliorare il tutto...anche se nn di molto...

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)

questo nn lo puoi capire senza vedere il mio metodo di ricerca del percorso...
Kmq l'idea che ho avuto, ancora da sistemare è di dare un indice a ogni ostacolo nel piano, quando cerco il percorso(che nn faccio di una cella alla volta ma di segmenti di lunghezza n)arrivando a sbattare su un ostacolo so qual'è(perkè ha un indice)quindi memorizzo l'indice, lo cerco nel mio bell'array direttamente e poi in base a quello ne "capisco" la struttura cosi'0 da poterlo evitare...il tutto è complicato, ma svolgo una specie di indietreggiamento...
Spero di essere stato chiaro, altrimenti mi spingo troppo oltre...

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.

questo kmq lo fai anche con un albero...in tutti i casi per inserire devi scorrere e scegliere la posizione...

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.

in effetti oggi ho implementato la cosa e nn posso..ma nn rinuncio alla mia idea in quanto voglio usare la stessa struttura per ostacoli e automi...quindi posso migliorare la cosa con ricerca dicotomica che parte da meta'...ma le cose migliorano su numeri alti...tipo 10000 automi...altrimenti è pratikamente lo stesso..ma è per mostrare al prof che so' il problema e cerco di migliorarlo..

Si, con una lista devi sempre scorrere dall'inizio. Con un albero no però...

e invece si'...come fai a inserire un nodo senza aver prima guardato dove metterlo??

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?

la testa che intendo è forse quella che tu chiami coda...
kmq semplicemente dopo aver inserito l'automa aumento la posizione dell'array e assegno alla posizione +1 il valore "testa"...mi serve ogni volta che inserisco...se la testa supera il max dim array allora vado in outlist e faccio la realloc...

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.

__________________
"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 23:46:

Originally posted by Skilotto83
qui ti sei gia' risposto piu' aventi...ho trovato il modo di ordinarli...ma in effetti kmq devo partire dall'inizio...anche se alemno cosi' so' quando finire...il ke mi sembra pari all'uso di un alebro come soluzione...se ho tempo implemento una ricerca dicotomica cosi' da migliorare il tutto...anche se nn di molto...

Lo puoi anche dividere in centinaia di segmenti un array utilizzando dei puntatori, non otterrai lo stesso effetto. Se gli array fossero stati sufficienti come pensi tu nessuno avrebbe sviluppato gli ADT (Abstract Data Type) per risolvere i problemi. Gli array in pratica esistono nell'hardware e sono un'astrazione fittizia.

questo nn lo puoi capire senza vedere il mio metodo di ricerca del percorso...
Kmq l'idea che ho avuto, ancora da sistemare è di dare un indice a ogni ostacolo nel piano, quando cerco il percorso(che nn faccio di una cella alla volta ma di segmenti di lunghezza n)arrivando a sbattare su un ostacolo so qual'è(perkè ha un indice)quindi memorizzo l'indice, lo cerco nel mio bell'array direttamente e poi in base a quello ne "capisco" la struttura cosi'0 da poterlo evitare...il tutto è complicato, ma svolgo una specie di indietreggiamento...
Spero di essere stato chiaro, altrimenti mi spingo troppo oltre...

In base all'indice , cioè la posizione in un array monodimensionale, come puoi "capire la struttura" di un ostacolo che è un oggetto rettangolare che può avere dimensione infinita ed occupare migliaia di celle ? (oltre al fatto che possono esserci più ostacoli sovrapposti sulle stesse coordinate i cui bordi di alcuni possono liberamente estendersi oltre parte dei bordi di quelli "sottostanti", pensando la sovrapposizione a strati).
Con un array monodimensionale è impossibile tenere traccia di oggetti su un piano bidimensionale. Il minimo possibile è usare una matrice che rappresenti la griglia, quindi un array bidimensionale. Ma non è efficiente ed il professore dice di non usarla.

in effetti oggi ho implementato la cosa e nn posso..ma nn rinuncio alla mia idea in quanto voglio usare la stessa struttura per ostacoli e automi...quindi posso migliorare la cosa con ricerca dicotomica che parte da meta'...ma le cose migliorano su numeri alti...tipo 10000 automi...altrimenti è pratikamente lo stesso..ma è per mostrare al prof che so' il problema e cerco di migliorarlo..

Scusa, ma usare un puntatore per suddividere la scansione di un array non è che crea un algoritmo magico che al livello asintotico ha un limite in pratica negativo... Anche perchè che io sappia non esiste modo di aumentare la velocità di un algoritmo all'aumentare del numero di dati da elaborare... Tanto è che poi quanto più un array è grande tanto più aumentano i tempi di accesso. Al massimo possono restare costanti , più o meno, in architetture hardware reali...

e invece si'...come fai a inserire un nodo senza aver prima guardato dove metterlo??

Non è così dispendiosa la cosa come puoi pensare quando si usano le reti con liste di adiacenza. Altrimenti non la userebbe nessuno.

la testa che intendo è forse quella che tu chiami coda...
kmq semplicemente dopo aver inserito l'automa aumento la posizione dell'array e assegno alla posizione +1 il valore "testa"...mi serve ogni volta che inserisco...se la testa supera il max dim array allora vado in outlist e faccio la realloc...

? Ok. Ho capito che riallochi la memoria per aumentare le dimensioni dell'array, tuttavia questo non vedo come possa risolvere tutto il problema. Tu continui a parlare di array monodimensionali in cui dici di inserire le strutture... Ciò che dici non può funzionare. E' impossibile usare array monodimensionali per tener traccia di coordinate ed oggetti in uno spazio bidimensionale. Ed usare una matrice, array bidimensionale, è vietato dal progetto perchè dispendioso in termini di tempo e risorse per un mondo a dimensioni infinite.
E se è per questo aumentare le dimensioni dell'array per le stringhe di input degli utenti è necessario se non si vuole usare una lista, visto che anche le stringhe non devono avere alcun limite.

Posted by LjL on 18-02-2005 01:51:

Originally posted by Skilotto83
qui ti sei gia' risposto piu' aventi...

Sì, lo so... pardon.

ho trovato il modo di ordinarli...ma in effetti kmq devo partire dall'inizio...anche se alemno cosi' so' quando finire...il ke mi sembra pari all'uso di un alebro come soluzione...

Uhm, mica tanto. Se usi un albero, il tempo necessario per la ricerca è una funzione della lunghezza del prefisso e del numero di automi *che rispondono a quel prefisso*. Se usi una lista (o array, in questo caso è uguale) in cui cerchi partendo dall'inizio, il tempo diventa una funzione della lunghezza del prefisso e del numero *totale* di automi.

[Sì, rimane comunque funzione *anche* della lunghezza del prefisso anche se usi cose come una strcmp()]

se ho tempo implemento una ricerca dicotomica cosi' da migliorare il tutto...anche se nn di molto...

Secondo me invece migliora di molto, anche se (come quasi in tutto...) solo asintoticamente, quindi non per numeri bassi.

Ma tra l'altro c'è un altro problema: se rappresenti i nomi degli automi come stringhe o comunque come oggetti creati da una malloc(), come fai a soddisfare la richiesta per cui la lunghezza delle stringhe non dev'essere limitata? L'unico modo che vedo è usare un'*altra* realloc (e poi magari un'altra e un'altra ancora...) se ce n'è bisogno -- cioè man mano che vedi che la stringa in input supera la lunghezza fissata dalla malloc().

questo nn lo puoi capire senza vedere il mio metodo di ricerca del percorso...

Sì, anche questo è vero.

Kmq l'idea che ho avuto, ancora da sistemare è di dare un indice a ogni ostacolo nel piano, quando cerco il percorso(che nn faccio di una cella alla volta ma di segmenti di lunghezza n)arrivando a sbattare su un ostacolo so qual'è(perkè ha un indice)quindi memorizzo l'indice, lo cerco nel mio bell'array direttamente e poi in base a quello ne "capisco" la struttura cosi'0 da poterlo evitare...

Qui sono d'accordo con quello che ha detto wingzero nell'ultimo messaggio: come diavolo fai a dare agli ostacoli un indice che permetta immediatamente di capire se stai sbattendoci contro?

Se come indice usi l'ascissa dell'ostacolo (che tra l'altro di ascissa non ne ha una sola), devi comunque smazzarti l'ordinata. Se usi l'ordinata, devi smazzarti l'ascissa.
Se combini in qualche modo ascissa e ordinata è come se stessi usando una matrice bidimensionale, a meno di usare un hash (cosa che tra l'altro potrebbe non essere una pessima idea, se non fosse che gli ostacoli non sono punti ma rettangoli... comunque può essere una soluzione).

il tutto è complicato, ma svolgo una specie di indietreggiamento...
Spero di essere stato chiaro, altrimenti mi spingo troppo oltre...

Sì, credo di aver capito il concetto... vai dritto, quando sbatti contro un ostacolo giri; se così facendo poi riesci a seguire un percorso decente, bene, altrimenti riprovi girando un po' prima di raggiungere l'ostacolo.
Sta attento però... detto così è abbastanza generico, ma io di idee del genere ne ho provate più di una, e ho sempre trovato inghippi, a volte solo dopo averci ragionato un bel po'. Quindi ti posso solo consigliare di controllare bene che non ci siano inghippi.

questo kmq lo fai anche con un albero...in tutti i casi per inserire devi scorrere e scegliere la posizione...

Insomma... primo, un albero non lo devi scorrere *tutto* (non devi passare per tutti i nodi); se i nodi sono n, "spesso e volentieri" devi scorrerne soltanto log(n). Una lista invece la devi scorrere fino a quando non trovi la posizione che cercavi, e per farlo ci metti O(n).
Secondo, io intedevo dire un'altra cosa: con gli alberi e con le liste devi scorrere, ok, ma dopo che hai scorso puoi inserire con un'operazione di tempo O(1).
Con un array, invece, dopo che hai scorso devi "fare spazio" per il nuovo elemento, cioè spostare di uno tutti gli elementi successivi -- un'operazione di tempo O(n).

[snip]

e invece si'...come fai a inserire un nodo senza aver prima guardato dove metterlo??

Sì, hai ragione. Intendevo dire quello che ho scritto sopra. Qualcosa devi "scorrere" comunque, semplicemente è di meno (o, nel caso peggiore, lo stesso).

la testa che intendo è forse quella che tu chiami coda...
kmq semplicemente dopo aver inserito l'automa aumento la posizione dell'array e assegno alla posizione +1 il valore "testa"...mi serve ogni volta che inserisco...se la testa supera il max dim array allora vado in outlist e faccio la realloc...

Ah, ok... mi confondeva il fatto che tu parlassi *sia* di testa *sia* di coda.
Quello che dici tu è quello che io di solito chiamo il "count" di un array (semplicemente perché la relativa variabile la chiamo sempre Count).

Attento comunque: ti va bene solo finché gli elementi dell'array non li tieni ordinati, dato che ti basta aggiungere il nuovo elemento alla fine dell'array (e realloc()are se necessario).
Ma se decidi di metterli in ordine (ad esempio per fare una ricerca dicotomica) vien fuori il problema che dicevo, cioè che inserire un elemento in una posizione arbitraria dell'array comporta il dover spostare di uno tutti gli elementi successivi.

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 18-02-2005 02:12:

Originally posted by wingzero
Lo puoi anche dividere in centinaia di segmenti un array utilizzando dei puntatori, non otterrai lo stesso effetto. Se gli array fossero stati sufficienti come pensi tu nessuno avrebbe sviluppato gli ADT (Abstract Data Type) per risolvere i problemi. Gli array in pratica esistono nell'hardware e sono un'astrazione fittizia.

Guarda che una lista o un albero non sono in sé e per sé dei tipi di dati astratti.
Vedi: http://www.swif.uniba.it/lei/foldop...tract+data+type

A mio avviso poi una lista o un albero è un'astrazione tanto quanto lo è un array. Al massimo sono astrazioni più complicate.

Gli array non esistono in hardware, a meno che l'hardware non supporti il concetto di array :-) (evviva la tautologia!)

Per indicizzare un array devi prendere l'indirizzo dove inizia l'array, sommarci l'indice moltiplicato per la dimensione in parole indirizzabili del tipo di dato di ogni elemento, e indirizzare il risultato.

Non so se 'sta roba che ho detto sia astratta o meno, ma mi sembra che lo sia né più né meno di quanto lo sarebbe l'equivalente per le liste o per gli alberi.

[snip]

Con un array monodimensionale è impossibile tenere traccia di oggetti su un piano bidimensionale. Il minimo possibile è usare una matrice che rappresenti la griglia, quindi un array bidimensionale. Ma non è efficiente ed il professore dice di non usarla.

[snip]

Non è così dispendiosa la cosa come puoi pensare quando si usano le reti con liste di adiacenza. Altrimenti non la userebbe nessuno.

Qui tu stavi rispondendo a due cose diverse, quindi perdonami se mettendole insieme ti faccio dire cose che non intendevi dire...

Però, per rappresentare un piano (o meglio il pezzo di piano che ti interessa), se usi una matrice bidimensionale butti via memoria in maniera crescente come x*y (x ed y sono le dimensioni del pezzo di piano); se usi una lista di adiacenza, invece, butti via memoria in maniera crescente come... circa 3*x*y (vertici più lati; in realtà è un pochino meno)!
Asintoticamente è la stessa cosa, ma di sicuro l'array è più compatto.

Ciò non significa che le liste di adiacenza siano cose inutili; ma le liste di adiacenza servono per grafi i cui vertici possono avere *un numero variabile di lati ciascuno*! Se invece, come nel nostro caso, ogni vertice ha lo stesso numero di lati (2 o 4 a seconda di come ti gira), asintoticamente usare un array o usare liste di adiacenza è uguale (sempre parlando di occupazione di memoria), e in pratica la costante nascosta è più grande nel caso delle liste di adiacenza.

In quanto all'efficienza in tempo, quella delle liste di adiacenza non può che essere minore o uguale a quella dell'array (sempre e solo nel nostro caso, e supponendo di non semplificare mai il grafo in nessun modo!).

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 18-02-2005 02:25:

Originally posted by wingzero
Sì, bhè, è un grafo orientato (digrafo = digraph dall'inglese = directed graph = grafo orientato), che è un modo per disegnare una rete con archi orientati.

Perché te la prendi su 'sta cosa dell'orientamento? ;-)
Ho detto anch'io che è orientato, però il grafo alla fine è un'astrazione che *tu* usi per rappresentare i cammini dall'automa al richiamo bla bla bla, quindi *tu* puoi decidere se usare un grafo orientato o no. Poi sono d'accordo che, usando un grafo, nel nostro caso sia molto saggio usarne uno orientato.

Il grosso problema sta nell'impostare la tortuosità che non so come usarla per calcolare la minore.

Guarda gli archi del tuo grafo... prendi un arco qualsiasi, scegli tu se "orizzontale" (collega due vertici con la stessa y) o "verticale" (stessa y). Supponiamo che ne hai scelto uno verticale: qual è la tortuosità minima con cui puoi raggiungerlo?
Be', a quell'arco o ci arrivi dall'arco verticale precedente, o ci arrivi dall'arco orizzontale precedente, ma in quel caso la tortuosità aumenta.

Mi fermo qui; basti dire che l'algoritmo basato su quello che ho detto per trovare la tortuosità minima con cui puoi raggiungere un arco può facilmente *non essere ricorsivo*, e avere una complessità funzione della distanza in orizzontale e in verticale dell'automa dal richiamo -- che sarebbe a dire che ha una complessità schifosa, dato che ci mette *sempre* più tempo a calcolare la tortuosità per automi lontani dal richiami, anche se non ci sono ostacoli di mezzo. Ma direi che è sempre meglio di niente, e soprattutto è molto meglio dell'algoritmo ricorsivo più ovvio che mi viene in mente (che consiste in: 'sti percorsi provali tutti e vedi qual è il migliore).

[QUOTE]
Ed ho problemi a programmare senza memory leak delle liste di adiacenza...

"Save the whales and free() the malloc()s", come scriveva uno nella sua firma :-P

non riuscirò mai a farle funzionare in tempo per la consegna.. e se anche ci riuscissi poi non saprei come usarle per risolvere il tutto al momento. Quindi ritengo di non essere in grado di consegnare, purtroppo per me.

Auguri. Neanch'io sono molto sicuro di riuscire a consegnare qualcosa di decente, se la cosa ti consola.
Ma se fossi in te il programma lo scriverei comunque, anche nella versione più lenta e stupida che ti viene in mente... sempre meglio che non consegnare, o no?

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by LjL on 18-02-2005 02:27:

Originally posted by wingzero
Puoi dirlo in caso di mappa priva da ostacoli magari, ma con gli ostacoli il discorso cambia perchè dei percorsi liberi bisognerà far scegliere all'automa quello con minore tortuosità.

Certo, ma comunque ci sarà sempre in tutti i casi (tranne nel caso peggiore) qualcosa nel grafo di semplificabile.
Il problema è che non so esattamente come eseguire 'sta semplificazione, ma è abbastanza evidente guardando un disegno qualsiasi (ad esempio quello del testo) che *deve* essere possibile una semplificazione.

Ciò non toglie che è comunque un grafo orientato.

Ok, ok, è un grafo orientato! ;-P

__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi

Posted by wingzero on 18-02-2005 08:57:

Originally posted by LjL
Guarda che una lista o un albero non sono in sé e per sé dei tipi di dati astratti.
Vedi: http://www.swif.uniba.it/lei/foldop...tract+data+type

A mio avviso poi una lista o un albero è un'astrazione tanto quanto lo è un array. Al massimo sono astrazioni più complicate.

Gli array non esistono in hardware, a meno che l'hardware non supporti il concetto di array :-) (evviva la tautologia!)

Per indicizzare un array devi prendere l'indirizzo dove inizia l'array, sommarci l'indice moltiplicato per la dimensione in parole indirizzabili del tipo di dato di ogni elemento, e indirizzare il risultato.

Non so se 'sta roba che ho detto sia astratta o meno, ma mi sembra che lo sia né più né meno di quanto lo sarebbe l'equivalente per le liste o per gli alberi.

http://www2.latech.edu/~box/ds/chap4.ppt

[url]http://en.wikibooks.org/wiki/Computer_Science

ata_Structures:Arrays [/url]

Arrays guarantee constant time read and write access, however many lookup operations (find min, find max, find index of an instance of an element) are O(n). Arrays are very efficient in most languages, as lookup and access operations compute the address of an element via a simple formula based on the base address element index.

Arrays typically map directly to contiguous storage locations within your computers memory and are therefore the "Natural" storage structure for most higher level languages.

Simple linear arrays are the basis for most of the other data structures. Many languages do not allow you to allocate any structure except an array, everything else must be implemented on top of the array. The exception is the linked list, that is typically implemented as individually allocated objects, but it is possible to implement a linked list within an array.

Posted by Skilotto83 on 18-02-2005 09:54:

se continuo cosi' butto ore per ripondere ai post...
Kmq mi sembra che wingzero sia abbastanza diffidente sulla mia soluzione mentre ljl ha capito il funzionamento e le motivazioni della mia idea di usare array....
kmq quando aggiungo un elemento devo effettivamente far scalare tutte le posizioni in basso di uno, a meno che l'automa debba essere gia' messo in cima alla lista...
Per la questione di come so la struttura dell'ostacolo....vi garantisko ke ho risolto...
se mi scontro su un ostacolo nell'asse x scorro la x finche nn ho piuu' l'ostacolo...lo stesso la y...
Nn vedo il problema...basta gestire la ovrapposizione degli ostacoli....
---------
| |
| | <---------------
---------

in un esempio simile io sbatto sulla parte y..mi basta scorrere y finchè nn è finita...e lo so per coordinate di vertici..analiticamente, in quanto nn ho inserito tutte le celle dell'ostacolo, ma solo i vertici...nn mi devo assolutamente preokkupare della profondita' di tale ostacolo...ragazzi, io ancora nn ho una versione precisissima, ma funziona...è solo questione di capire cosa si ha davanti e quindi deviare il percorso senza sbatterci tutte le volte....
All'inizio avevo pensato di fare una roba tipo che se sbatto su una serie di celle e da li capisco che nn trovo il percorso, le celle le segno come inutili, e quindi nei successivi tentativi nn le considero neanke...dovrebbe essere simile al backtracking..ma kmq nn si hanno miglioramenti notevoli rispetto a una ricerca esaustiva brute force...

Posted by Skilotto83 on 18-02-2005 10:09:

il disegno è venuto male....boh...
kmq è logico che la pate dove sbatto è inizio ostacolo e nn all'interno...

X LJL...

La storia della lunghezza del nome si risolve on una strlen, data questa poi alloco spazio per il nome...questo nella funzione...
In main invece devo usare le realloc per forza...quando leggo da tastiera nn posso farci nulla...
Secondo...uso una strcmp per ordinare i nomi...
Ragazzi..la soluzione magari nn è la migliore...ma mi risulta comoda primo perchè uso la stessa sia per automi che per ostacoli...e questo porta ad una semplicita' mdi lettura del codice...
e secondo perkè kosi' sembra ke mi venga la tortuosita' e il percorso libero....
Certo che se mi avanza tempo e utto funziona cerkero' di inserire automi in un alberello...
Ma gliu ostacoli nn si tokkano..sono in un array e vanno da power cosi'...

Posted by mark on 18-02-2005 11:20:

i risultati del prof, mostrano che per l'automa (00) non esiste il percorso

e 12 11 00

a me invece pare proprio che esiste ed è di 36 passi

boh

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Posted by mattcobain on 18-02-2005 11:33:

ragazzi sono emozionato...ho finito!!!!! :ola: almeno il codice....ora c'è da fare la relazione, i costi, le prestazioni.....però il grosso è andato.....
io direi, per gli altri che hanno finito, perché non facciamo qualche prova con determinati input dati da noi e confrontiamo i risultati...sarebbe una verifica in più oltre all'output del prof....c'è qualcuno che ci sta?!

All times are GMT. The time now is 22:54.

Pages (33): « First ... « 13 14 15 16 [17] 18 19 20 21 » ... Last »
Show all 482 posts from this thread on one page