Je suis nouveau ici, mais j'ai une question trouvée dans mon livre de texte. Malheureusement, il n'a pas de réponse donc je me demandais si quelqu'un pouvait s'il vous plaît aider. La question est:
Vous avez la tâche de propager des invitations au sein d'une entreprise. Vous avez seulement le temps de parler à une certaine quantité de personnes, mais vous êtes assuré que si vous invitez quelqu'un, ils inviteront leur patron, cette personne Invitez leur patron, et ainsi de suite, jusqu'au PDG. Vous avez cartographié toute la hiérarchie de la société et a attribué une valeur à chaque personne, indiquant à quel point il serait précieux de les inviter. Compte tenu de cette configuration et un limiter le nombre de personnes avec lesquelles vous pouvez parler, vous voulez calculer l'optimal ensemble de personnes à inviter. Un ensemble optimal de personnes maximisera le total valeur de toutes les personnes invitées, directement ou indirectement, par votre sélection.
Il y aura exactement une personne, le PDG, sans patron dans la hiérarchie. Tout D'autres personnes vont éventuellement répondre à cette personne sur la chaîne de commandement, mais pas nécessairement directement.
Vous êtes garanti que chaque personne aura au plus un patron, mais ce patron peut avoir une autre à son tour. Par exemple, la personne A peut avoir un boss B, dont le patron est C, dont le patron est D, dont le patron est le PDG. Influencer ainsi la personne une volonté influencer automatiquement B, C, D et le PDG.
Différents employés peuvent avoir des patrons en commun dans la chaîne de commandement. Vous ne faites pas Obtenez une valeur supplémentaire pour influencer une personne plus d'une fois. Par exemple, si A et B répondent tous les deux directement au PDG, et vous influencez les deux, vous allez Recevoir une valeur de VAL (A) + VAL (B) + VAL (PDG), pas Val (A) + Val (B) + 2Val (PDG).
Compte tenu d'un entier positif J, sélectionnez le J Personnes qui finiront par résulter dans la plus grande valeur globale.
Je sais que l'approche de la force brute est de simplement rechercher la liste de la valeur maximale J Times, mais ce n'est pas très utile. Je pense qu'il y a une approche de programmation dynamique, mais ma tentative n'a pas toujours fourni la bonne réponse. Toute aide serait appréciée!
3 Réponses :
Soit V [E, K] Soyez la valeur maximale de la délivrance des invitations K aux subordonnés directs et indirects d'E et E, ignorant la valeur de tous les superviseurs directs et indirects de E. Si l'employé e n'a pas de subordonnés, le cas de base est si l'employé e0 a deux subordonnés, E1 et E2, puis la récurrence est La convolution naïve avec plus de deux employés est trop lente, nous devons donc convoller la première paire, puis convoller dans le reste. Je vais omettre les détails.
@David - Il est définitivement optimal de choisir l'employé avec la plus grande valeur marginale. Avez-vous un pseudocode à montrer que cela peut être complété en moins que O (N ^ K)? Ce serait une approche de style de force brute.
@AgirmaDad: Si vous marquez des personnes déjà invitées, alors de marquer une personne particulière, il vous suffit de marcher dans l'arbre jusqu'à ce que vous atteigniez la première personne déjà invitée (chaque personne ci-dessus est nécessairement déjà invitée également). Cela prendra au plus n pas, et il y a au maximum des N personnes à marquer, alors trouver la meilleure personne à ajouter sera au pire o (n ^ 2). Il y a k étapes, donc dans l'ensemble, c'est O (kn ^ 2).
En fait, @nemo semble avoir raison. Cette page Wikipedia mentionne même le problème de couverture maximale, qui est le NP-dur, et qui n'est qu'une légère généralisation de ce problème.
@j_random_hacker Yep, je ne suis pas éveillé. La réponse a été complètement réécrite.
@Davideisenstat - Pas sûr de comprendre ce que vous entendez par convoluation? Je comprends les cas de base et le cas où il y a deux employés, mais je ne suis pas sûr de ce que vous voulez dire comme comment développer cela à plusieurs subordonnés (3, 4 ou plus). Toute aide supplémentaire serait géniale. Merci de vous aider à mieux comprendre. Mise à jour: Votre récurrence est-elle récurrente pour 2 subordonnés O (nk ^ 2)?
@Agirmaad oui à votre mise à jour. La version naïf 3-subordonnée serait Max sur J1, J2 de Val (E0) + V [E1, J2] + V [E2, J2] + V [E3, K - J1 - J2] , qui est O (nk ^ 3). Pour garder l'exposant de souffler avec plus de subordonnés, nous réécrivons à max sur J1 de max sur J2 de ... puis un tas de calculs pour l'intérieur max sont partagés.
@Davideisenstat est O (nk ^ 2) le meilleur alors? Je pense que j'ai peut-être pu venir avec une approche O (NK) mais pas sûr que cela fonctionne. J'essayais de penser à diviser et à conquérir une approche où je divisez la hiérarchie par subordonnés, mais il n'y a pas de moyen propre pour identifier ce qui est préférable sans d'abord atteindre le fond de ce chemin respectif. Il pourrait également être converti sur un problème de chemin le plus long, mais il s'agirait ensuite d'une période d'exécution de O (NK ^ 2 + ..). Merci encore pour votre aide.
Edit: Cette réponse suppose que les valeurs d'invitation des personnes sont toutes non négatives.
Ce problème peut être résolu à l'aide d'un algorithme gourmand. Discutons d'abord du cas où les valeurs sont toutes égales. Nous essayons donc d'inviter le nombre maximum de personnes. L'observation clé est que, dans n'importe quelle solution optimale, vous devez toujours choisir la personne avec le plus grand nombre de supérieurs directs ou indirects. Voici une brève explication de pourquoi: Supposons que la personne donc dans la première étape, nous pouvons toujours sélectionner la personne avec le plus supérieurs. Ensuite, le problème réduit le même problème sur plusieurs arbres plus petits. Par exemple, supposons que nous sélectionnons 3 invités à partir de l'arborescence suivante: Notre première sélection sera Le meilleur choix suivant est Nous pouvons le faire efficacement, car nous devons simplement garder une trace de l'enfant le plus profond (pas nécessairement un enfant direct) de chaque noeud, que nous pouvons calculer à l'avance. Ensuite, nous avons besoin d'une sorte de structure de données de file d'attente prioritaire pour sélectionner le meilleur arbre à choisir. Si vous sélectionnez Pour étendre ceci au cas où les valeurs peuvent être inégales, essentiellement exactement la même idée fonctionne, sauf plutôt que la profondeur, vous devez calculer la valeur totale de tous les supérieurs. Pour chaque nœud x a le plus de supérieurs et que vous avez des sélections qui n'incluent pas la personne x . Considérez la personne y parmi vos sélections qui partage le plus de supérieurs avec x . Ensuite, vous pouvez faire mieux en sélectionnant x au lieu de y . h , qui nous donne automatiquement D , B et a . Ensuite, il reste à sélectionner 2 à partir des trois arbres l , etc. k personnes d'une hiérarchie de taille n , cela devrait donner un O (n + k journal n) algorithme. x , vous gardez une trace de l'enfant y qui a la plus grande valeur totale le long du chemin entre y et x < / code>.
Je pense qu'il y a un problème avec l'approche gourmande si la valeur d'un nœud peut être négative.
Bon point, cela ne fonctionne que si les valeurs ne sont pas négatives, que j'ai supposées être le cas. Mais je suppose que le problème a du sens avec des valeurs négatives aussi.
sonne comme un Problème de graphique . Vous pouvez utiliser l'idée de composants connectés pour réaliser une solution à cela.
personne f est le patron de personne E , qui est à son tour le patron de personne D , ... tout le chemin vers Personne A , alors vous voulez après que le DFS soit capable de dire à O (1) fois que la personne F est le patron de la personne A et vice versa.
N'oubliez pas de conserver un compte pour chaque chef où le compte sera la somme des valeurs de toutes les personnes en dessous de lui, et continuez éventuellement une trace du nombre de personnes.
Le cas optimal serait que vous trouverez toutes les personnes inférieures à la chaîne en premier, sinon l'algorithme doit fonctionner dans O (nk) où k est la chaîne maximale de bas en haut
C'est un peu plus compliqué que de choisir les personnes les plus basses hiérarchiquement: certaines d'entre elles pourraient avoir un ancêtre commun!
Exactement - une approche que j'ai essayée était de boucler à travers ces employés de niveau les plus bas, sélectionnez le MAX, et mettez à jour les valeurs des autres, mais il est toujours extrêmement lent et certainement pas optimal.
Pour clarifier, quelle est la contrainte - le nombre de personnes pouvant assister à la partie ou le nombre d'invitations que vous pouvez écrire? (Pas la même chose parce que certaines personnes sont invitées indirectement)
OP, avez-vous essayé un algorithme gourmand? Pouvez-vous prouver qu'il est optimal? Sinon, quand ça va mal? Est-ce que cela inspire un nouvel algorithme?
Votez pour continuer à ouvrir - il s'agit d'un problème d'algorithmes soigneusement défini soigneusement défini. (Bien que ce soit mieux avec un exemple.)