que clustering algoritmos agrupamiento algorithm graph constraint-programming

algorithm - clustering - Algoritmo de programación de citas(N personas con N espacios libres, restricción de satisfacción)



algoritmos de agrupamiento clustering (4)

Planteamiento del problema

Tenemos un empleador que quiere entrevistar a N personas, y por lo tanto hace N espacios para entrevistas. Cada persona tiene un horario libre para esas máquinas tragamonedas. Proporcione un algoritmo que programe a 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

Ingenuo: hay N! Maneras de programar N personas. Ir a través de todos ellos, para cada permutación, comprobar si es factible. ¡En! )

Retroceso:

  1. Busque cualquier horario de entrevista que solo pueda tener 1 persona. Programe a la persona, elimínela de la lista de candidatos y elimine la ranura.
  2. Busque candidatos que solo puedan entrar en 1 espacio. Programe a la persona, elimínela de la lista de candidatos y elimine la ranura.
  3. Repita 1 y 2 hasta que no haya más combinaciones como esa.
  4. Elija una persona, programe al azar en una de sus ranuras disponibles. Recuerda esta operación.
  5. Repita 1, 2, 3 hasta que tengamos un horario o haya un conflicto sin solución. Si tenemos un horario, devuélvelo. Si hay un conflicto sin solución, retrocede.

Este es O (n!) El peor de los casos, creo, que no es mejor.

También podría haber una solución de DP, pero todavía no la veo.

Otros pensamientos

El problema se puede representar en una matriz NxN, donde las filas son "ranuras", las columnas son "personas" y los valores son "1" gratis y "0" para ocupado. Entonces, estamos buscando una Matriz de Identidad intercambiada fila-columna dentro de esta matriz. Los pasos 1 y 2 buscan 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 lo contrario no se cumple) Otra forma de verlo es tratar la matriz como una matriz de borde de gráfico dirigido sin peso. Luego, los nodos representan cada uno 1 candidato y 1 ranura. Luego estamos buscando un conjunto de bordes para que cada nodo en el gráfico tenga un borde saliente y un borde entrante. O, con 2x 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

Como señalaste, 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 un borde entre una persona y una ranura Si la persona está disponible para esta ranura).

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

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

Creo que puedes usar flujos de red .

  • Cree un vértice u_i para el candidato i , y un vértice v_j para la ranura j .
  • Cree un nodo de origen s y coloque un borde (dirigido) de s a cada u_i de capacidad 1.
  • Haga un nodo sumidero t y coloque un borde de cada v_j a t de capacidad 1.
  • Ponga una ventaja de u_i a v_j si el candidato puedo entrevistar en la ranura j .
  • Tenemos vértices O(N^2) bordes O(N^2) , el flujo máximo posible es N
  • Encuentre el flujo máximo utilizando, por ejemplo, el algoritmo Ford-Fulkerson , que toma O(E*f) donde E es el número de bordes 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 programa: si el borde (u_i,v_j) tiene el flujo 1, entonces entrevistamos al candidato i en la ranura j , de lo contrario es imposible.

Por el teorema de flujo integral, el flujo máximo tendrá flujos de números enteros en los bordes, que es 0 o 1, por lo que tenemos un programa válido.

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

El enfoque basado en conjuntos se muestra a continuación en el lenguaje de alto nivel CP MiniZinc . s son las personas que están disponibles en cada intervalo de tiempo (utilizando la notación establecida); las variables de decisión son la matriz x (a qué persona se le debe asignar 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 genera estas 4 soluciones (en 0,5 ms), por ejemplo, el tiempo 1 se asigna a la 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 de MiniZinc está aquí :pointment_scheduling_set.mzn

El modelo de enfoque matricial está aquí (sin la sección de salida) y utiliza un enfoque de programación de enteros 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 la misma, aunque se presenta de otra manera (y más detallada) y, como sucede, en el mismo orden que el enfoque basado en conjuntos.

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