Assegnare le persone agli edifici rispettando le preferenze?

Question

Un amico mi ha fatto una domanda oggi su un problema di assegnazione. Ho trovato una soluzione abbastanza semplice, ma sento che può essere reso più semplice e veloce. Il tuo aiuto sarebbe apprezzato.

Il problema: Supponendo che ho N persone, ho bisogno di assegnarle in M edifici, ogni edificio può ospitare K persone. Non tutte le persone sono disposte a vivere l'una con l'altra, quindi ho una matrice di celle N * N e una 1 che segna le persone che sono disposte a vivere l'una con l'altra. Se una cella contiene 1 significa che io e J possiamo vivere insieme. Ovviamente la matrice è simmetrica attorno alla diagonale principale.

La mia soluzione è la seguente (pseudo codice):

int[] Match(int[] people, int[][] pairs, int numBuildings, int buildingsSize) 
{ 
    int[] freePeople = findFreePeople(people); 
    if(freePeople) = 0 
    { 
     return people; 
    } 

    foreach(int person in freePeople) 
    { 
     for(int buildingIndex=0 to numBuildings) 
     { 
      if(CheckIfPersonFitsInBuilding(...)) 
      { 
       int[] tempPeople = people.Copy(); 
       tempPeople[person] = buildingIndex; 
       int[] result = Match(tempPeople,pairs,numBuildings,buildingsSize); 
       if(result != null) 
       { 
        return result; 
       } 
      } 
     } 
    } 
    return null; 
} 

Ho appena coprono tutte le modalità possibili utilizzando la ricorsione. Sento che questo potrebbe essere ottimizzato molto, e non sto parlando di euristica, ma di una soluzione con una complessità molto minore.

1. C'è un problema formale ben noto che è simile a questo?
2. C'è un algoritmo migliore?

Penso che questo potrebbe essere correlato allo stable marriage problem, anche se non ne sono sicuro.

Answer 1

Questo problema è noto per essere NP-hard da una riduzione dal problema NP completo di decomposing a graph into cliques (il problema di copertura clique ).

In primo luogo, alcuni termini e discussioni. Un clique in un grafico è un insieme di k nodi diversi in modo tale che ciascun nodo è connesso l'un l'altro nodo nella cricca. Un independent set nel grafico è un insieme di k nodi diversi in modo tale che non vi siano due nodi collegati tra loro. Se si prende un grafico G e si introducono i bordi ogni volta che manca un bordo e si rimuovono tutti i bordi precedentemente esistenti, si ottiene complement graph del grafico originale. Ciò significa che il problema di trovare una cricca in un grafico iniziale equivale a trovare un insieme indipendente nel grafico del complemento.

Il motivo per cui questo è interessante è che nel problema che stai descrivendo, ti viene dato un grafico di persone in cui ogni spigolo indica "queste due persone non possono essere ospitate insieme". Di conseguenza, puoi pensare al problema che stai descrivendo cercando di trovare un modo per suddividere il grafico in sottografi k, ognuno dei quali è un insieme indipendente. Se costruisci il complemento di questo grafico, ottieni il grafico di tutte le persone che stanno bene insieme. In tal caso, si desidera suddividere il gruppo in k gruppi che sono tutti clique.

E 'noto che il seguente problema è NP-completo:

Dato un grafico e un numero k, si può rompere i nodi del grafo in disparte, in cricche k?

Possiamo ridurre questo problema al tuo problema in tempo polinomiale, dimostrando che il tuo problema è NP-difficile. La costruzione è semplice - dato il grafico iniziale G e il numero k, prima costruisci il complemento di G.Ciò significa che se si riesce a scomporre il complemento in k set indipendenti, allora il grafico originale G può essere suddiviso in k cliques (a causa della dualità tra cricche e insiemi indipendenti). Ora, prendi questo nuovo grafico e convertilo in un insieme di persone, uno per nodo, in cui due persone non possono essere collocate nella stessa stanza l'una con l'altra se i loro nodi sono stati collegati nel grafico originale. Ora, c'è un modo per distribuire queste persone in k case se il complemento di G può essere scomposto in k gruppi indipendenti se G può essere scomposto in k clique. Di conseguenza, il noto problema NP-completo della cover della cricca può essere ridotto al tuo problema in tempo polinomiale, quindi il tuo problema è NP-hard. Per garantire che qualsiasi set indipendente possa essere inserito in una casa, basta impostare la capacità massima di ogni stanza su n, il numero di nodi nel grafico. Ciò consente a qualsiasi set indipendente di essere ospitato in qualsiasi stanza.

