Possible problème NP-complet?

Question

Je voudrais juste quelqu'un pour vérifier si le problème suivant est NP-complet ou s'il est en fait une meilleure / solution plus facile à ce que la simple combinaison de la force brute de vérification.

Nous avons une sorte de-problème d'allocation des ressources dans notre logiciel, et je vais vous expliquer avec un exemple.

Disons que nous avons besoin de 4 personnes à être au travail pendant la journée de décalage. Ce nombre, et le fait qu'il est un « quart de jour » est enregistré dans notre base de données.

Cependant, nous ne demandons pas seulement quelqu'un pour remplir ces taches, il y a des exigences qui doivent être remplies afin de répondre au besoin.

Parmi les 4, disons que deux d'entre eux doit être une infirmière, et 1 d'entre eux doit être médecins.

L'un des médecins doit aussi travailler dans le cadre d'une équipe en particulier.

Nous avons donc cet ensemble d'informations:

  

Day-shift: 4
  1 médecin
  1 médecin, besoin de travailler en équipe A
  Une infirmière

Ce qui précède est pas le problème. Le problème vient quand nous commençons à choisir les gens à travailler le quart de jour et d'essayer de déterminer si les personnes que nous avons cueillies à ce jour peuvent réellement remplir les critères.

Par exemple, disons que nous prenons James, John, Ursula et Mary à travailler, où James et Ursula sont des médecins, John et Mary sont des infirmières.

Ursula travaille également dans l'équipe A.

, en fonction de l'ordre que nous essayons de répondre au besoin, nous pourrions finir par déduisant que nous avons les bonnes personnes, ou non, à moins que nous commençons à essayer différentes combinaisons.

Par exemple, si aller dans la liste et choisissez Ursula première, on pourrait lui correspondre aux critères « 1 médecin ». Puis nous arrivons à James, et nous constatons que depuis qu'il ne travaille pas en équipe A, les autres critères sur « 1 médecin, doivent travailler en équipe A », ne peut être rempli avec lui. Comme les deux autres sont des infirmières, elles ne correspondront pas que les critères non plus.

Nous avons donc revenir en arrière et essayer James d'abord, et lui aussi peut s'adapter aux premiers critères, et Ursula peut répondre aux critères qui a besoin de cette équipe.

Le problème nous semble que nous devons essayer différentes combinaisons jusqu'à ce que nous avons soit les avons tous essayés, dans ce cas, nous avons des critères qui ne sont pas encore rempli, même si le travail nombre total de têtes est le même comme le nombre total de têtes nécessaires, ou nous avons trouvé une combinaison qui fonctionne.

Est-ce la seule solution, peut-on penser à une meilleure?

---

Modifier :. Quelques précisions

Commentaires à cette question mentionne que, avec ce peu de gens, nous devrions aller avec la force brute, et je suis d'accord, c'est probablement ce que nous pouvions faire, et nous pourrions même faire, dans la même voie que certaines optimisations de tri regardent la taille des données et prend différents algorithmes de tri avec des frais généraux moins initial si la taille des données est faible.

Le problème est que cela fait partie d'un système de planification de la liste, dans laquelle vous pourriez avoir un assez grand nombre de personnes impliquées, en tant que « Nous avons besoin de X sur le quart de jour », ainsi que « Nous avons cette piscine des personnes Y qui sera fait », ainsi que le potentiel pour un grand « Nous avons cette liste de critères Z pour les X personnes qui devront correspondre en quelque sorte avec ces personnes Y », puis vous ajoutez au fait que nous aurons un certain nombre de jours pour faire le même calcul pour, en temps réel, comme le leader ajuste la liste, puis la nécessité d'une solution rapide est venu.

En gros, le leader verra une information de somme en direct sur l'écran qui dit combien de personnes sont toujours portées disparues, à la fois sur le quart de jour dans son ensemble, ainsi que le nombre de personnes est mise en place des différents critères, et combien les gens nous fait nis en plus de ceux que nous avons. Cet affichage devra mettre à jour semi-direct alors que le leader ajuste la liste avec « si James prend le quart de jour au lieu de Ursula, et Ursula prend le quart de travail de nuit ».

Mais grand merci au peuple qui a répondu à cette jusqu'à présent, le problème de satisfaction de contraintes comme la façon dont les sonsnous devons aller, mais nous allons voir sans aucun doute difficile à tous les liens et les noms de l'algorithme ici.

Voilà pourquoi j'aime StackOverflow:)

Answer 1

