Corrispondenza di una combinazione di candidati a posizioni di un lavoro in base alle loro competenze

Question

Essenzialmente ho un posto di lavoro con un numero fisso di posizioni, diciamo 3 o 6 e N richiedenti.

Il lavoro richiede un certo numero di abilità dire abilità a, b, c, ... z.

I candidati hanno alcune competenze che il lavoro richiede ma probabilmente non tutte le abilità.

Quello che sto cercando di fare è costruire un algoritmo per abbinare i 3 o 6 candidati in modo tale che le loro capacità combinate soddisfino tutte le abilità che il lavoro richiede per tutte le situazioni. Completamente soddisfacenti tutti, ma nel peggiore dei casi il più possibile

Se questo è simile o uguale a qualsiasi tipo di algoritmo fammi sapere che non riesco a capire come fare questo.

Ho provato a pensare ad una soluzione come aggiungere la persona che ha più competenze di cui ha bisogno il lavoro, quindi cercare di trovare la persona con la persona con più competenze 1 che non ha il lavoro richiesto. Ma ciò crolla se la soluzione è una combinazione di persone con una "media" quantità di abilità.

Ho anche pensato di trasformare le abilità di ciascun candidato in binario 1 o 0 per significare se ce l'hanno, ma ho difficoltà a trasformarlo in qualcosa di utile. Penso che farlo potrebbe essere sulla strada giusta.

Answer 1

Questo non è un algoritmo specifico, ma un approccio per questo tipo di problemi consiste nell'utilizzare un risolutore/ottimizzatore di vincoli. Ad esempio, in Java è possibile utilizzare OptaPlanner.

questi sono fondamentalmente sistemi dichiarativi, quindi invece di spiegare l'algoritmo devi programmare quale sia il problema. Descrivere fondamentalmente lo spazio degli stati e i vincoli per ciò che è o non è una soluzione. Quindi lo esegui e ti dirà se ha trovato una soluzione e quale soluzione ha trovato.

Answer 2

Nota: questa non è una soluzione completa, ma volevo condividere un paio di considerazioni. Si prega di provare e trovare una soluzione migliore.

Quindi, abbiamo n richiedenti e un insieme di competenze mS = {s(1),s(2),...,s(m)}.
Ogni richiedente è, per i nostri scopi, un sottoinsieme A di S che caratterizza le sue abilità.
t è il numero di candidati da scegliere (ad esempio 3 o 6).

Come detto OP, possiamo rappresentare le competenze di ogni richiedente come una stringa di lunghezza m, dove il carattere nella posizione i è 1 se s(i) appartiene A, e 0 in caso contrario.

Esempio:

S = {Programming, Accounting} 

      Programming Accounting 
Applicant1  0   1 
Applicant2  1   1 

riduzione del numero di richiedenti

Possiamo definire il seguente ordine alle ricorrenti: dati due ricorrenti a1 e a2, diciamo che a1 <= a2 se e solo se la seguente affermazione è vera: if a1 has a skill, then a2 also has it. Nell'esempio sopra, abbiamo Applicant1 <= Applicant2.

Ora possiamo filtrare il set dei nostri richiedenti utilizzando questo ordine: se un richiedente a1 è "sotto" un altro richiedente a2 nel nostro ordine, a1 può essere scartatore, poiché la scelta di a2 produrrà sempre almeno lo stesso risultato. Questo può essere fatto nei passi O(n^2).

non ottimali, algoritmo greedy

Una volta che abbiamo finito, vorrei procedere in questo modo:

r = string of lenght m filled with zeros 

choose an applicant a 
r = skills(a) 
best_applicant = null 

APPLICANT_LIST = new LIST 
APPLICANT_LIST.add(a) 
for(counter=0; counter < (t-1); counter ++) 
{ 
    foreach applicant b not in APPLICANT_LIST 
    { 
    if (count(skills(b) OR r) > count(r)) 
    then 
     r = (skills(b) OR r) 
     best_applicant = b 
    } 
    APPLICANT_LIST.add(b) 
} 

In sostanza, avrei scelto un candidato a e iniziare con la sua/il suo set di abilità r, e quindi cercare il richiedente b che aggiungerebbe la maggior parte delle competenze al mio set esistente r per massimizzarlo. Aggiungerei b alla mia lista e ripetere la procedura finché non avrò un gruppo di richiedenti t. Tutto questo viene fatto nei passaggi O(n^2) (poiché t è costante, lo ignoro). Questo pseudocodice potrebbe non essere corretto da uno scopo di programmazione (a seconda della lingua, potresti voler controllare le condizioni di uscita, i puntatori nulli, ecc.), Ma sono sicuro che ti verrà l'idea.

Ho paura che questo metodo non produce sempre la soluzione ottimale, come mostra questo esempio:

t = 3 

a1 000000001111 
a2 000011110000 
a3 111100000000 
a4 110111001101 

se si dovesse cominciare a4, non avrebbe mai arrivare alla soluzione ottimale {a1,a2,a3}. Questo è il prezzo che paghiamo per una soluzione ottimale in ogni fase, ma non considera il problema da una visione globale.

Nota: nell'esempio precedente, la scelta di un richiedente di partenza diverso non sarebbe di aiuto, poiché a4 sarebbe comunque incluso. Potrebbe anche essere completamente avido e scegliere il candidato con il maggior numero di competenze come il nostro primo candidato.