¿Asigna personas a edificios respetando las preferencias?

Question

Un amigo me hizo una pregunta hoy sobre un problema de asignación. Encontré una solución bastante sencilla, pero creo que se puede simplificar y agilizar. Su ayuda será apreciada.

El problema: Suponiendo que tengo N gente, tengo que asignarlos a M edificios, cada edificio puede albergar K personas. No todas las personas están dispuestas a vivir juntas, así que tengo una matriz de células N * N y un 1 que marca a las personas que están dispuestas a vivir juntas. Si una celda contiene 1, significa que I y J pueden vivir juntos. Obviamente, la matriz es simétrica alrededor de la diagonal principal.

Mi solución es la siguiente (pseudo código):

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; 
} 

acabo de cubrir todos los posibles arreglos utilizando la recursividad. Siento que esto podría ser optimizado en gran medida, y no estoy hablando de heurística, sino de una solución con mucha menos complejidad.

1. ¿Existe algún problema formal conocido que sea similar a esto?
2. ¿Hay algún algoritmo mejor?

Creo que esto podría estar relacionado con el stable marriage problem, aunque no estoy seguro.

Answer 1

Se sabe que este problema es NP-hard por una reducción del problema NP-complete de decomposing a graph into cliques (problema de la camarilla).

Primero, algo de terminología y discusión. Un clique en un gráfico es un conjunto de k nodos diferentes de modo que cada nodo está conectado a cada otro nodo en la camarilla. Un independent set en el gráfico es un conjunto de k nodos diferentes de modo que no hay dos nodos conectados entre sí. Si toma cualquier gráfico G y luego introduce bordes siempre que falta un borde y elimina todos los bordes que existían previamente, obtiene el complement graph del gráfico original. Esto significa que el problema de encontrar una camarilla en un gráfico inicial es equivalente a encontrar un conjunto independiente en el gráfico del complemento.

La razón por la que esto es interesante es que en el problema que está describiendo, se le da un gráfico de personas donde cada borde indica "estas dos personas no pueden alojarse juntas". En consecuencia, puede pensar en el problema que está describiendo como tratando de encontrar una forma de dividir el gráfico en k subgrafos, cada uno de los cuales es un conjunto independiente. Si construyes el complemento de este gráfico, obtienes la gráfica de todas las personas que están bien juntas. En ese caso, desea dividir el grupo en k grupos que son todos camarillas.

Se sabe que el siguiente problema es NP-completo:

Dado un gráfico y un número k, se puede romper los nodos en el gráfico aparte en k camarillas?

Podemos reducir este problema a su problema en tiempo polinomial, lo que indica que su problema es NP-hard. La construcción es simple: dado el gráfico inicial G y el número k, primero construye el complemento de G.Esto significa que si puedes dividir el complemento en k conjuntos independientes, entonces el gráfico original G se puede dividir en k cliques (debido a la dualidad entre camarillas y conjuntos independientes). Ahora, tome este nuevo gráfico y conviértalo en un conjunto de personas, una por nodo, donde dos personas no pueden colocarse en la misma sala como si se conectaran sus nodos en el gráfico original. Ahora, hay una forma de distribuir estas personas en k casas si el complemento de G se puede dividir en k conjuntos independientes si se puede dividir G en k cliques. En consecuencia, el problema conocido NP-completo de la cobertura de camarilla se puede reducir a su problema en tiempo polinomial, por lo que su problema es NP-difícil. Para asegurarse de que cualquier conjunto independiente puede caber en una casa, simplemente configure la capacidad máxima de cada habitación en n, la cantidad de nodos en el gráfico. Esto permite que cualquier conjunto independiente se aloje en cualquier habitación.

Dado que su problema es NP-hard, no puede haber una solución de tiempo polinomial a menos que P = NP. En consecuencia, lo mejor que nadie sabe, no existe un algoritmo de tiempo polinomial y la recursión de retroceso muy bien podría ser la solución óptima.

Espero que esto ayude!

Answer 2

Una buena manera de resolver estos problemas es utilizar un solucionador de restricciones para dominios finitos.

Por ejemplo, utilizando 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. 

Desde un punto de vista la complejidad, este sigue siendo NP-completo. Pero el solucionador de restricciones puede reordenar la forma en que se realizan las asignaciones en el paso de etiquetado, de modo que los callejones sin salida se encuentren pronto, lo que da como resultado un árbol de búsqueda más pequeño.

Answer 3

templatetypedef dio a very nice proof de por qué el problema es NP-hard y no tiene (conocido) solución de tiempo polinomial.

Sin embargo, como con muchos problemas NP-hard, eso no significa que no pueda resolverlo de manera eficiente en la práctica o que no puede mejorar una solución de fuerza bruta.

En particular, debe consultar constraint satisfaction problems. Son una clase más general de problemas que describen precisamente lo que está tratando de resolver: dado un conjunto de restricciones, ¿cuáles son los valores que satisfacen todas las restricciones?

El libro AIMA tiene a very nice chapter sobre cómo solucionar este tipo de problemas. Sugiero que lean sobre eso ya que hay mucha información buena allí y es muy accesible ya que el libro fue diseñado para el nivel de pregrado. Te voy a dar algunas de las grandes ideas aquí:

Las principales preguntas son:

• Cuál estudiante debe ser asignado a continuación en su recursividad?
• ¿En qué orden se deben considerar los edificios para ese estudiante?

Éstos son dos heurísticas para esto:

• restantes valores mínimos (MRV) heurísticos: Al elegir el estudiante debe asignar a un edificio al lado de su recursividad, elegir al estudiante con las opciones menor número de izquierda.
• menos valor limitante (LCV) heurística: Después de decidir lo que el estudiante a la vista, asignar el edificio que descarta las opciones de menor cantidad de los estudiantes restantes

para la heurística MRV, romper los lazos mediante la elección del estudiante que tiene la mayor cantidad de restricciones en los otros estudiantes. La idea detrás de estas heurísticas es que desea elegir rutas de búsqueda que tienen más probabilidades de tener éxito (LCV). Pero dado un camino de búsqueda particular, quiere fallar lo antes posible para reducir la cantidad de tiempo dedicado a esa ruta (MRV).

Además, en lugar de recursividad ingenua con verificación básica adelantada, debe usar un algoritmo de búsqueda más avanzado como AC-3 que se ve más adelante.

Al ver que los problemas de satisfacción de restricciones son tan comunes en muchas aplicaciones de ingeniería de software, ya hay un montón de bibliotecas abiertas que pueden resolverlas de manera eficiente. Por supuesto, esto se debe a que el problema que está tratando de resolver es para una aplicación en el mundo real y no una especie de tarea asignada.