¿Posible problema de NP completo?

Question

Solo me gustaría que alguien verificara si el siguiente problema es NP-completo o si realmente existe una solución mejor/más fácil que la simple verificación de combinación de fuerza bruta.

Tenemos una especie de problema de asignación de recursos en nuestro software y lo explicaré con un ejemplo.

Digamos que necesitamos que 4 personas trabajen durante el turno de día.Este número y el hecho de que se trata de un "turno de día" están registrados en nuestra base de datos.

Sin embargo, no requerimos que cualquiera ocupe esos lugares; hay algunos requisitos que deben cumplirse para cumplir con los requisitos.

De esos 4, digamos que 2 de ellos tiene que ser enfermera y 1 de ellos tiene que ser médico.

Uno de los médicos también tiene que trabajar como parte de un equipo determinado.

Entonces tenemos este conjunto de información:

Turno de dia:4
1 médico
1 médico, necesita trabajar en el equipo A
1 enfermera

Lo anterior no es el problema.El problema surge cuando empezamos a elegir personas para trabajar en el turno de día y tratamos de averiguar si las personas que hemos elegido hasta ahora realmente pueden cumplir los criterios.

Por ejemplo, digamos que elegimos a James, John, Ursula y Mary para trabajar, donde James y Ursula son médicos, John y Mary son enfermeros.

Úrsula también trabaja en el equipo A.

Ahora bien, dependiendo del orden en el que intentemos encajar, podríamos acabar deduciendo que tenemos a las personas adecuadas, o no, a menos que empecemos a probar diferentes combinaciones.

Por ejemplo, si bajamos en la lista y elegimos a Ursula primero, podríamos relacionarla con el criterio de "1 médico".Luego llegamos a James y notamos que, dado que no trabaja en el equipo A, el otro criterio sobre "1 médico, necesita trabajar en el equipo A" no se puede cumplir con él.Como las otras dos personas son enfermeras, tampoco cumplirán ese criterio.

Entonces retrocedemos y probamos con James primero, y él también puede cumplir con los primeros criterios, y luego Ursula puede cumplir con los criterios que necesita ese equipo.

Entonces, el problema nos parece que necesitamos probar diferentes combinaciones hasta que las hayamos probado todas, en cuyo caso tenemos algunos criterios que aún no se han cumplido, incluso si el número total de cabezales que funcionan es el mismo que el total. número de cabezales necesarios, o hemos encontrado una combinación que funciona.

¿Es esta la única solución? ¿Alguien puede pensar en una mejor?

---

Editar:Alguna aclaración.

Los comentarios a esta pregunta mencionan que con estas pocas personas, deberíamos utilizar la fuerza bruta, y estoy de acuerdo, eso es probablemente lo que podríamos hacer, e incluso podríamos hacerlo, en el mismo carril en el que algunos tipos de optimizaciones analizan el tamaño de los datos y selecciona diferentes algoritmos de clasificación con menos gastos generales iniciales si el tamaño de los datos es pequeño.

Sin embargo, el problema es que esto es parte de un sistema de planificación de listas, en el que es posible que haya bastantes personas involucradas, tanto para decir "Necesitamos X personas en el turno de día" como "Tenemos este grupo de Y personas". que lo hará", así como el potencial para un gran "Tenemos esta lista de criterios Z para aquellas X personas que tendrán que coincidir de alguna manera con estas personas Y", y luego se suma al hecho de que tendremos varios días para hacer el mismo cálculo, en tiempo real, mientras el líder ajusta la plantilla, y entonces ha surgido la necesidad de una solución rápida.

Básicamente, el líder verá una información de suma en vivo en la pantalla que indica cuántas personas aún faltan, tanto en el turno diurno en su conjunto, como cuántas personas cumplen con los diversos criterios y cuántas personas realmente tenemos. ned además de los que tenemos.Esta pantalla tendrá que actualizarse semi-en vivo mientras el líder ajusta la lista con "¿Qué pasa si James toma el turno de día en lugar de Ursula y Ursula toma el turno de noche?".

Pero muchas gracias a las personas que han respondido esto hasta ahora, el problema de satisfacción de restricciones parece el camino que debemos seguir, pero definitivamente analizaremos detenidamente todos los enlaces y nombres de algoritmos aquí.

Por eso me encanta StackOverflow :)

Answer 1

