Sto tentando di scrivere un programma per una competizione (siamo autorizzati a consultare Stack Exchange, a patto che non mi venga dato un codice fisico) che includa un elenco di 5000 nomi di persone (distribuiti abbastanza uniformemente dalla A alla Z, ma sono veri nomi - non stringhe di caratteri casuali, e ogni nome è unico) e ordina questa lista di persone in "stanze" di esattamente 4 persone ciascuna, con ogni persona collocata esattamente in una sola stanza (non può riutilizzare nomi, non può omettere nomi ).
Ogni "soluzione" è composta da 1250 di tali stanze (la memorizzo in un array 2d e sto usando java), e il "punteggio" della soluzione è definito come la somma del punteggio di ogni stanza, dove il punteggio della stanza è il numero di lettere comuni detenute in ciascuno dei 4 nomi di persone. Una determinata lettera viene conteggiata più di una volta se appare esattamente tante volte nel nome di ciascuna persona.
Ho iniziato con gli algoritmi che hanno semplicemente collocato i nomi in stanze casuali solo per testare le acque e vedere quale potrebbe essere il punteggio minimo dei punteggi (circa 650). Ho quindi provato a fare una semplice lista alfabetica della lista contenente i nomi (usando Collections.sort ()), che ha migliorato notevolmente il punteggio (circa 3800), ma aveva ancora un po 'di margine di miglioramento.
Il mio ultimo algoritmo è stato una versione leggermente modificata della ricottura simulata, in cui inizio con la lista ordinata alfabeticamente e cambio continuamente due persone da due stanze (selezionando due numeri di camera casuali e due indici casuali nelle stanze). All'interno di ogni iterazione di livello esterno, aggiorno la temperatura di annealing e conduco una ricerca di loop interno di 1000 iterazioni (alla temperatura del loop esterno) dove ottengo 1000 swap casuali, scelgo quello migliore (nessuna selezione di probabilità di temperatura nel loop interno ), e usa quello nel ciclo esterno, accettandolo come la nuova soluzione se il suo punteggio è più alto e accettandolo con una certa probabilità se è inferiore.
Questo approccio SA mi ha ottenuto un punteggio nei 6000 bassi e funziona abbastanza rapidamente, ma sembra essersi asintomato. Ci sono altri algoritmi o ottimizzazioni che dovrei prendere in considerazione? Dovrei allontanarmi da un approccio stocastico e cercare approcci di costruzione che facciano uso della natura alfabetica delle parole stesse? Grazie!