🍦 👨🏽‍🤝‍👨🏻 👩🏽‍🎨 Le livre «Algorithme parfait. Algorithmes gourmands et programmation dynamique

Bonjour, habrozhiteli! Dans le nouveau livre, Tim Rafgarden parle d'algorithmes gourmands (le problème de la planification, les arbres couvrant minimal, le clustering, les codes Huffman) et la programmation dynamique (le problème du sac à dos, l'alignement des séquences, les chemins les plus courts, les arbres de recherche optimaux). Cet article présente un extrait «Développer un algorithme gourmand». Les algorithmes

gourmands semblent bien adaptés à la tâche de planification du travail, en minimisant la somme pondérée des temps d'exécution. La sortie a une structure itérative, où le travail est traité un à la fois. Pourquoi ne pas utiliser un algorithme gourmand qui décide itérativement quel travail sera le prochain?

La première étape de notre plan consiste à résoudre deux cas particuliers du problème général. Nos solutions à ces cas montreront à quoi pourrait ressembler un algorithme gourmand dans le cas général. Ensuite, nous restreignons le domaine à un seul algorithme candidat et prouvons que c'est ce candidat qui résout correctement le problème. Le processus par lequel nous arrivons à cet algorithme est plus important à retenir que l'algorithme lui-même; ce processus est reproductible et vous pouvez l'utiliser dans vos propres applications.

13.3.1. Deux cas particuliers

Supposons que pour minimiser la somme pondérée des dates d'achèvement, il existe en fait un algorithme gourmand correct. À quoi cela ressemblerait-il si nous supposons que toutes les œuvres ont la même longueur (mais éventuellement des poids différents) ou, inversement, ont le même poids (mais éventuellement des longueurs différentes)?

13.2

(1) , ?
(2) , ?
) ;
) ;
) ;
) ;
( . 13.3.3.)

13.3.2.

En général, le travail peut avoir différents poids et différentes longueurs. Chaque fois que nos deux règles de base - préférer un travail plus court et un travail avec des poids plus élevés - ont la chance que deux emplois coïncident, nous savons lequel planifier en premier (plus court avec des poids plus élevés). Mais que faire si ces deux règles donnent des conseils contradictoires? Que devons-nous faire avec un travail court avec un poids faible et un travail long avec un poids élevé?

Quel sera l'algorithme gourmand le plus simple qui fonctionnera comme il se doit? Chaque travail a deux paramètres, et l'algorithme doit examiner les deux. La meilleure option serait de développer une formule qui compile la longueur et le poids de chaque travail en une seule note (contribution), de sorte que la planification des travaux de la plus haute à la plus basse est garantie pour minimiser le nombre de dates d'achèvement pondérées. Si une telle formule existe, il s'ensuit de nos deux cas particuliers qu'elle doit avoir deux propriétés: (i) en laissant la longueur fixe, elle devrait augmenter du poids de l'ouvrage; (ii) en laissant le poids fixe, il doit diminuer par rapport à la longueur de l'ouvrage (rappelez-vous que plus la note est élevée, mieux c'est). Passez une minute à réfléchir à plusieurs formules qui ont ces deux propriétés.

La fonction la plus simple, qui augmente en poids et diminue en longueur, est peut-être la différence: la
proposition n ° 1 pour la marque de l'œuvre.

La marque indiquée pourrait être négative, mais cela ne fait pas obstacle à la construction cohérente des œuvres de la plus haute à la plus basse. . Cependant, il existe de nombreuses autres options. Par exemple, le rapport de deux paramètres est un autre candidat: la

proposition n ° 2 pour le marquage de l'œuvre

Ces deux fonctions de calcul de la note conduisent à deux algorithmes gourmands différents.

GREEDYDIFF GREED DIFFERENCE

Planifier le travail dans l'ordre décroissant
(rompre arbitrairement la coïncidence des valeurs).

GREEDYRATIO

( ).

Ainsi, déjà notre première étude de cas illustre le premier sujet du paradigme gourmand (section 13.1.2): il n'est généralement pas difficile de proposer plusieurs algorithmes gourmands concurrents pour une tâche. Mais lequel des deux algorithmes, le cas échéant, est correct? Un moyen rapide d'exclure l'un d'eux est de trouver une instance dans laquelle deux algorithmes affichent des planifications différentes avec des valeurs différentes de la fonction objectif. Pour tout algorithme dont les résultats sont pires dans cet exemple, nous pouvons conclure qu'il n'est pas toujours optimal. Dans deux cas particuliers avec des œuvres de même poids ou de même longueur, les deux algorithmes agissent correctement. L'exemple le plus simple possible de l'exclusion de l'un d'eux peut être une instance d'une tâche dans laquelle deux œuvres ont des poids et des longueurs différentes,en conséquence, les deux algorithmes prévoient de fonctionner dans des ordres opposés. Autrement dit, nous recherchons deux œuvres, dont l'ordre dans la différence est l'opposé de leur ordre par rapport. Exemple:

