Cours Stage - Algorithmes gloutons

Exercice - Algorithmes gloutons

L'énoncé

Je souhaite louer mon vélo à mes amis, mais leurs disponibilités ne leur permettent de le louer qu’à des horaires bien définis. Le problème est de construire un planning de location en louant le vélo au plus d'amis possible.

Soit $n\in\mathbb{N}^{*}$ le nombre d'amis souhaitant louer le vélo. Chacun d'eux, identifié par une lettre $A_i$ où $i$ est un entier compris entre 1 et $n$, est identifié à un intervalle temporel $[d_i,f_i[$ où $d_i$ et $f_i$ désignent respectivement l'heure de début et l'heure de fin de la location.


Question 1

On considère maintenant quatre amis dont les créneaux horaires ne sont plus disjoints.

$A_1 : [1,2[$    $A_2 : [2,3[$     $A_3 : [3,4[$     $A_4 : [0,1[$

 

Sitation 2

 

Donner un planning de location optimal pour cette situation.

Cette situation est simple. Tous les amis peuvent louer le vélos sur des créneaux horaires disjoints. Le planning est donc défini par la suite $[A_4,A_1,A_2,A_3]$ d'amis.

L'algorithme qui mène à ce résultat choisit les amis par ordre croissant des heures de début ou de fin des locations en s'assurant que les intervalles sont disjoints.

Dans cette situation, tous les créneaux horaires sont disjoints, ils sont donc compatibles.

Question 2

On considère maintenant quatre amis dont les créneaux horaires ne sont plus disjoints.

$A_1 : [1,2[$    $A_2 : [2,3[$     $A_3 : [3,4[$     $A_4 : [0,1[$

 

Situation 2

 

Donner l'ensemble des solutions pouvant être construites.

Dans cette situation, les intervalles ne sont plus disjoints, ils ne sont pas compatibles. On peut construire les solutions :

$[A_1,A_2]$    ou    $[A_4,A_2]$    ou    $[A_3]$

Deux amis ne peuvent pas louer le vélo au même moment.

Question 3

Parmi les solutions trouvées précédemment, lesquelles pouvons-nous retenir ?

Seules les deux premières solutions sont retenues puisque la dernière ne maximise pas le nombre de conférenciers choisis.

L'objectif est de louer le vélo au plus d'amis possible.

Question 4

Un ami me propose un algorithme qui consiste à prendre les intervalles les plus courts :

        ▷ choisir l'intervalle le plus court

        ▷ supprimer tous les chevauchements

        ▷ choisir le prochain intervalle le plus court

Cet algorithme est-il de type glouton ?

Un tel algorithme est effectivement de type glouton. Chaque choix fait sélectionne l'une des meilleures possibilités et ne remet jamais en cause les choix précédents.

Un algorithme glouton fait le meilleur choix parmi un ensemble restreint de choix.


Un algorithme ne peut pas remettre en cause les choix précédents.

Question 5

Dessiner un planning pour lequel cet algorithme ne donne pas la meilleure solution.

Dans la situation illustrée ci-dessous, l'algorithme proposé n'est pas optimal :

Situation 3

En effet, la solution de cet algorithme est : $[A_1]$ alors qu'une solution optimale est : $[A_3,A_2]$ qui maximise le nombre de locations.

Appuyé vous sur les situations précédentes.