È ora disponibile Luna park il settimo episodio della rubrica TAI.
Nell’attesa del prossimo esercizio e quindi l’editoria di questo vi invito a divertirvi cercando di risolverlo.
Dopo 2 esercizi più complessi abbiamo deciso di proporre un problema meno impegnativo.
Buon divertimento!!
Il prossimo esercizio \texttt{TAI} arriverà in leggero ritardo a causa della sessione d’esami che ha praticamente occupato tutto il tempo sia a me sia a @zJack1342 , nonostante ciò ritengo sia opportuno mostrare l’editorial di Luna Park.
L’esercizio chiede sostanzialmente: partendo da un grafo bidirezionale pesato formare K alberi in modo che la somma degli archi che li compongono sia massima possibile.
Partiamo analizzando il problema nel caso in cui K sia uguale a 1, in quest’istanza viene quindi chiesto di formare un unico albero con N nodi in modo che la somma degli archi sia massima. Questo problema è noto come \texttt{Maximum Spanning Tree}, che non è altro che una leggerissima modifica del più noto problema \texttt{Minimum Spanning Tree [MST] } del quale è presente anche un esercizio relativo sulla piattaforma: mst .
Per risolvere il problema del Minimum/Maximum Spanning Tree esistono principalmente 2 algoritmi: Prim’s Algorithm e Kruskal’s Algorithm. Entrambi utilizzando un approccio greedy; In certe istanze è più efficiente usare l’algoritmo di Prim (Quando il grafo è completo) in altre, come in questa l’algoritmo di Kruskal garantisce prestazioni migliori.
L’idea base dietro all’algoritmo di Kruskal è: ordinare gli archi in ordine decrescente (ricordo che cerchiamo il Maximum Spanning Tree) e partendo da quello con lunghezza maggiore, finendo con quello minore, prendere l’arco in questione solo se non forma un ciclo con gli archi già scelti precedentemente.
Ipotizzando di avere N nodi e M archi nel grafo iniziale.
Abbiamo visto come l’algoritmo di Kruskal permetta di trovare la somma massima degli archi che formano un solo albero, adattarlo a trovare la somma massima degli archi di K alberi è molto semplice.
Notiamo come ogni volta che l’algoritmo aggiunge un arco allo Spanning Tree diminuisce il numeri di componenti di 1, partendo da N componenti per arrivare, dopo aver aggiunto N-1 archi, ad 1 solo componente. Notiamo anche come gli archi aggiunti siano in ordine decrescente di peso.
Per adattare l’algoritmo basta quindi fermarsi quando si hanno K alberi rimasti.
Utilizzare la versione dell’algoritmo di Kruskal che ho appena descritto non permette però di ottenere punteggio pieno ( se ottimizzate veramente bene ottiene comunque 100/100 ). Per velocizzare la soluzione è fondamentale notare le assunzioni del problema che specificano: 1 \le W_i \le 1000.
Il fatto che gli archi abbiano lunghezze inferiori od uguali a mille ci permette di velocizzare la parte di ordinamento, per farlo è sufficiente utilizzare l’algoritmo di ordinamento: Counting Sort.
In questo modo per ordinare gli archi avremo complessità O(M) invece di O(MlogM) ed essendo il numero di archi elevato questa miglioria consente di velocizzare a sufficienza per ottenere punteggio pieno.
Luna Park è attualmente l’unico esercizio, insieme ad hasta a valere 1000 punti nonostante il fatto che l’abbiano risolto 20 persone sulle 23 che l’hanno provato e che delle 532 soluzioni inviate ben 202 siano corrette.
