Algoritmi di ordinamento basati sul nome per lettere comuni massimizzate

4

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!

    
posta Nick 13.01.2016 - 19:01
fonte

1 risposta

3

Un'euristica che vale la pena considerare:

  1. Scegli un nome casuale e aggiungilo a un gruppo.
  2. Scansiona i nomi rimanenti per la corrispondenza del punto più alto e aggiungilo al gruppo.
  3. Scansiona i nomi rimanenti per la corrispondenza del punteggio totale più alta rispetto ai due nomi raggruppati e aggiungilo al gruppo.
  4. Scansiona i nomi rimanenti per la corrispondenza del punteggio totale più alta rispetto ai tre nomi raggruppati e aggiungilo al gruppo.
  5. Ripeti per completare i restanti gruppi.

Il risultato probabilmente mancherebbe di alcune partite eccellenti perché i suoi membri si sarebbero abbinati prematuramente agli altri. Tuttavia, potrebbe essere un buon stato di partenza per i metodi stocastici.

Un ulteriore arricchimento potrebbe essere pre-calcolare "distanze" tra tutti i nomi. Sono 12.500.000 misurazioni: molto, ma fattibile. Ordina le misure e inizia il processo sopra con la migliore corrispondenza.

Il pensiero finale è k-means clustering . Potremmo pensare ai nomi come punti in 26 dimensioni dello spazio euclideo. Questa è una dimensione per personaggio. Ogni personaggio è una "unità" lungo quella dimensione. "Aaron" è due unità lungo l'asse A , zero unità lungo B , zero lungo C , ecc. 1 lungo R ... Pertanto, condivide un punto con "Roana", è piuttosto vicino a "Rona", ma non è vicino a "Ziggy". (Questo non è un modo perfetto per misurare. Ad esempio, "Ziggy" non è più vicino o più vicino a "Aaron" di "Tim", ma il nostro layout euclideo lo suggerisce. Dovrò pensare un po 'di più it ...)

True k-means è impossibile con una complessità di O (n dk + 1 logn) [d == dimensions (26), k == conteggio cluster (1250)] Ouch. Tuttavia, concettualizzare come punti nello spazio sembra utile. Esistono tutti i tipi di trucchi che puoi provare con ricerca per il vicinato più vicino .

    
risposta data 15.01.2016 - 07:12
fonte

Leggi altre domande sui tag