Algorithmes gourmands expliqués avec des exemples

Qu'est-ce qu'un algorithme gourmand?

Vous avez peut-être entendu parler de nombreuses techniques de conception algorithmique en parcourant certains des articles ici. Certains d'entre eux sont:

  • Force brute
  • Diviser et conquérir
  • Programmation gourmande
  • Programmation dynamique pour n'en nommer que quelques-uns. Dans cet article, vous découvrirez ce qu'est un algorithme glouton et comment vous pouvez utiliser cette technique pour résoudre de nombreux problèmes de programmation qui autrement ne semblent pas anodins.

Imaginez que vous partez en randonnée et que votre objectif est d'atteindre le plus haut sommet possible. Vous avez déjà la carte avant de commencer, mais il y a des milliers de chemins possibles affichés sur la carte. Vous êtes trop paresseux et n'avez tout simplement pas le temps de les évaluer. Vissez la carte! Vous avez commencé la randonnée avec une stratégie simple: soyez gourmand et myope. Prenez simplement les chemins qui montent le plus. Cela semble être une bonne stratégie pour la randonnée. Mais est-ce toujours le meilleur?

Une fois le voyage terminé et que tout votre corps est endolori et fatigué, vous regardez la carte de randonnée pour la première fois. Oh mon Dieu! Il y a une rivière boueuse que j'aurais dû traverser, au lieu de continuer à monter. Cela signifie qu'un algorithme gourmand choisit le meilleur choix immédiat et ne reconsidère jamais ses choix. En termes d'optimisation d'une solution, cela signifie simplement que la solution gourmande essaiera de trouver des solutions optimales locales - qui peuvent être nombreuses - et pourrait manquer une solution optimale globale.

Définition formelle

Supposons que vous ayez une fonction objective qui doit être optimisée (maximisée ou minimisée) à un moment donné. Un algorithme Greedy fait des choix gourmands à chaque étape pour s'assurer que la fonction objectif est optimisée. L'algorithme Greedy n'a qu'un seul coup pour calculer la solution optimale afin qu'il ne revienne jamais en arrière et annule la décision.

Les algorithmes gourmands présentent certains avantages et inconvénients:

  • Il est assez facile de trouver un algorithme gourmand (ou même plusieurs algorithmes gourmands) pour un problème. L'analyse du temps d'exécution pour les algorithmes gourmands sera généralement beaucoup plus facile que pour d'autres techniques (comme Divide and conquer). Pour la technique Divide and conquer, il n'est pas clair si la technique est rapide ou lente. En effet, à chaque niveau de récursivité, la taille de devient plus petite et le nombre de sous-problèmes augmente.
  • La partie difficile est que pour les algorithmes gourmands, vous devez travailler beaucoup plus dur pour comprendre les problèmes d'exactitude. Même avec le bon algorithme, il est difficile de prouver pourquoi il est correct. Prouver qu'un algorithme gourmand est correct est plus un art qu'une science. Cela implique beaucoup de créativité. Habituellement, trouver un algorithme peut sembler trivial, mais prouver qu'il est réellement correct est un tout autre problème.

Problème de planification d'intervalle