Poiché il problema è NP-difficile, non può esserci una soluzione di tempo polinomiale a meno che P = NP. Di conseguenza, come meglio sa chiunque, non esiste un algoritmo del tempo polinomiale e la ricorsione del backtracking potrebbe essere la soluzione ottimale.

Spero che questo aiuti!

Answer 2

Un buon modo per risolvere questi problemi è utilizzare un risolutore di vincoli per domini finiti.

Ad esempio, utilizzando GNU Prolog:

solve(Out):- 
    People = [Jon, Mary, Alice, Smith, Dick, George, Betty, Lucy], 
    fd_domain(People, 0, 3), % people lives in buildings 0 to 3. 
    fd_atmost(4, People, 0), % at most, 4 people may live in building 0 
    fd_atmost(3, People, 1), % at most, 3 people may live in building 1 
    fd_atmost(2, People, 2), % etc. 
    fd_atmost(1, People, 3), 
    Jon #\= Mary,    % Jon hates Mary 
    Alice #\= Smith,   % etc. 
    Betty #\= Lucy, 
    Jon #\= Alice, 
    Dick #\= George, 
    fd_labeling(People),  % iterate until an acceptable combination is found. 
    People = Out. 

:- solve(O), write(O), nl. 

Dal punto di vista della complessità, questo continua ad essere NP-completo. Ma il risolutore di vincoli può riordinare il modo in cui le assegnazioni vengono eseguite nella fase di etichettatura in modo tale che i vicoli ciechi vengano scoperti presto risultando in un albero di ricerca più piccolo.

Answer 3

templatetypedef ha fornito a very nice proof del motivo per cui il problema è NP-difficile e non ha una soluzione di tempo polinomiale (nota).

Tuttavia, come per molti problemi con NP-hard, ciò non significa che non è possibile risolverlo in modo efficiente nella pratica o che non si può migliorare con una soluzione di forza bruta.

In particolare, è necessario esaminare constraint satisfaction problems. Sono una classe più generale di problemi che descrivono precisamente ciò che stai cercando di risolvere: dati un insieme di vincoli, quali sono i valori che soddisfano tutti i vincoli?

Il libro AIMA ha a very nice chapter su come risolvere questi tipi di problemi. Vi suggerisco di leggerlo perché ci sono molte buone informazioni ed è molto accessibile in quanto il libro è stato progettato per il livello universitario. Ti darò alcune delle grandi idee qui:

Le domande principali sono:

• Quale studente dovrebbe essere assegnato il prossimo nella tua ricorsione?
• In quale ordine devono essere considerati gli edifici per quello studente?

Qui ci sono due euristiche per questo:

• valori minimi rimanenti (MRV) euristici: Al momento di scegliere quale studente da assegnare a un edificio accanto nella vostra ricorsione, scegliere lo studente con le scelte minor numero sinistra.
• Almeno valore vincolante (LCV) euristica: Dopo aver deciso cosa studente a guardare, assegnare l'edificio che esclude le scelte minor numero per i restanti studenti

per l'euristica MRV, rompere i legami scegliendo il studente che ha i maggiori vincoli sugli altri studenti. L'idea alla base di queste euristiche è che si desidera selezionare i percorsi di ricerca che hanno maggiori probabilità di successo (LCV). Ma dato un particolare percorso di ricerca, si vuole fallire il prima possibile per ridurre la quantità di tempo trascorso su quel percorso (MRV).

Inoltre, al posto della ricorsione ingenua con controllo di base in avanti, è necessario utilizzare un algoritmo di ricerca più avanzato come AC-3 che guarda più avanti.

Visto che i problemi di soddisfazione dei vincoli sono così comuni in molte applicazioni di ingegneria del software, ci sono già un sacco di librerie aperte che risolvono in grado di risolverle in modo efficiente. Ovviamente, questo è dato dal fatto che il problema che stai cercando di risolvere è per un'applicazione del mondo reale e non un compito a casa.