Les bidons d'essence

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 7 — Algorithmes gloutons

Énoncé

Une voiture disposant d'une autonomie de $K$ km se déplace le long d'une route comportant des stations aux positions $p_{0} = 0 < p_{1} < \dots < p_{m}$ . Proposer une méthode gloutonne pour minimiser le nombre d'arrêts de ravitaillement et en prouver l'optimalité.

Corrigé

L'algorithme glouton consiste à s'arrêter à la station accessible la plus lointaine à chaque étape.

def arrets(p: list, K: int) -> list:
    stops, position = [], 0
    i = 0
    while p[i] != p[-1]:
        # Rechercher la station la plus lointaine à portée d'autonomie
        while i + 1 < len(p) and p[i + 1] - position <= K:
            i += 1
        stops.append(p[i])
        position = p[i]
    return stops[:-1] if stops and stops[-1] == p[-1] else stops

Preuve (le glouton reste devant) : Notons $g_{1} < g_{2} < \dots < g_{r}$ les positions des arrêts choisis par le glouton, et $o_{1} < o_{2} < \dots < o_{s}$ ceux d'une planification optimale. Montrons par récurrence que $g_{j} \geq o_{j}$ .

Pour $j = 1$ : le glouton choisit la station maximale accessible depuis le départ $p_{0}$ , donc $g_{1} \geq o_{1}$ .
Si $g_{j} \geq o_{j}$ : la station $o_{j + 1}$ est à une distance maximale de $K$ de $o_{j}$ , et donc à fort fortiori à une distance inférieure ou égale à $K + (g_{j} - o_{j})$ du point $g_{j}$ . L'autonomie de la voiture permet de franchir l'intervalle depuis $g_{j}$ . Le choix du glouton $g_{j + 1}$ étant maximal sur cet intervalle, on a $g_{j + 1} \geq o_{j + 1}$ . Par conséquent, le glouton atteint l'arrivée avec un nombre d'arrêts $r \leq s$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.