Permutation/Algorithme pour résoudre le puzzle de remplissage conditionnel

Question

J'ai creusé pour voir si quelque chose de similaire a été fait précédemment, mais je n'ai rien vu avec les conditions en miroir. Pour faire en sorte que le problème soit plus facile à comprendre, je vais l'appliquer dans le contexte du remplissage d'une liste d'équipes de baseball.

La structure de liste donnée est organisée comme suit: C, 1B, 2B, 3B, SS, 2B/SS (soit ou), 1B/3B, OF, OF, OF, OF, UT (peut être n'importe quelle position) Chaque joueur a au moins une des positions de non-sauvegarde (positions qui permettent plus d'une position) où il est éligible et dans plusieurs cas plus d'un (c'est-à-dire un joueur qui peut jouer 1B et OF, etc.). Dites que vous êtes le manager d'une équipe qui a déjà des joueurs et que vous voulez voir si vous avez de la place pour un joueur en particulier ou si vous pouvez déplacer un ou plusieurs joueurs pour ouvrir un emplacement où il est éligible. Mes tentatives initiales consistaient à utiliser une permutation conditionnelle et à rassembler dans une liste toutes les «files» uniques possibles pour chaque joueur, en mettant à jour les emplacements ouverts avant de passer au joueur suivant. Cela a également requis (puisque l'ordre dans lequel le joueur a été déplacé affecterait les positions disponibles pour le joueur suivant) que la liste bouclée ait été réorganisée puis bouclée à nouveau. Je pense toujours que c'est la voie à suivre, mais il y a un certain nombre d'embûches qui ont accroché la fonction.

