 |
 desrob |
| ma xkè liste di liste quando si può fare solo un ... |
15-09-2005 22:26 |
|
 |
desrob |
.fedelissimo.
Registered: May 2004
Posts: 55 (0.01 al dì)
Location:
Corso: informatica
Anno: terzo
Time Online: 1 Day, 6:49:59 [...]
Status: Offline
Edit | Report | IP: Logged |
ma xkè liste di liste quando si può fare solo una semplice lista koncatenata! le tabelle hash e gli alberi RB li eliminio a priori visto ke sono troppo incasinati , se vuoi avete altre idee potete postarle visto ke le mie scarseggiano !! tnx
|
|
15-09-2005 22:26 |
|
|
| |
|
| maynard80 |
| più che altro come ordini la lista e soprattutto ... |
15-09-2005 22:31 |
|
|
maynard80 |
.novellino.
Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline
Edit | Report | IP: Logged |
più che altro come ordini la lista e soprattutto poi la devi sempre scorrere tutta.... a livello di ottimizzazione fa un po pena.... certo anche io sono abbastanza imbranato, ma se ci riesco a fare qualcosa di buono meglio. Meglio non scartare a priori una soluzione perchè "incasinata", è vero che è + dura da implementare, ma è sicuramente + efficiente
__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !
|
|
15-09-2005 22:31 |
|
|
| |
|
| desrob |
| l'importante è ke il programma funzioni, poi se f ... |
15-09-2005 22:36 |
|
|
desrob |
.fedelissimo.
Registered: May 2004
Posts: 55 (0.01 al dì)
Location:
Corso: informatica
Anno: terzo
Time Online: 1 Day, 6:49:59 [...]
Status: Offline
Edit | Report | IP: Logged |
l'importante è ke il programma funzioni, poi se funziona bene è meglio ! ma scegliere gli alberi RB è un suicidio, fattelo dire ..poi puoi fare quello ke vuoi !!!!
|
|
15-09-2005 22:36 |
|
|
| |
|
| Frigging |
| Un Inserimento in O(1) per una lista e' minore di ... |
16-09-2005 00:16 |
|
|
Frigging |
.primate.
Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline
Edit | Report | IP: Logged |
Un Inserimento in O(1) per una lista e' minore di un inserimento in un RB O(lgn), ma una ricerca in un RB O(lgn) e' minore che in una lista O(n^2)... di conseguenza dipende da cosa ci si deve fare...
Gli RB alberi implementati (senza accessori  ) vengono sulle 500 righe di codice (commenti abbondanti inclusi).
Senza operazione di JoinRB.
Io escluderei cmq le tabelle hash, tries & company.
Rimangono in gioco:
- LISTE
- ALBERI
Cmq sono dell'idea che l'implementazione piu' difficile da ottimizzare e' quella della determinazione dei campi. Troppo dispendiosa... Secondo me si puo' fare di meglio di O(n^2).
Voi cosa avete pensato per determinare i campi?
|
|
16-09-2005 00:16 |
|
|
| |
|
| Jaco |
| A questo giro ci sono anch'io.Anch'io avevo pensat ... |
16-09-2005 00:31 |
|
|
Jaco |
.novellino.
Registered: Jun 2004
Posts: 4 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: 2...3
Time Online: 0:44:10 [...]
Status: Offline
Edit | Report | IP: Logged |
A questo giro ci sono anch'io.Anch'io avevo pensato a delle liste di puntatori oppure tabelle hash,ma dagli altri progetti tutti hanno sempre usato liste o alberi e questo non mi sembra troppo diverso.
|
|
16-09-2005 00:31 |
|
|
| |
|
| Frigging |
| ma perche' avevate pensato alle tabelle hash? ... |
16-09-2005 00:50 |
|
|
Frigging |
.primate.
Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline
Edit | Report | IP: Logged |
ma perche' avevate pensato alle tabelle hash?
|
|
16-09-2005 00:50 |
|
|
| |
|
| livio_82 |
| Ok, dopo aver letto tutti i vostri commenti, ora m ... |
16-09-2005 03:14 |
|
|
livio_82 |
.bgp
Registered: Feb 2003
Posts: 241 (0.03 al dì)
Location: Predore
Corso: informatica F49
Anno: Trentasettesimo
Time Online: 1 Day, 16:57:17 [...]
Status: Offline
Edit | Report | IP: Logged |
Ok, dopo aver letto tutti i vostri commenti, ora mi posso concedere la lettura del testo
Spero che la notte fonda mi aiuti nella comprensione.
Alea iacta est!
__________________
Livio
** Pone seram, cohibe, sed quis custodiet ipsos custodes? Cauta est et ab illis incipit uxor. **
www
|
|
16-09-2005 03:14 |
|
|
| |
|
| drakend |
| Con un albero RB come pensate di calcolare il camm ... |
16-09-2005 05:42 |
|
|
drakend |
.grande:maestro.
Registered: Oct 2002
Posts: 1857 (0.22 al dì)
Location:
Corso:
Anno:
Time Online: 11 Days, 16:15:18 [...]
Status: Offline
Edit | Report | IP: Logged |
Con un albero RB come pensate di calcolare il cammino massimo?
|
|
16-09-2005 05:42 |
|
|
| |
|
| Frigging |
| Per cosa vorresti calcolare il cammino massimo? Qu ... |
16-09-2005 07:36 |
|
|
Frigging |
.primate.
Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline
Edit | Report | IP: Logged |
Per cosa vorresti calcolare il cammino massimo? Quello di peso massimo?
Anch'io son daccordo che l'rb per quello non ve bene.
Last edited by Frigging on 16-09-2005 at 10:23
|
|
16-09-2005 07:36 |
|
|
| |
|
| maynard80 |
| [QUOTE][i]Originally posted by drakend [/i]
... |
16-09-2005 07:36 |
|
|
maynard80 |
.novellino.
Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by drakend
Con un albero RB come pensate di calcolare il cammino massimo?
è proprio questo che non so fare, inizialmente avevo pensato ad un albero RB come struttura del piano, ma ora che devo pensare al calcolo del cammino massimo non saprei cosa utilizzare...
__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !
|
|
16-09-2005 07:36 |
|
|
| |
|
| Paolo74GRS |
| Ma secondo voi, per quanto riguarda la funzione di ... |
16-09-2005 11:23 |
|
|
Paolo74GRS |
.primate.
Registered: Mar 2003
Posts: 71 (0.01 al dì)
Location: Bergamo
Corso: Informatica
Anno: > 3
Time Online: 2 Days, 11:55:02: [...]
Status: Offline
Edit | Report | IP: Logged |
Ma secondo voi, per quanto riguarda la funzione di inserimento nuovo piano (function "i"), va fatto il controllo sul fatto che il piano che sto inserendo ed il file che vado ad utilizzare considerano lo stesso numero di punti=fiori?
..oppure considero non possibile il caso errato?
|
|
16-09-2005 11:23 |
|
|
| |
|
| maynard80 |
| [QUOTE][i]Originally posted by Frigging [/i]
... |
16-09-2005 12:50 |
|
|
maynard80 |
.novellino.
Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by Frigging
Per cosa vorresti calcolare il cammino massimo? Quello di peso massimo?
Anch'io son daccordo che l'rb per quello non ve bene.
beh invece dovrebbe essere possibile applicare un algoritmo di calcolo del cammino PESATO indipendentemente dalla struttura dati utilizzata, per questo la lista è una cacchiata con la sua complessità n^2 contro l'albero con complessità log(n).
__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !
|
|
16-09-2005 12:50 |
|
|
| |
|
| Frigging |
| [QUOTE][i]Originally posted by maynard80 [/i]
... |
16-09-2005 12:58 |
|
|
Frigging |
.primate.
Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by maynard80
beh invece dovrebbe essere possibile applicare un algoritmo di calcolo del cammino PESATO indipendentemente dalla struttura dati utilizzata, per questo la lista è una cacchiata con la sua complessità n^2 contro l'albero con complessità log(n).
Se usi un albero rb come fai a mantenere la proprieta' di connessione tra un pto(x0,y0)e un punto(x1,y0) ad esempio?
Se usi l'rb che criterio di ordinamento di key vai a usare? E soprattutto si puo' muovere in 3 direzioni e non solo due .. di conseguenza l'albero binario non lo vedo giusto...
che ne pensi?
Meglio un albero normale...
Per quello chiedevo a cosa serviva l'rb se e' per il peso allora non va bene secondo me...
Mah adesso cmq ci penso un po su... se si puo' usare anche per la determinazione del cammino di peso massimo.
|
|
16-09-2005 12:58 |
|
|
| |
|
| maynard80 |
| [QUOTE][i]Originally posted by Frigging [/i]
... |
16-09-2005 13:59 |
|
|
maynard80 |
.novellino.
Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by Frigging
Se usi un albero rb come fai a mantenere la proprieta' di connessione tra un pto(x0,y0)e un punto(x1,y0) ad esempio?
Se usi l'rb che criterio di ordinamento di key vai a usare? E soprattutto si puo' muovere in 3 direzioni e non solo due .. di conseguenza l'albero binario non lo vedo giusto...
che ne pensi?
Meglio un albero normale...
Per quello chiedevo a cosa serviva l'rb se e' per il peso allora non va bene secondo me...
Mah adesso cmq ci penso un po su... se si puo' usare anche per la determinazione del cammino di peso massimo.
non capisco, la struttura dati è indipendente da queste cose, i nodi sono ordinati in base alla chiave (x,y) se un nodo non esiste non esiste il rispettivo fiore.
quando scorri l'albero per trovare il cammino sarà li e solo li che tra i parametri del cammino dici che sono permessi alcuni spostamenti (3 spostamenti) e memorizzi il percorso in una struttura di supporto dove andrà a finire solo il cammino prescelto.
ogni ricerca sarà sempre + veloce che in una lista ed esaminerà ricorsivamente i percorsi possibili restituendo quello migliore.
non deve in alcun modo interessare che il grafo sia costruito in base ai percorsi possibili, ma che sia efficiente.
__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !
|
|
16-09-2005 13:59 |
|
|
| |
|
| Frigging |
| [QUOTE][i]Originally posted by maynard80 [/i]
... |
16-09-2005 14:08 |
|
|
Frigging |
.primate.
Registered: Mar 2005
Posts: 69 (0.01 al dì)
Location:
Corso: Informatica
Anno:
Time Online: 8:27:03: [...]
Status: Offline
Edit | Report | IP: Logged |
Originally posted by maynard80
non capisco, la struttura dati è indipendente da queste cose, i nodi sono ordinati in base alla chiave (x,y) se un nodo non esiste non esiste il rispettivo fiore.
quando scorri l'albero per trovare il cammino sarà li e solo li che tra i parametri del cammino dici che sono permessi alcuni spostamenti (3 spostamenti) e memorizzi il percorso in una struttura di supporto dove andrà a finire solo il cammino prescelto.
ogni ricerca sarà sempre + veloce che in una lista ed esaminerà ricorsivamente i percorsi possibili restituendo quello migliore.
non deve in alcun modo interessare che il grafo sia costruito in base ai percorsi possibili, ma che sia efficiente.
Avevo capito che la struttura la usavi in modo diverso. Sorry!
|
|
16-09-2005 14:08 |
|
|
| |
|
| All times are GMT. The time now is 02:37. |
|
|
 |
|
 |
|
|
| |
Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
|
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
|
|
|
|
|
|
desrob
