J'ai donc un problème d'attribution d'emploi qui n'a pas le coût traditionnel de la méthode hongroise.
Par exemple: P>
worker A on job 5 worker B on job 2 worker C on job 1
4 Réponses :
Les coûts factices devraient faire l'affaire. Attribuez un coût de 1 à tout travail possible et un coût infini (si votre système le permet) à des emplois qu'ils ne peuvent pas. L'algorithme hongrois est conçu pour minimiser le coût total dans toutes les tâches, de sorte qu'il incitera les choses naturellement. Il ne devrait pas y avoir de besoin de rendre compte de ce que vous pensez que leurs préférences d'emploi sont; C'est le travail de l'algorithme.
Merci pour la réponse, j'ai pensé à cela en premier, mais craignait que la matrice d'extrémité soit remplie de 0 à la fois de la minumisation de la rangée et de la colonne (sauf sur les positions avec un coût infini), mais peut-être que ce n'est pas un problème? Je suis toujours nouveau à l'algorithme et j'essaie d'apprendre.
Cela ne devrait pas être un problème - tout cela signifie qu'il peut y avoir plus d'une solution tout aussi bonne.
Algorithme hongrois vous donnera une réponse, mais n'utilisez pas les coûts d'infini, car vous ne pouvez pas comparer la forme matricielle: Comment votre ordinateur peut-il comparer Au lieu de cela, utilisez certains coûts qui sont si importants qu'il garantira de ne pas être attribué (et oui, soyez prudent avec débordement). (Infinity + Infinity) et Infinity (sauf si vous ne comparez pas les frais. ). 1, INF, INF et 2, 1, INF ?
Malheureusement, il est impossible de déterminer un tel coût dans le cas général.
C'est vrai - je n'ai pas regardé hongrois pendant un certain temps, mais avec une préférence pas trop clairement définie, il sera difficile de le modifier (je doute), à moins que vous puissiez vous et l'autre réponse, ignorez les préférences.
Attribuez le coût -1 au travail qu'ils peuvent, et les autres sont nuls.
puis exécutez l'algorithme hongrois et cela vous donnera la réponse (cela reviendra-t-il, en fait).
Ne le faites pas avec quelques nombres importants, cela peut provoquer un débordement (sauf si vous ne mettez pas en œuvre le hongrois très soigneusement).
En effet, il s'agit de correspondances maximales dans les graphiques bipartites et il y a tellement de façons de résoudre ce problème, voir Pages Wiki:
http://en.wikipedia.org/wiki/matching_(Graph_Theory)# Maximum_matchings_in_bipartite_graphes
PS: L'algorithme HopCroft-Karp est plus rapide que le hongrois et est plus simple aussi. Ça vaut la peine d'essayer. Une méthode compumée est plus rapide que ces deux, mais il n'est pas recommandé d'apprendre ces algorithmes à tout premier.
PSS: Votre identifiant dans Stackoverflow est une méthode pour résoudre ce problème. C'est un flux de réseau. C'est ce qu'on appelle le chemin d'argument le plus court (SAP). Voir: http://coral.ie.lehigh.edu/ ~ Ted / Files / IE411 / Lectures / Lecture11.PDF
Vous ignorez les préférences. Vous pouvez probablement faire de la plomberie, mais à quel point seriez-vous heureux (plaisanter)?
Désolé, j'aurais dû dire que les préférences ne sont pas importantes, tant que je peux attribuer le nombre maximum d'emplois possibles.
@Ziyaowei Je ne comprends pas quelles sont les préférences exactement.
lol et maintenant je dois apprendre la méthode de chemin d'argumentation la plus courte, est une question d'honneur: p
@sap C'est un peu difficile, vous pouvez d'abord apprendre d'abord un algorithme de base puis essayez de comprendre le flux réseau et la sève.
@Sayakiss Darn! Maintenant, I devez apprendre sur SAP. J'ai été nerd-snipé ! (Et j'étais juste en passant ... ;-)
L'algorithme hongrois pourrait être fait pour travailler ici, mais un algorithme pour non pondé correspondance de bipartite maximum comme
Comme il n'y a pas de coût, comment comparez-vous deux missions différentes?
Je pensais à ajouter des coûts «factimes» basés sur l'indice de préférences d'emploi, par exemple, le travailleur A pour Job 5 a un coût de 3 (parce que c'est le 3ème emploi de cette liste de travailleurs), est-ce une bonne idée?