[Algoritmi, Java] - Soluzione problema tramite algoritmo

[DTaffuri]

Ciao a tutti, in un recente concorso pubblico che ho fatto è uscito come traccia la progettazione dell'algoritmo con la traccia che posterò di seguito. Avevo pensato ad un approccio brute force enumerando tutte le soluzioni valide per poi raffinarlo tramite soluzione approssimata ma più efficiente. Il problema è che non sono riuscito proprio a trovare la soluzione per nessuno dei punti elencati. Idee di risoluzione?

Traccia:

Una coppia invita al ricevimento N persone da distribuire su K tavoli nel modo migliore possibile, tenendo conto della reciproca affinità. Assumendo che a ciascun tavolo possano sedersi un numero minimo e massimo di invitati e che l'affinità reciproca tra due invitati sia nota ed espressa da un numero intero (anche negativo), il candidato:

1 - Descriva l'algoritmo più appropriato a determinare la disposizione che massimizza l'affinità complessiva, intesa come somma delle affinità presenti allo stesso tavolo.

2 - Indichi la struttura dati più adeguata ad eseguire l'algoritmo.

3 - Esprima la complessità dell'algoritmo, motivandola

4 - Descriva un algoritmo a complessità inferiore che consenta di determinare una soluzione sub ottimale in tempo minore.

[apatriarca]

Partiamo dall'idea di usare un approccio brute force. Quali sono gli input e output dell'esercizio? Riesci a scrivere degli esempi di input e calcolare a mano qualche output? Che approccio hai usato per calcolare tali risultati? Riesci a pensare ad un modo per applicare tale approccio in codice?

Testo nascosto, fai click qui per vederlo

Se non hai alcuna idea puoi provare a pensare a come calcolare tutte le disposizioni e l'affinità totale per ogni disposizione. La soluzione si può a quel punto calcolare trovando il massimo.

[apatriarca]

Vorrei comunque aggiungere che non si tratta di un problema semplice. Rientra infatti nella classe di problemi NP. L'algoritmo brute force è abbastanza fattibile, ma il quarto punto richiede probabilmente di aver già visto qualche algoritmo simile.

[DTaffuri]

Allora, ho pensato ad un grafo come struttura dati per rappresentare tutte le relazioni, con il peso di ogni arco che indica l'affinità. Il grafo ovviamente è non orientato.

Input: grafo che rappresenta le relazioni, numero di persone, numeri di tavoli, numero min e max di persone al tavolo.

Output: Disposizione delle n persone ai k tavoli che massimizza l'affinità (somma di tutte le affinità di ogni tavolo)

Non sono purtroppo riuscito a cavarne nulla nemmeno considerando un esempio concreto. Non riesco a definire un processo specifico per ottenere ciò che vuole l'algoritmo, anche considerando poche persone e pochi tavoli

[apatriarca]

Siccome il grafo è completo puoi semplicemente memorizzarlo come una matrice di dimensione \( N \times N \). Come output puoi semplicemente avere un array che associa ad ogni persona il tavolo a cui è stato assegnato.

Un'idea per il brute force potrebbe essere la seguente:
1. Generare tutte le possibili dimensioni dei tavoli. Se hai ad esempio 20 persone e 4 tavoli di dimensione variabile tra 4 e 6 persone hai le possibili dimensioni: (6 6 4 4), (6 5 5 4) e (5 5 5 5). Nota che li ho ordinati per dimensione perché se scambi due tavoli ottieni la stessa affinità.
2. Per ogni dimensione e ogni tavolo considerare tutte le possibili estrazioni di persone con gruppi uguali alle dimensioni dei tavoli.
3. Per ogni estrazione calcolare l'affinità e memorizzare il massimo trovato.

La complessità non è facilissima da calcolare per cui potrebbe valer la pena di fare delle semplificazioni e andare per eccesso. La complessità sarà comunque nell'ordine di \(N!\) probabilmente.

Si tratta di un problema di graph partitioning in ogni caso ed esistono algoritmi per trovare soluzioni sub-ottimali. La soluzione del punto 4 consiste quindi nel reiventarne uno di questi...

[apatriarca]

Nota che il numero di disposizioni da provare è proibitivo anche per numeri molto piccoli e in effetti se hai mai organizzato o visto organizzare un evento come un matrimonio il metodo per la soddivisione dei tavoli è decisamente diverso.

In una situazione reale sfruttiamo il fatto che esistono gruppi di persone in questi eventi come famiglie o gruppi di amici che hanno una affinità molto più alta tra di loro rispetto a quella che hanno con gli altri. Questi gruppi vengono quindi poi uniti o divisi per ottenere i tavoli. Non so quanto sia aplicabile al caso generico però perché questa struttura "gerarchica" che troviamo spesso nelle reti sociali potrebbe non essere applicabile all'input.

Una volta scelta una disposizione è poi sempre possibile cercare di migliorarla. Possiamo per esempio considerare due persone e scambiarle nei tavoli. Se le affinità di queste persone nei nuovi tavoli crescono allora avremo una nuova disposizione migliore della precedente. Se non è possibile applicare questo o altri metodi per migliore l'affinità totale saremo arrivati ad un massimo locale. Questo è probabilmente un altro possibile spunto per il quarto punto.

[DTaffuri]

Io penso che alla traccia non interessi che il numero sia proibitivo, infatti il 4 punto serve proprio per creare un algoritmo a complessità inferiore che produca una soluzione non ottimale ma che venga eseguito in tempi accettabili. Per l'algoritmo che deve produrre la soluzione ottimale, invece, non c'è altra via che calcolare tutte le possibili disposizioni con la rispettiva affinità e prendere la disposizione con affinità massima come soluzione