Le premier travail a un rapport plus grand

mais plus grand (–2 vs –1). Ainsi, l'algorithme GreedyDiffplanifie d'abord le deuxième travail, tandis que l'algorithme GreedyRatioplanifie le contraire.

EXERCICE 13.3

Quelle est la somme des dates d'achèvement pondérées dans les calendriers déduits respectivement par les algorithmes GreedyDiffet GreedyRatio?

a) 22 et 23
b) 23 et 22
c) 17 et 17
d) 17 et 11
(Pour une solution et une explication, voir la section 13.3.3.)

Nous avons avancé en excluant l'algorithme GreedyDiffde toute considération ultérieure. Cependant, le résultat de l'exercice 13.3 ne conduit pas directement au fait que l'algorithme GreedyRatiosera toujours optimal. À notre connaissance, il existe d'autres cas où cet algorithme produit un planning non optimal. Vous devez toujours être sceptique à l'égard d'un algorithme qui n'est pas accompagné d'une preuve de son exactitude, même si cet algorithme fait la bonne chose dans plusieurs cas de test et est extrêmement sceptique à l'égard des algorithmes gourmands.

Dans notre cas, l'algorithme est GreedyRatioen fait garanti pour minimiser le nombre de dates d'achèvement pondérées.

Théorème 13.1 (l'exactitude de l'algorithme GreedyRatio) . Pour chaque ensemble de poids de travail positifset des longueurs de travail positives, l' algorithme GreedyRatioaffiche un calendrier avec la plus petite somme possible de dates d'achèvement pondérées.

Cette affirmation logique n'est pas évidente et vous ne devez pas lui faire confiance sans avoir reçu de preuves. Conformément au troisième thème du paradigme gourmand (section 13.1.2), cette preuve reprend toute la section suivante.

, . .

. — , ( ). — , , , . «» ( ) , .

Le thème restant du paradigme gourmand est la simplicité de l'analyse d'exécution (section 13.1.2). Ici, bien sûr, c'est. L'algorithme GreedyRatio trie uniquement les travaux par relation, ce qui prend du temps O (n log n), où n est le nombre de travaux en entrée (voir la note de bas de page 1 à la p. 24).

13.3.3. Solutions d'exercice 13.2–13.3

La solution pour l'exercice 13.2 La

bonne réponse est: (a) . Supposons d'abord que tous les n travaux ont la même durée, disons 1. Ensuite, chaque programme a exactement le même ensemble de délais - {1, 2, 3, ..., n} - et la seule question est de savoir quel type de travail obtient date d'achèvement et quelle est la date limite. Notre sémantique des poids de travail implique certainement que le travail avec un poids plus important devrait recevoir des temps de réalisation plus courts, et cela est vrai. Par exemple, vous ne voudriez pas planifier un travail avec un poids de 10 tiers (avec un délai de 3) et un travail avec un poids de 20 cinquième (avec un délai de 5); vous feriez mieux de changer les positions de ces deux œuvres, ce qui réduirait la somme des délais pondérés de 20 (comme vous pouvez le constater par vous-même).

Le deuxième cas, dans lequel toutes les œuvres ont le même poids, est légèrement plus fin. Ici, vous voulez donner la préférence à un travail plus court. Par exemple, considérons deux travaux de poids unitaire avec des longueurs de 1 et 2. Si vous prévoyez d'abord un travail plus court, les délais d'achèvement seront 1 et 3 avec un total de 4. Dans l'ordre inverse, les délais seront 2 et 3 avec le pire résultat 5. En général, le planifié le travail contribue d'abord au temps d'achèvement de tout travail, car tout travail doit attendre l'achèvement du premier. Toutes choses étant égales par ailleurs, la planification du travail le plus court minimise d'abord cet impact négatif. Le deuxième travail contribue à toutes les dates d'achèvement à l'exception du premier travail, donc le deuxième travail le plus court doit être planifié ensuite, et ainsi de suite.

Solution de l'exercice 13.3

La bonne réponse est b). L'algorithme GreedyDiffprévoit d'abord un deuxième travail. La date limite pour terminer ce travail est

alors que la date limite pour terminer un autre travail est la

somme des délais pondérés pour l'achèvement.

L'algorithme GreedyRatioplanifie d'abord le premier travail, entraînant des délais

et la somme des délais pondérés égaux à

Étant donné que l'algorithme GreedyDiffne parvient pas à calculer la planification optimale pour cet exemple , il n'est pas toujours correct.

»Plus d'informations sur le livre peuvent être trouvées sur le site Web de l'éditeur
» Contenu
» Extrait

pour Khabrozhiteley 25% de réduction sur le coupon - Algorithmes

Lors du paiement de la version papier du livre, un livre électronique est envoyé par e-mail.

Le livre «Algorithme parfait. Algorithmes gourmands et programmation dynamique »

13.3.1. Deux cas particuliers

13.3.2.

13.3.3. Solutions d'exercice 13.2–13.3

More articles: