algoritmo de programación de citas (N personas con N ranuras libres-ocupado, de satisfacción de restricciones)

Question

Planteamiento del problema

Tenemos un empleador que quiere entrevistar N personas, y por lo tanto hace que N intervalos de entrevista. Cada persona tiene un horario libre para esas máquinas tragamonedas. Proporcione un algoritmo que planifique las N personas en N ranuras, si es posible, y devuelva una bandera/error/etc., si es imposible. ¿Cuál es la complejidad de tiempo de ejecución más rápida posible?

Mis enfoques hasta ahora

Naive: hay N! formas de programar N personas. Examine todos ellos, para cada permutación, verifique si es factible. O (n!)

Backtracking:

1. Busque cualquier ranuras de tiempo de la entrevista que sólo puede tener 1 persona. Programe la persona, quítelos de la lista de candidatos y elimine la ranura.
2. Busque cualquier candidato que solo entre en 1 casilla. Programe la persona, quítelos de la lista de candidatos y elimine la ranura.
3. Repite 1 & 2 hasta que no haya más combinaciones como esa.
4. Elija una persona, planifíquelas al azar en una de sus ranuras disponibles. Recuerde esta operación.
5. Repite 1, 2, 3 hasta que tengamos un cronograma o hay un conflicto no resuelto. Si tenemos un horario, devuélvalo. Si hay un conflicto irresoluble, retroceda.

Este es el O (n!) Peor caso, creo - que no es mejor.

Puede haber un D.P. solución también, pero aún no lo veo.

Otros pensamientos

El problema se puede representar en una matriz NxN, donde las filas son "slots", las columnas son "personas", y los valores son "1" de forma gratuita y "0" para ocupado. Luego, estamos buscando una matriz de identidad intercambiada por filas y columnas dentro de esta matriz. Los pasos 1 & 2 están buscando una fila o una columna con solo un "1". (Si el rango de la matriz es = N, I eso significa que hay una solución. Pero no ocurre lo contrario) Otra forma de verlo es tratar la matriz como una matriz de borde grafica sin peso. Entonces, los nodos representan cada uno 1 candidato y 1 espacio. Estamos buscando un conjunto de bordes para que cada nodo en el gráfico tenga un borde saliente y un borde entrante. O bien, con 2 nodos, sería un gráfico bipartito.

Ejemplo de una matriz:

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

Answer 1

Como señaló, el problema es equivalente al problema de encontrar una coincidencia máxima en un gráfico bipartito (un conjunto de vértices es el conjunto de personas y el otro en el conjunto de ranuras, hay una ventaja entre persona y un espacio si la persona está disponible para este espacio).

Este problema se puede resolver con el Hopcroft-Karp algorithm.

Complejidad O (n^(5/2)) en el peor de los casos, mejor si el gráfico es escaso.

Answer 2

yo creo que se puede utilizar network flows.

• Crear un vértice u_i para el candidato i, y un vértice de v_jj ranura.
• Realice un nodo fuente s y coloque un borde (dirigido) desde s a cada u_i de capacidad 1.
• Hacer un nodo receptor, t y poner un borde de cada v_j a t de la capacidad 1.
• Ponga una ventaja u_i-v_j si el candidato i puede entrevistar en la ranura j.
• Tenemos O(N) vértices y O(N^2) bordes, el máximo posible flujo es N.
• Encuentra el flujo máximo usando, por ejemplo, el Ford-Fulkerson algorithm, que toma O(E*f) donde E es el número de bordes y f es el valor del flujo máximo, por lo que toma O(N^3).
• Si el flujo máximo es N, entonces tenemos un cronograma: si el borde (u_i,v_j) tiene flujo 1, entonces entrevistamos al candidato i en el slot j, de lo contrario es imposible.

Según el teorema del flujo integral, el flujo máximo tendrá un número entero de flujos en los bordes, que es 0 o 1, por lo que tenemos un horario válido.

Answer 3

Este es el Maximum Bipartite Matching problem.

Dependiendo de la densidad del gráfico, la solución más rápida es probablemente la Hopcroft-Karp algorithm, que se ejecuta como máximo en O (N^(5/2)) tiempo, pero probablemente mucho más rápido.

Answer 4

En cuanto al enfoque de programación de restricción, se puede modelar de diferentes maneras, por ejemplo, con un enfoque de matriz y un enfoque basado en conjuntos.

El enfoque basado en conjunto se muestra a continuación en el lenguaje CP de alto nivel MiniZinc. s es la gente que está disponible cada intervalo de tiempo (usando la notación establecida); las variables de decisión son la matriz x (qué persona debe asignarse cada vez).

 
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) ]; 

El modelo emite estas 4 soluciones (en 0,5 ms), p. tiempo 1 se asigna a persona 3 etc.

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

El modelo MiniZinc es aquí: appointment_scheduling_set.mzn

La matriz de modelo de enfoque es aquí (sin la sección de salida) y el uso de un enfoque de programación entera estándar: 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 solución de este modelo es el mismo, aunque presenta en otro (y más detallado) forma y - como es el caso - en el mismo orden que el enfoque basado en el conjunto

 
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