Lo que tienes hay un limitación problema de satisfacción de ; su relación con la NP es interesante, porque son típicamente NP pero a menudo no NP-completo, es decir, que son tratables con soluciones en tiempo polinómico.

Como se señala en los comentarios ebo, su situación suena como que puede formularse como un problema de cobertura exacta , que puede aplicar algoritmo de Knuth X a. Si se toma esta tachuela, por favor háganoslo saber cómo funciona para usted.

Answer 2

Todo tiene un aspecto como si tuviera un limitación problema de satisfacción de .

En su caso particular me miro técnicas de propagación de restricciones primeros - que puede ser capaz de reducir el problema a un tamaño manejable de esa manera.

¿Qué pasa si nadie se ajusta a los criterios?

Answer 3

Lo que usted describe es el 'Compañero de problema' que se describe en la ligera esta tesis .

oso conmigo, estoy en busca de una mejor conexión.

Editar

Aquí hay otro tesis .

Answer 4

En cuanto a mí lo más probable es tratar de encontrar a la reducción grafo bipartito juego problema. Además de demostrar que es un problema NP por lo general es mucho más complicado que quedarse no puede encontrar solución polinómica.

Answer 5

No estoy seguro de que su problema es NP, no huele esa manera, pero lo que yo haría si fuera tú estaría a la orden los requisitos para las posiciones tales que intenta llenar la primera más específica, ya que menos personas estará disponible a llenar estas posiciones, por lo que son menos propensos a tener que dar marcha atrás mucho. No hay ninguna razón por qué no debe combinar esto con el algoritmo X, un algoritmo de Knuth-dad pura.

Answer 6

Voy a dejar la teoría a otros, ya que mi comprensión matemática no es tan grande, pero es posible encontrar una herramienta como casuario / o Cassowary.net NSolver útil para representar su problema de forma declarativa como un problema de satisfacción de restricciones y luego resolver el restricciones.

En este tipo de herramientas, se emplea con frecuencia el método simplex combinado con propagación de restricciones para reducir determinísticamente el espacio de la solución y después encontrar una solución óptima dada una función de coste. Para espacios de soluciones más grandes (que no parecen aplicarse en el tamaño del problema que se especifique), se emplean algoritmos genéticos de vez en cuando.

Si no recuerdo mal, NSolver también incluye código de ejemplo en una simplificación de un problema de la enfermera-rostering real que el Dr. Chun trabajó en Hong Kong. Y hay un documento sobre el trabajo que hizo.

Answer 7

Me suena como que tiene un par de problemas separables que sería mucho más fácil de resolver:

- seleccione un médico del equipo A - seleccione otro médico desde cualquier equipo - seleccionar dos enfermeras

Así que hay tres problemas independientes.

Una aclaración, sin embargo, hacer que tiene que tener dos médicos (uno del equipo especificado) y dos enfermeras, o un médico del equipo especificado, dos enfermeras y otro que puede ser médico o enfermera?

Answer 8

Algunas preguntas:

1. ¿El objetivo es satisfacer las restricciones exactamente , o únicamente aproximadamente (pero tanto como sea posible)?
2. ¿Puede una persona ser miembro de varios equipos?
3. ¿Cuáles son todas las restricciones posibles? (Por ejemplo, podríamos necesitar un médico que es un miembro de varios equipos?)

Si desea satisfacer las restricciones exactamente , a continuación, me gustaría pedir las restricciones cada vez menos por el rigor, es decir, los que más difícil se van a lograr (por ejemplo, el médico y el equipo de A en el ejemplo anterior ) se debe comprobar primero

Si desea satisfacer las restricciones aproximadamente , entonces es una historia diferente ... que tendría que especificar algún tipo de ponderación / importancia-función que determina lo que hubiera preferido, cuando no puede coincidir exactamente, y tienen varias posibilidades para elegir.

Answer 9

Si tiene varias o muchas restricciones, eche un vistazo a Planificador de babas (código abierto, java).

Fuerza bruta, rama y atado y técnicas similares llevan mucho tiempo.Algoritmos deterministas como llenar primero los turnos más grandes son muy subóptimos.Las metaheurísticas son una muy buena manera de abordar esto.

Eche un vistazo específico al ejemplo de lista de enfermeras del mundo real de Drools Planner.Es fácil añadir muchas limitaciones, como "las enfermeras jóvenes no quieren trabajar el sábado por la noche" o "algunas enfermeras no quieren trabajar muchos días seguidos".