Jagged Array

venerdì 12 dicembre 2008 - 16.14

Elenco Threads

Stanze Forum

Aggiungi ai Preferiti

Cerca nel forum

Lechter Profilo | Newbie

29 messaggi | Data Invio: ven 12 dic 2008 - 16:14

salve a tutti,
ho un array jagged di n righe, ognuna composta da un numero differente di elementi.
tutti gli elementi sono interi e rappresentano un id di un utente su una tabella sql server 2005.
Ora, il primo elemento di ogni riga dell'array è l'id di un utente, e tutti gli altri elementi sulla stessa riga sono gli id degli utenti "amici".

quindi potrebbe essere così (1, 3, 6, 11),(3, 1, 7)

l'utente 1 è amico di 3, 6, 11, e l'utente 3 è amico di 1 e 7.

Il problema è ricercare tutti i percorsi possibili che legano un utente ad un'altro selezionato, per esempio in questo aray per andare dall'utente 1 all'utente 7 il percorso è 1,3,7.

ci sono due problemi: i cicli infiniti (siccome 1 è amico di 3 ma anche viceversa) e il salvare tutti i percorsi possibili scorrendo quindi ogni possibile percorso di questo array.

Potete autarmi? è ore che ci sbatto la testa ma niente...

luigidibiasi Profilo | Guru

1.077 messaggi | Data Invio: ven 12 dic 2008 - 23:06

Ciao,

forse ti converrebbe utilizzare i grafi per rappresentare i collegamenti tra i vari amici (in questo caso grafi non orientati) e successivamente implementarti gli algoritmi di visita per stamparti i percorsi che cerchi. Non sò se .NET abbia queste strutture già pronte (se ci sono meglio così risparmi molto tempo)

Nei corsi di laurea fanno implementare una struttura che rappresenta un grafo non orientato (generalmente in java ma credo che ci metterai 5 minuti a tradurla in Vb o C#) quindi cercando in rete puoi trovartela bella e pronta (risparmiando un mucchio di tempo) per l'utilizzo.

Generalmente poi fanno implementare anche tutti gli algoritmi per lavorarci sopra quindi con una attenta ricerca puoi trovarti tutto.

Nel caso non riuscissi a trovare niente ti posto dei link che potrebbero risultarti utili :

http://www.di.unito.it/~horvath/Didattica/Alg&Lab_0607/lez33-grafi_visite.pdf
http://www.dia.unisa.it/professori/debonis/debonis1/LASD08-09/Lezioni.htm

Tieni presente che il problema che stai affrontando ( già la parola cicli la dice lunga ) non è affatto banale quindi non prendere a testate il PC

Luigi Di Biasi
http://blogs.dotnethell.it/luigidibiasi/

Lechter Profilo | Newbie

29 messaggi | Data Invio: lun 15 dic 2008 - 09:27

ormai ho un'array così e non posso stare a ricodificare e ripensare il tutto

idee please?

luigidibiasi Profilo | Guru

1.077 messaggi | Data Invio: lun 15 dic 2008 - 09:36

E' dura

Se trovo qualcosa te lo posto

Luigi Di Biasi
http://blogs.dotnethell.it/luigidibiasi/

Lechter Profilo | Newbie

29 messaggi | Data Invio: lun 15 dic 2008 - 09:38

si che è dura cavolo, è giorni che ci sbatto contro la testa ma niente...

luigidibiasi Profilo | Guru

1.077 messaggi | Data Invio: lun 15 dic 2008 - 09:45

può capitare anche una situazione del genere?

(1, 3, 5, 6) (3,7,9) (3,10,11)

con 3,9 amici di 3 e 10,11 amici di tre scritti in array diversi oppure tutti gli amici di 3 saranno nello stesso array?
(3,7,9,10,11) ?

Luigi Di Biasi
http://blogs.dotnethell.it/luigidibiasi/

Lechter Profilo | Newbie

29 messaggi | Data Invio: lun 15 dic 2008 - 09:47

no questo lo escludo, una riga per utente coi suoi amici e non più righe per uno stesso utente...

Lechter Profilo | Newbie

29 messaggi | Data Invio: lun 15 dic 2008 - 11:16

niente, non riesco proprio a venirne a capo...cavolo...

luigidibiasi Profilo | Guru

1.077 messaggi | Data Invio: lun 15 dic 2008 - 11:28

Stasera cerco di inviarti le classi albero e gli algoritmi che ho usato io in passato per risovlere problemi del genere.

Con gli array non credo sia possibile a meno di algoritmi bruteforce.....
Luigi Di Biasi
http://blogs.dotnethell.it/luigidibiasi/

Lechter Profilo | Newbie

29 messaggi | Data Invio: lun 15 dic 2008 - 11:30

eh...credo che coi grafi, nodi e archi sia tutto più semplice, così mi sto bruciando il cervello...se qualcuno comunque sapesse come farlo così con gli array è il benvenuto!

Lechter Profilo | Newbie

29 messaggi | Data Invio: lun 15 dic 2008 - 11:41

e poi il mio non è un albero ma è un grafo!

Lechter Profilo | Newbie

29 messaggi | Data Invio: lun 15 dic 2008 - 12:00

rendiamolo per un attimo più semplice:

partendo dal presupposto che per trovare tutti i percosi possibili tra un nodo ed un altro devo scorrere TUTTI i percorsi dal nodo di partenza verso tutti i nodi collegati, supponiamo di voler solo trovare TUTTI i percorsi possibili partendo da un nodo qualsiasi...

così posso poi prendere SOLO quelli che terminano col nodo cercato, così forse è tutto più semplice...

luigidibiasi Profilo | Guru

1.077 messaggi | Data Invio: lun 15 dic 2008 - 12:19

Il problema sta nei cicli che, con gli array, al momento non ho idea di come gestirli.

Luigi Di Biasi
http://blogs.dotnethell.it/luigidibiasi/

aiedail92 Profilo | Expert

993 messaggi | Data Invio: mar 16 dic 2008 - 16:08

Ciao

Ti servono tutti i possibili percorsi, oppure solo il più rapido?

Luca

luigidibiasi Profilo | Guru

1.077 messaggi | Data Invio: mar 16 dic 2008 - 16:37

878_test.zip

Ho provato ad implementare al volo una classe per gestire una sorta di grafo generabile a partire dagli array jagged.

Ora dobbiamo solo implementare l'algoritmo giusto

Luigi Di Biasi
http://blogs.dotnethell.it/luigidibiasi/

Lechter Profilo | Newbie

29 messaggi | Data Invio: mar 16 dic 2008 - 16:43

allora ho quasi risolto, quando (e SE) finirò posterò il tutto e ti farò vedere la mia soluzione!

cmq ho fatto un ciclo for che scorre l'array nelle due direzioni, e per ogni elemento di una riga chiama una funzione ricorsiva che fa la stessa cosa, registrando il percorso in una stringa...non dovrebbe mancarmi molto.

Torna su

Stanze Forum

Elenco Threads

Partecipa anche tu! Registrati!

Hai bisogno di aiuto ?
Perchè non ti registri subito?

Dopo esserti registrato potrai chiedere
aiuto sul nostro Forum oppure aiutare gli altri

Consulta le Stanze disponibili.

Registrati ora !