 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
Progetto Febbraio
Clicca QUI per vedere il messaggio nel forum |
| Kuzzi |
Buongiorno a tutti,
sono arrivato al punto in cui ho un albero che contiene tutte le triplette (uomo,donna,affinità) relative ad un determinato giorno,ora secondo quanto definito dalla funzione festa, dovrei selezionare le n con affinità minore (escludendo i duplicati) e con queste creare i gruppi.
Il problema è che non so come costruire il grafo a partire dall'albero.
Devo usare una lista di appoggio?
Ogni suggerimento è ben accetto :)
Grazie |
| CowBoy |
Originally posted by CowBoy
I nodi del grafo devono essere numerati partendo da 1, in maniera progressiva, quindi ti serve un quarto elemento (es ID) associato ad ogni uomo e donna.
Originally posted by CowBoy
Prova ad implementare un grafo con liste di adiacenza Qui trovi il codice necessario per le strutture dati. Cerca di capire a cosa servono, il copia/incolla ossessivo ti creerà solo problemi.
Originally posted by CowBoy
Come vertici metti tutti i partecipanti alla cena, e poi collega il benefattore alla popolana affine con un arco di peso = affinità.
|
| Miran |
volta costruito il grafo come detto come li costruisco i gruppi?
spero in un vostro aiuto ^_^
Grazie |
| CowBoy |
Premesso che non mi sono interessato del testo del progetto, ho solo un idea parziale di quello che si chiede. La mia opinione è di riportare le liste di adiacenza per ogni "benefattore" ed analizzarle... se non ci sono "archi" allora è un benefattore sfortunato che si godrà la cena, altrimenti per ogni coppia di vertici(benefattore, popolana) si esegue un qualche algoritmo FIND-UNION(nel momento in cui due insiemi hanno un nodo in comune allora si uniscono in un'unico grande insieme, formando il gruppo).
Per maggiori informazioni, a titolo d'esempio, vedi l'algoritmo di Kruskal. |
| Magio |
| per le stanze si usa un dfs, ma per coppie separate voi cosa volete/pensate du usare? |
| CowBoy |
NUOVO AVVISO: http://lonati.dsi.unimi.it/algo/1011/?page=avvisi
25 febbraio 2011
A proposito della operazione "coppie_separate", nella traccia si richiede di individuare un'insieme massimale di coppie e si specifica, nel caso in cui esista più di un insieme massimale, di scegliere quello con discrepanza complessiva minore. Ci siamo accorti che quest ultimo vincolo (introdotto per rendere la soluzione unica) rende in realtà il problema molto più complesso! Pertanto correggiamo la specifica: non si deve considerare il vincolo sulla disparità, ovvero basta trovare uno qualsiasi degli insiemi massimali di coppie. Nell'esempio 4, quindi, sono accettabili entrambi gli insiemi citati. |
| CowBoy |
Originally posted by Magio
per le stanze si usa un dfs, ma per coppie separate voi cosa volete/pensate du usare?
Ci sono alcuni casi dove DFS non ti da risultati oppure te ne da troppi rispetto alla soluzione globale, fate attenzione ai grafi non connessi.
Il problema delle coppie assomiglia un po al problema della sotto stringa massima. Se volete provate a ragionarci su, dando alle popolate il simbolo del benefattore collegato, creando così due vettori("benefattori" e "popolane con benefattore") di records o di puntatori a intero... |
| Magio |
| Piu che un lcs che non credo funzioni molto cè il problema del matrimonio stabile che credo opportunamente modificato sia più utile ma nemmeno qui sò se sia una buona idea |
| darkman13 |
| Ciao, qualcuno potrebbe postare il progetto risolto, grazie! |
| picchio |
Originally posted by Chobeat
io adesso sono riuscito a fare tutto con gli alberi rb, l'unico problema è che non si porta dietro le info del nodo ma solo la key. sarà qualche problema di puntatori.
Parlando col Prof. sembra che la scelta dell' albero RB come str. dati di base per contenere i vari invitati sia quella più giusta, anche se dice che in generale andavano bene anche le tab. HASH. Per quanto riguarda invece l' ordinamento, anzichè convertire la stringa in un numero con la funz. che Cowboy suggerisce (che peraltro funziona alla grande!) si poteva secondo il Prof. semplicemente usare la funz. di libreria "strcmp". Dice che essa introduce un ordinamento di tipo lessicografico, sufficiente per avere un albero RB ...Non so voi, ma io non ci sarei mai arrivato ... Per quanto riguarda invece l' ultimo quesito "coppie" ebbene la migliore str. dati era il grafo bipartito, poichè il testo chiede la "coppia" che massimizza ... Sul Cormen (ed1) ho visto che c'è proprio un paragrafo che tratta dell' argomento 27.3 "Abbinamento massimo in un grafo bipartito". Anche su questo non ci sarei mai arrivato...del resto non so se Torelli abbia mai spiegato i grafi bipartiti ?! |
|
|
|
|