Les données pour commencer la boucle que vous assumez est donnée est: 1. Liste des positions du joueur en cours d'évaluation peut joueur (celui qui est vérifié s'il peut s'adapter) 2. Liste des joueurs actuellement sur la liste et les positions de chacun d'entre eux sont éligibles à (Je stocke actuellement une liste de listes et utilise l'index de la liste comme identifiant unique du joueur) 3. Une liste des positions ouvertes comme la liste est actuellement

C'est prouvé un mal de tête plus important que prévu à l'origine. Un collègue m'a même suggéré que la situation que j'ai (qui implique, à une échelle beaucoup plus grande, des affectations conditionnelles pour chaque objet) était NP-complète. Je suis certain que ce n'est pas le cas, puisqu'une fois qu'un joueur a été repositionné dans un alignement particulier en cours de test, la liste entière ne devrait pas avoir besoin d'être réitérée une fois qu'un autre joueur a bougé. C'est le long et court et j'ai finalement décidé de l'ouvrir aux forums.

Merci de votre aide. En raison de restrictions, je ne peux pas poster des portions de code (certaines sont héritées). Il est cependant en cours de traduction en .NET (C# pour le moment). Si des informations supplémentaires sont nécessaires, j'essaierai de réécrire certaines des petites parties de la fonction pour publication.

Joseph G.

ÉDITÉ 07/24/2010 Merci beaucoup pour les réponses. J'ai effectivement examiné l'utilisation d'un algorithme génétique, mais je l'ai finalement abandonné en raison de la quantité de travail nécessaire pour déterminer les résultats ordinaux. Le but ultime du test est de déterminer s'il existe, en fait, un scénario qui renvoie un résultat positif. Il n'est pas nécessaire de déterminer le bénéfice relatif de chaque solution de travail.

J'apprécie les commentaires sur le manque probable de familiarité avec le contexte que j'ai présenté le problème. Le modèle réel est dans la distribution des commandes de construction sur plusieurs serveurs de build spécifiques à la plate-forme. C'est accessible, mais je préférerais ne pas comprendre pourquoi certaines tâches de construction ne peuvent être exécutées que sur certains systèmes et pourquoi certains systèmes ne peuvent exécuter que certains types de commandes de construction.

Il semble que vous ayez compris l'essentiel de ce que je vous ai présenté, mais voici un autre modèle un peu moins spécifique. Il y a un ensemble de positions discrètes dans un tableau ordonné de listes en tant que telles (appelées "positions"):

((2), (2), (3), (4), (5), (6), (4, 6), (3, 5), (7), (7), (7), (7), (7), (2, 3, 4, 5, 6, 7))

De plus, il y a un tableau non ordonné de listes (que je nommerai «employés») qui ne peut occuper qu'un des emplacements si son tableau a un membre en commun avec la liste ordonnée à laquelle il serait assigné. Après que les affectations initiales ont été faites, si un employé supplémentaire arrive, je dois déterminer s'il peut combler l'un des postes vacants, et sinon, si les employés actuels peuvent être réorganisés pour permettre l'un des postes que l'employé peut combler à rendre disponible.

La force brute est quelque chose que je voudrais éviter, car avec une valeur de l'ordre de 40 à 50 objets (et qui va bientôt augmenter), les déterminations individuelles seront très coûteuses à calculer à l'exécution.

Answer 1

Je ne comprends pas du tout le baseball du tout si désolé si je suis sur la mauvaise voie. J'aime les rounders, mais il n'y a que 2 positions à jouer en rounders, un batteur ou tout le monde.

Avez-vous envisagé d'utiliser Genetic Algorithms pour résoudre ce problème? Ils sont très bons pour résoudre les problèmes difficiles de NP et travaillent étonnamment bien pour les problèmes de rotation et de type horaire aussi.

Vous avez un modèle de solution qui peut facilement être marqué et facilement manipulé, ce qui est un bon début pour un algorithme génétique. Pour des problèmes plus complexes où les permutations totales sont trop grandes pour calculer un algorithme génétique, il faut trouver une solution proche de l'optimum ou excellente (avec beaucoup, beaucoup d'autres solutions valables) dans un laps de temps assez court. Bien que si vous souhaitez trouver la solution optimale à chaque fois, vous devrez forcément la forcer brutalement (je n'ai fait qu'effleurer le problème, alors ce n'est peut-être pas le cas mais ça semble être le cas). Dans votre exemple, vous auriez une classe de solution, ceci représente une solution, IE une line-up pour l'équipe de baseball. Vous générez aléatoirement 20 solutions, qu'elles soient valides ou non, alors vous avez un algorithme de notation qui évalue la solution. Dans votre cas, un meilleur joueur dans le line-up marquerait plus qu'un pire joueur, et toute line-up invalide (pour quelque raison que ce soit) forcerait un score de 0.

Toutes les solutions de score 0 sont détruites, et remplacés par de nouveaux, et le reste des solutions se multiplient pour former de nouvelles solutions. Théoriquement et après un temps suffisant, le pool de solutions devrait s'améliorer.

Ceci a l'avantage non seulement de trouver beaucoup de files d'attente uniques valides, mais aussi de les noter. Vous n'avez pas précisé dans votre problème la nécessité d'évaluer les solutions, mais cela offre de nombreux avantages (par exemple, si un joueur est blessé, il peut être temporairement classé comme -10 ou autre). Tous les autres joueurs marquent en fonction de leurs statistiques quantifiables.

Il est évolutif et fonctionne bien.

Answer 2

Il semble que vous ayez un problème de correspondance bipartite. Une partition a un sommet pour chaque joueur de la liste. L'autre a un sommet pour chaque position de la liste. Il y a un bord entre un sommet de joueur et un sommet de position si et seulement si le joueur peut jouer cette position. Vous êtes intéressé par appariements: collections d'arêtes telles qu'aucune extrémité n'est répétée.

Étant donné une affectation de joueurs à des positions (une correspondance) et un nouveau joueur à accueillir, il existe un algorithme simple pour déterminer si cela peut être fait. Direct chaque bord dans la correspondance actuelle de la position au joueur; diriger les autres du joueur à la position. Maintenant, en utilisant la recherche de largeur d'abord, recherchez un chemin du nouveau joueur à une position non assignée. Si vous en trouvez un, il vous indique une série possible de réaffectations. Si vous ne le faites pas, il n'y a pas de correspondance avec tous les joueurs.

Par exemple, le joueur A peut jouer On suppose que les positions 1 ou 2

A--1 
\ 
    \ 
    2 

Nous attribuons provisoirement A à 2. Maintenant B montre et ne peut jouer 2. direct le graphique:

A->1 
< 
    \ 
B->2 

Nous trouvons un chemin B->2->A->1, ce qui signifie "assigner B à 2, déplaçant A à 1".

Il y a beaucoup de jolie théorie pour traiter les appariements hypothétiques. Les algorithmes génétiques ne doivent pas s'appliquer.

---

EDIT: Je dois ajouter qu'en raison de l'utilisation de BFS, il calcule la séquence moins perturbatrice de réaffectations.