Ho una matrice. Ho una lista di persone che devono occupare le celle n1, n2, n3 ecc., Un numero diverso di celle in file differenti. Devo posizionare le persone nelle celle. L'occupazione della stessa cella tra le righe viene considerata come sovrapposizione. La sovrapposizione deve essere ridotta al minimo.
Ho persone che si riferiscono a questo in modo diverso come un problema di ottimizzazione, un problema di allocazione e persino una programmazione lineare.
Devo prima ottenere un consenso su quale è questa classe di problema chiamata.
In secondo luogo, ho bisogno di sapere come dovrebbe essere una soluzione efficiente, in termini di notazione big-o o qualsiasi altra cosa.
Ecco un esempio:
C'è una scheda di 4 x 4 celle. Ci sono molti pezzi ciascuno di un colore (R, G, B). Ogni colore deve riempire un numero di colonne in ogni riga. Un possibile esempio:
Row1 Row2 Row3 Row4
Red 1 2 3 2
Blue 2 2 0 0
Green 1 0 1 2
Questo è l'input. La disposizione degli input potrebbe essere diversa ma occupa l'intera scheda ... nessuna cella è vuota.
Il conteggio degli stessi pezzi di colore che occupano una COLONNA dovrebbe essere ridotto al minimo. Una possibile (cattiva) disposizione basata sull'input è questa:
1 2 3 4
1 r b b g
2 r r b b
3 r r r g
4 r r g g
Questo è male perché in realtà massimizza il conteggio dei colori nella stessa colonna. Una disposizione migliore è la seguente:
1 2 3 4
1 r b b g
2 b r r b
3 g r r r
4 r g g r
La sovrapposizione è inevitabile, ma dovrebbe essere ridotta al minimo e in modo dimostrabile. Non so se c'è solo una soluzione migliore o se ci potrebbero essere molte soluzioni. Anche se ci potrebbero essere molte soluzioni, abbiamo bisogno di inventarne solo una.
Se ci penso di più, sembra una versione allentata del problema delle otto-queens. Mi sto preoccupando perché continuo a vedere la ricorsione e il back-tracking.
MODIFICA 1:
Sto pensando ad una versione rilassata della generazione di puzzle di sudoku.