Plongeons-nous dans un problème intéressant que vous pouvez rencontrer dans presque toutes les industries ou tous les domaines de la vie. Certains exemples du problème sont les suivants:

  • On vous donne un ensemble de N horaires de cours pour une seule journée dans une université. L'horaire d'une conférence spécifique est de la forme ( heure s, heure f ) où l' heure s représente l'heure de début de cette conférence et de même l' heure f représente l'heure de fin. Étant donné une liste de N programmes de cours, nous devons sélectionner un ensemble maximal de conférences à tenir pendant la journée de sorte   qu'aucune des conférences ne se chevauchent, c'est-à-dire si les conférences Li et Lj sont incluses dans notre sélection, l'heure de début de j > = heure de fin de i ou vice versa .
  • Votre ami travaille comme animateur de camp, et il est chargé d'organiser des activités pour un groupe de campeurs. L'un de ses plans est l'exercice de mini-triathlon suivant: chaque concurrent doit nager 20 tours de piscine, puis faire du vélo 10 miles, puis courir 3 miles.
  • Le plan est d'envoyer les concurrents de manière échelonnée, via la règle suivante: les candidats doivent utiliser la piscine un à la fois. En d'autres termes, le premier concurrent nage les 20 tours, sort et commence à faire du vélo.
  • Dès que cette première personne est sortie de la piscine, un deuxième concurrent commence à nager les 20 tours; dès qu'il ou elle est sorti et commence à faire du vélo, un troisième concurrent commence à nager, et ainsi de suite.
  • Chaque concurrent a un temps de nage projeté, un temps de vélo projeté et un temps de course projeté. Votre ami veut décider d'un programme pour le triathlon: un ordre dans lequel séquencer les départs des concurrents.
  • Disons que l'heure de fin d'un programme est la première heure à laquelle tous les concurrents auront terminé les trois étapes du triathlon, en supposant que les prévisions de temps soient exactes. Quel est le meilleur ordre pour envoyer des gens, si l'on veut que toute la compétition soit terminée le plus tôt possible? Plus précisément, donnez un algorithme efficace qui produit un planning dont le temps de réalisation est le plus petit possible

Le problème de la planification des conférences

Regardons les différentes approches pour résoudre ce problème.

Heure de début la plus ancienne D'abord,  sélectionnez l'intervalle qui a l'heure de début la plus ancienne. Jetez un œil à l'exemple suivant qui rompt cette solution. Cette solution a échoué car il pourrait y avoir un intervalle qui commence très tôt mais qui est très long. Cela signifie que la prochaine stratégie que nous pourrions essayer serait de commencer par examiner des intervalles plus petits.

Première heure de départ en premier

Intervalle le plus petit Premièrement,  c'est-à-dire que vous finissez par sélectionner les cours dans l'ordre de leur intervalle global qui n'est rien d'autre que le leur   finish time - start time. Encore une fois, cette solution n'est pas correcte. Regardez le cas suivant.

Intervalle le plus court d'abord

Vous pouvez clairement voir que la conférence à intervalle le plus court est celle du milieu, mais ce n'est pas la solution optimale ici. Examinons encore une autre solution pour ce problème en tirant des informations de cette solution.

Intervalle le moins conflictuel D'abord,  c'est-à-dire que vous devez examiner les intervalles qui causent le moins de conflits. Encore une fois, nous avons un exemple où cette approche ne parvient pas à trouver une solution optimale.

Intervalle le moins conflictuel en premier

Le diagramme nous montre que l'intervalle le moins conflictuel est celui du milieu avec seulement 2 conflits. Après cela, nous ne pouvons choisir que les deux intervalles aux extrémités avec des conflits de 3 chacun. Mais la solution optimale est de choisir les 4 intervalles au niveau le plus élevé.

Premier temps de finition en premier . C'est l'approche qui nous donne toujours la solution la plus optimale à ce problème. Nous avons tiré de nombreux enseignements des approches précédentes et avons finalement adopté cette approche. Nous trions les intervalles selon l'ordre croissant de leurs heures de fin, puis nous commençons à sélectionner les intervalles dès le début. Regardez le pseudo code suivant pour plus de clarté.

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

Quand utilisons-nous des algorithmes gourmands

Les algorithmes gourmands peuvent vous aider à trouver des solutions à de nombreux problèmes apparemment difficiles. Le seul problème avec eux est que vous pourriez trouver la bonne solution, mais vous ne pourrez peut-être pas vérifier si c'est la bonne. Tous les problèmes gourmands partagent une propriété commune selon laquelle un optima local peut éventuellement conduire à un minimum global sans reconsidérer l'ensemble des choix déjà envisagés.

Les algorithmes gourmands nous aident à résoudre de nombreux types de problèmes, tels que:

Problème de chemin le plus court:

Problème minimum de Spanning Tree dans un graphique

Problème d'encodage Huffman

Problème des centres K