Nomina Pianificazione (N persone con N-slot liberi occupato, vincolo-soddisfazione)

Question

problema dichiarazione

Abbiamo un datore di lavoro che vuole intervistare N persone, e quindi rende N slot intervista. Ogni persona ha un programma occupato per quelle slot. Dare un algoritmo che pianifica gli N persone in N slot, se possibile, e restituire un flag/error/etc se è impossibile. Qual è la complessità di runtime più veloce possibile?

miei approcci finora

Naive: ci sono N! modi per pianificare N persone. Passa attraverso tutti loro, per ogni permutazione, controlla se è fattibile. O (n!)

Backtracking:

1. Cercare eventuali fasce orarie di intervista che possono avere solo 1 persona. Pianifica la persona, rimuovila dall'elenco di candidati e rimuovi lo slot.
2. Cerca candidati che possono entrare solo in 1 slot. Pianifica la persona, rimuovila dall'elenco di candidati e rimuovi lo slot.
3. Ripetere 1 & 2 finché non ci sono più combinazioni del genere.
4. Scegli una persona, programmale in modo casuale in uno degli slot disponibili. Ricorda questa operazione.
5. Ripeti 1, 2, 3 finché non abbiamo un programma o c'è un conflitto irrisolvibile. Se abbiamo un programma, restituiscilo. Se c'è un conflitto irrisolvibile, torna indietro.

Questo è il caso peggiore O (n!), Credo - che non è migliore.

Potrebbe esserci un D.P. soluzione pure - ma non la vedo ancora.

Altri pensieri

Il problema può essere rappresentato in una matrice NxN, dove le righe sono "slot", le colonne sono "persone", ed i valori sono "1" gratuitamente e "0" per occupato. Quindi, stiamo cercando una Identity Matrix con scambio di righe in questa matrice. Passaggi 1 & 2 stai cercando una riga o una colonna con un solo "1". (Se il rango della matrice è = N, I significa che esiste una soluzione, ma il contrario non regge) Un altro modo per esaminarlo è trattare la matrice come una matrice di bordo del grafico diretta non pesata. Quindi, i nodi rappresentano ciascuno 1 candidato e 1 slot. Stiamo quindi cercando un insieme di spigoli in modo che ogni nodo nel grafico abbia un bordo in uscita e un margine in entrata. Oppure, con due nodi, sarebbe un grafico bipartito.

Esempio di una matrice:

1 1 1 1 
0 1 1 0 
1 0 0 1 
1 0 0 1 

Answer 1

Come hai sottolineato, il problema è equivalente al problema di trovare un matching massimo in un grafico bipartito (un gruppo di vertici è l'insieme di persone e l'altro sul set di slot, c'è un margine tra un persona e uno slot se la persona è disponibile per questo slot).

Questo problema può essere risolto con Hopcroft-Karp algorithm.

Complessità O (n^(5/2)) nel caso peggiore, meglio se il grafico è scarso.

Answer 2

credo che è possibile utilizzare network flows.

• Creare un vertice u_i per candidato i, e un vertice v_j per lo slot j.
• Creare un nodo di origine s e inserire un bordo (diretto) da s a ogni u_i di capacità 1.
• Fai un nodo lavandino t e mettere un bordo da ciascun v_j a t di capacità 1.
• Mettere un bordo da u_i a v_j se candidato i può interrogare nello slot j.
• Abbiamo i vertici O(N) e il limite O(N^2), il massimo è possibile il flusso è N.
• Trova il flusso max usando, per esempio, la Ford-Fulkerson algorithm, che prende O(E*f) dove E è il numero di bordi e f è il valore della portata massima, quindi prende O(N^3).
• Se il flusso massimo è N, allora abbiamo un programma: se il limite (u_i,v_j) ha il flusso 1, allora intervistiamo il candidato i nello slot j, altrimenti è impossibile.

Con il teorema del flusso integrale, il flusso massimo avrà flussi interi sui bordi, che è 0 o 1, quindi abbiamo un programma valido.

Answer 3

Questo è il Maximum Bipartite Matching problem.

A seconda della densità del grafico, la soluzione più veloce è probabilmente la Hopcroft-Karp algorithm, che viene eseguita al massimo in tempo O (N^(5/2)), ma probabilmente molto più veloce.

Answer 4

Come per l'approccio Programmazione vincoli, può essere modellato in diversi modi, ad esempio con un approccio a matrice e un approccio basato su set.

L'approccio basato sul set è mostrato sotto nel linguaggio CP ad alto livello MiniZinc. s sono le persone disponibili per ogni fascia oraria (usando la notazione impostata); le variabili decisionali sono l'array x (a quale persona dovrebbe essere assegnato ogni volta).

 
include "globals.mzn"; 
int: n = 4; 

% free persons per time slot 
array[1..n] of set of int: s = 
[{1,2,3,4}, 
{2,3}, 
{1,4}, 
{1,4}]; 


% decision variables 
% the assignment of persons to a slot (appointment number 1..n) 
array[1..n] of var 1..n: x; 

solve satisfy; 

constraint 
    % ensure that the appointed person for the time slot is free 
    forall(i in 1..n) (
    x[i] in s[i] 
) 
    /\ % ensure that each person get a distinct time slot 
    alldifferent(x) 
; 

output [ show(x) ]; 

Il modello emette queste 4 soluzioni (a 0,5 ms), ad esempio tempo 1 è assegnata alla persona 3 ecc

 
x: [3, 2, 4, 1] 
---------- 
x: [2, 3, 4, 1] 
---------- 
x: [3, 2, 1, 4] 
---------- 
x: [2, 3, 1, 4] 

Il modello MiniZinc è qui: appointment_scheduling_set.mzn

La matrice modello approccio è qui (senza la sezione di uscita) e utilizzare un approccio di programmazione intera serie: appointment_scheduling.mzn.

 
int: n = 4; 

% rows are time slots 
% columns are people 
array[1..n, 1..n] of int: m = array2d(1..n, 1..n, 
[ 
1, 1, 1, 1, 
0, 1, 1, 0, 
1, 0, 0, 1, 
1, 0, 0, 1, 
]); 

% decision variables 
% the assignment of persons to a slot (appointment number 1..n) 
array[1..n, 1..n] of var 0..1: x; 

solve satisfy; 

constraint 
    forall(i in 1..n) (
    % ensure a free slot 
    sum([m[i,j]*x[i,j] | j in 1..n]) = 1 

    /\ % ensure one assignment per slot and per person 
    sum([x[i,j] | j in 1..n]) = 1 
    /\ 
    sum([x[j,i] | j in 1..n]) = 1 
) 
; 

La soluzione di questo modello è lo stesso, ma presentato in un altro (e più dettagliata) via e - come accade - nello stesso ordine come l'approccio basato set

 
slot 1: 3 
slot 2: 2 
slot 3: 4 
slot 4: 1 
---------- 
slot 1: 2 
slot 2: 3 
slot 3: 4 
slot 4: 1 
---------- 
slot 1: 3 
slot 2: 2 
slot 3: 1 
slot 4: 4 
---------- 
slot 1: 2 
slot 2: 3 
slot 3: 1 
slot 4: 4