Qu'est-ce que vous avez il y a un problème de satisfaction de contraintes ; leur relation avec NP est intéressant, car ils sont généralement NP, mais souvent pas NP-complets, à savoir qu'ils sont traitables à des solutions en temps polynomiale.

Comme EBO a noté dans les commentaires, votre situation semble que cela peut être formulé comme un problème de couverture exacte , que vous pouvez appliquer algorithme de Knuth X . Si vous prenez cette tactique, s'il vous plaît laissez-nous savoir comment cela fonctionne pour vous.

Answer 2

Il ne semble que vous avez un .

Dans votre cas, je regarde en particulier les techniques de propagation de contraintes premières - vous pourriez être en mesure de réduire le problème à une taille de cette façon.

Qu'est-ce qui se passe si personne ne répond aux critères?

Answer 3

Ce que vous décrivez est le 'problème Roommate', il est décrit légèrement dans cette thèse .

Ours avec moi, je suis à la recherche de meilleurs liens.

EDIT

Voici une autre .

Answer 4

Quant à moi, je très probablement essayer de trouver réduction graphe biparti correspondant problème. Aussi pour prouver ce problème est NP est généralement beaucoup plus compliqué que vous ne pouvez pas rester trouver une solution polynomiale.

Answer 5

Je ne suis pas sûr que votre problème est NP, il ne sent pas de cette façon, mais ce que je ferais si je vous serais d'ordonner les exigences pour les positions telles que vous essayez de remplir la première plus spécifique depuis moins de personnes sera disponible combler ces postes, vous êtes donc moins susceptibles d'avoir à revenir en arrière beaucoup. Il n'y a aucune raison pour laquelle vous ne devriez pas combiner avec l'algorithme X, un algorithme de pur Knuth-ness.

Answer 6

Je vais laisser la théorie à d'autres, étant donné que mon savvy mathématique est pas si grand, mais vous pouvez trouver un outil comme casoar / Cassowary.net ou NSolver utile pour représenter votre problème déclarative comme un problème de satisfaction de contraintes et résoudre le contraintes.

Dans de tels outils, la méthode simplex combinée à la propagation de contrainte est souvent employée pour réduire l'espace de manière déterministe solution, puis trouver une solution optimale étant donné une fonction de coût. Pour les espaces de solutions plus grandes (qui ne semblent pas appliquer la taille du problème que vous spécifiez), parfois des algorithmes génétiques sont utilisés.

Si je me souviens bien, NSolver inclut également dans le code exemple une simplification d'un problème d'infirmière-rostering réelle que le Dr Chun a travaillé sur à Hong Kong. Et il y a un document sur le travail qu'il a fait.

Answer 7

Il me semble que vous avez quelques problèmes séparables qui serait beaucoup plus facile à résoudre:

- choisir un médecin de l'équipe A - choisir un autre médecin de toute équipe - sélectionner deux infirmières

Vous avez donc trois problèmes indépendants.

Une clarification cependant, ne vous devez avoir deux médecins (un de l'équipe spécifiée) et deux infirmières, ou un médecin de l'équipe spécifiée, deux infirmières et un autre qui peut être soit médecin ou une infirmière?

Answer 8

Quelques questions:

1. L'objectif est de satisfaire les contraintes exactement , ou seulement environ (mais autant que possible)?
2. une personne peut-elle être membre de plusieurs équipes?
3. Quelles sont toutes les contraintes possibles? (Par exemple, nous pourrions avoir besoin d'un médecin qui est membre de plusieurs équipes?)

Si vous voulez satisfaire les contraintes exactement , je commanderais les contraintes en moins laissés par, qui est, ceux qui sont les plus difficiles à atteindre (par exemple, le médecin et l'équipe A dans votre exemple ci-dessus ) devrait être vérifiée premier

Si vous voulez satisfaire les contraintes environ , puis est une autre histoire ... vous devez indiquer une sorte de pondération / importance fonction qui détermine ce que nous préférons, quand nous peut ne pas correspondre exactement, et ont plusieurs possibilités de choix.

Answer 9

Si vous avez plusieurs ou de nombreuses contraintes, jetez un oeil à Drools Planner (open source, java).

Brute force , branch and bound et des techniques similaires à prendre longtemps. algorithmes déterministes tels que remplir les plus grands changements premier sont très suboptimale. Les méta-heuristiques sont une très bonne façon de traiter cette question.

Jetez un oeil particulier à l'infirmière dans le monde réel rostering exemple de planificateur Drools. Il est facile d'ajouter de nombreuses contraintes, telles que « les jeunes infirmières ne veulent pas travailler le samedi soir » ou « certaines infirmières ne veulent pas travailler à plusieurs jours de suite ».